Circulant and skew-circulant preconditioners for skew-hermitian type Toeplitz systems

Raymond H. CHAN; Xiao Qing JIN

doi:10.1007/BF01933178

Circulant and skew-circulant preconditioners for skew-hermitian type Toeplitz systems

Raymond H. CHAN^*, Xiao Qing JIN

^*Corresponding author for this work

Research output: Journal Publications › Journal Article (refereed) › peer-review

26 Citations (Scopus)

Abstract

We study the solutions of Toeplitz systems A_nx=b by the preconditioned conjugate gradient method. The n ×n matrix A_n is of the form a₀I+H_n where a₀ is a real number, I is the identity matrix and H_n is a skew-Hermitian Toeplitz matrix. Such matrices often appear in solving discretized hyperbolic differential equations. The preconditioners we considered here are the circulant matrix C_n and the skew-circulant matrix S_n where A_n=1/2(C_n+S_n). The convergence rate of the iterative method depends on the distribution of the singular values of the matrices C^-1_n A_n and S^-1_nA_n. For Toeplitz matrices A_n with entries which are Fourier coefficients of functions in the Wiener class, we show the invertibility of C_n and S_n and prove that the singular values of C^-1_nA_n and S^-1_nA_n are clustered around 1 for large n. Hence, if the conjugate gradient method is applied to solve the preconditioned systems, we expect fast convergence.

Original language	English
Pages (from-to)	632-646
Number of pages	15
Journal	BIT
Volume	31
Issue number	4
DOIs	https://doi.org/10.1007/BF01933178
Publication status	Published - Dec 1991
Externally published	Yes

Keywords

circulant matrix
preconditioned conjugate gradient method
skew-circulant matrix
Skew-Hermitian type Toeplitz matrix

Access to Document

10.1007/BF01933178

Cite this

@article{dd2641c312c44f11b8c0c7d3182545b3,

title = "Circulant and skew-circulant preconditioners for skew-hermitian type Toeplitz systems",

abstract = "We study the solutions of Toeplitz systems Anx=b by the preconditioned conjugate gradient method. The n ×n matrix An is of the form a0I+Hn where a0 is a real number, I is the identity matrix and Hn is a skew-Hermitian Toeplitz matrix. Such matrices often appear in solving discretized hyperbolic differential equations. The preconditioners we considered here are the circulant matrix Cn and the skew-circulant matrix Sn where An=1/2(Cn+Sn). The convergence rate of the iterative method depends on the distribution of the singular values of the matrices C-1n An and S-1nAn. For Toeplitz matrices An with entries which are Fourier coefficients of functions in the Wiener class, we show the invertibility of Cn and Sn and prove that the singular values of C-1nAn and S-1nAn are clustered around 1 for large n. Hence, if the conjugate gradient method is applied to solve the preconditioned systems, we expect fast convergence.",

keywords = "circulant matrix, preconditioned conjugate gradient method, skew-circulant matrix, Skew-Hermitian type Toeplitz matrix",

author = "CHAN, {Raymond H.} and JIN, {Xiao Qing}",

year = "1991",

month = dec,

doi = "10.1007/BF01933178",

language = "English",

volume = "31",

pages = "632--646",

journal = "BIT",

issn = "0006-3835",

publisher = "Springer Netherlands",

number = "4",

}

TY - JOUR

T1 - Circulant and skew-circulant preconditioners for skew-hermitian type Toeplitz systems

AU - CHAN, Raymond H.

AU - JIN, Xiao Qing

PY - 1991/12

Y1 - 1991/12

N2 - We study the solutions of Toeplitz systems Anx=b by the preconditioned conjugate gradient method. The n ×n matrix An is of the form a0I+Hn where a0 is a real number, I is the identity matrix and Hn is a skew-Hermitian Toeplitz matrix. Such matrices often appear in solving discretized hyperbolic differential equations. The preconditioners we considered here are the circulant matrix Cn and the skew-circulant matrix Sn where An=1/2(Cn+Sn). The convergence rate of the iterative method depends on the distribution of the singular values of the matrices C-1n An and S-1nAn. For Toeplitz matrices An with entries which are Fourier coefficients of functions in the Wiener class, we show the invertibility of Cn and Sn and prove that the singular values of C-1nAn and S-1nAn are clustered around 1 for large n. Hence, if the conjugate gradient method is applied to solve the preconditioned systems, we expect fast convergence.

AB - We study the solutions of Toeplitz systems Anx=b by the preconditioned conjugate gradient method. The n ×n matrix An is of the form a0I+Hn where a0 is a real number, I is the identity matrix and Hn is a skew-Hermitian Toeplitz matrix. Such matrices often appear in solving discretized hyperbolic differential equations. The preconditioners we considered here are the circulant matrix Cn and the skew-circulant matrix Sn where An=1/2(Cn+Sn). The convergence rate of the iterative method depends on the distribution of the singular values of the matrices C-1n An and S-1nAn. For Toeplitz matrices An with entries which are Fourier coefficients of functions in the Wiener class, we show the invertibility of Cn and Sn and prove that the singular values of C-1nAn and S-1nAn are clustered around 1 for large n. Hence, if the conjugate gradient method is applied to solve the preconditioned systems, we expect fast convergence.

KW - circulant matrix

KW - preconditioned conjugate gradient method

KW - skew-circulant matrix

KW - Skew-Hermitian type Toeplitz matrix

UR - http://www.scopus.com/inward/record.url?scp=0041600220&partnerID=8YFLogxK

U2 - 10.1007/BF01933178

DO - 10.1007/BF01933178

M3 - Journal Article (refereed)

AN - SCOPUS:0041600220

SN - 0006-3835

VL - 31

SP - 632

EP - 646

JO - BIT

JF - BIT

IS - 4

ER -

Circulant and skew-circulant preconditioners for skew-hermitian type Toeplitz systems

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this