The Spectra of Super-Optimal Circulant Preconditioned Toeplitz Systems

Raymond H. CHAN; Xiao Qing JIN; Man Chung YEUNG

doi:10.1137/0728046

The Spectra of Super-Optimal Circulant Preconditioned Toeplitz Systems

Raymond H. CHAN^*, Xiao Qing JIN, Man Chung YEUNG

^*Corresponding author for this work

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

17 Citations (Scopus)

Abstract

The solutions of Hermitian positive-definite Toeplitz systems A_nx = b by the preconditioned conjugate gradient method are studied. The preconditioner, called the 'super-optimal' preconditioner, is the circulant matrix T_n that minimizes ∥I - C_n^-1 A_n∥_F over all circulant matrices C_n. The convergence rate is known to be governed by the distribution of the eigenvalues of T_n^-1 A_n. For n-by-n Toeplitz matrix A_n with entries being Fourier coefficients of a positive function in the Wiener class, the asymptotic behaviour of the eigenvalues of the preconditioned matrix T_n^-1 A_n is found as n increases, and it is proved that they are clustered around one.

Original language	English
Pages (from-to)	871-879
Number of pages	9
Journal	SIAM Journal on Numerical Analysis
Volume	28
Issue number	3
DOIs	https://doi.org/10.1137/0728046
Publication status	Published - Jun 1991
Externally published	Yes

Keywords

Toeplitz matrix
super-optimal preconditioner
circulant matrix
circulant matrix preconditioned conjugate gradient method

Access to Document

10.1137/0728046

Cite this

@article{92fd2f08bbef4838bdcabcf0a230ec0d,

title = "The Spectra of Super-Optimal Circulant Preconditioned Toeplitz Systems",

abstract = "The solutions of Hermitian positive-definite Toeplitz systems Anx = b by the preconditioned conjugate gradient method are studied. The preconditioner, called the 'super-optimal' preconditioner, is the circulant matrix Tn that minimizes ∥I - Cn-1 An∥F over all circulant matrices Cn. The convergence rate is known to be governed by the distribution of the eigenvalues of Tn-1 An. For n-by-n Toeplitz matrix An with entries being Fourier coefficients of a positive function in the Wiener class, the asymptotic behaviour of the eigenvalues of the preconditioned matrix Tn-1 An is found as n increases, and it is proved that they are clustered around one.",

keywords = "Toeplitz matrix, super-optimal preconditioner, circulant matrix, circulant matrix preconditioned conjugate gradient method",

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

year = "1991",

month = jun,

doi = "10.1137/0728046",

language = "English",

volume = "28",

pages = "871--879",

journal = "SIAM Journal on Numerical Analysis",

issn = "0036-1429",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "3",

}

TY - JOUR

T1 - The Spectra of Super-Optimal Circulant Preconditioned Toeplitz Systems

AU - CHAN, Raymond H.

AU - JIN, Xiao Qing

AU - YEUNG, Man Chung

PY - 1991/6

Y1 - 1991/6

N2 - The solutions of Hermitian positive-definite Toeplitz systems Anx = b by the preconditioned conjugate gradient method are studied. The preconditioner, called the 'super-optimal' preconditioner, is the circulant matrix Tn that minimizes ∥I - Cn-1 An∥F over all circulant matrices Cn. The convergence rate is known to be governed by the distribution of the eigenvalues of Tn-1 An. For n-by-n Toeplitz matrix An with entries being Fourier coefficients of a positive function in the Wiener class, the asymptotic behaviour of the eigenvalues of the preconditioned matrix Tn-1 An is found as n increases, and it is proved that they are clustered around one.

AB - The solutions of Hermitian positive-definite Toeplitz systems Anx = b by the preconditioned conjugate gradient method are studied. The preconditioner, called the 'super-optimal' preconditioner, is the circulant matrix Tn that minimizes ∥I - Cn-1 An∥F over all circulant matrices Cn. The convergence rate is known to be governed by the distribution of the eigenvalues of Tn-1 An. For n-by-n Toeplitz matrix An with entries being Fourier coefficients of a positive function in the Wiener class, the asymptotic behaviour of the eigenvalues of the preconditioned matrix Tn-1 An is found as n increases, and it is proved that they are clustered around one.

KW - Toeplitz matrix

KW - super-optimal preconditioner

KW - circulant matrix

KW - circulant matrix preconditioned conjugate gradient method

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

U2 - 10.1137/0728046

DO - 10.1137/0728046

M3 - Journal Article (refereed)

AN - SCOPUS:0026172324

SN - 0036-1429

VL - 28

SP - 871

EP - 879

JO - SIAM Journal on Numerical Analysis

JF - SIAM Journal on Numerical Analysis

IS - 3

ER -

The Spectra of Super-Optimal Circulant Preconditioned Toeplitz Systems

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this