Fast Band-Toeplitz Preconditioners for Hermitian Toeplitz Systems

Raymond H. CHAN; Ping Tak Peter TANG

doi:10.1137/0915011

Fast Band-Toeplitz Preconditioners for Hermitian Toeplitz Systems

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

Abstract

This paper considers the solutions of Hermitian Toeplitz systems where the Toeplitz matrices are generated by nonnegative functions ƒ. The preconditioned conjugate gradient method withwell-known circulant preconditioners fails in the case when ƒ has zeros. This paper employs Toeplitz matrices offixed bandwidth as preconditioners. Their generating functions g are trigonometric polynomials of fixed degree and aredetermined by minimizing the maximum relative error ||(ƒ - g)/ƒ||∞. Itis shown that the condition number of systems preconditioned by theband-Toeplitz matrices are O(1) for ƒ, with or withoutzeros. When ƒ is positive, the preconditioned systems converge at thesame rate as other well-known circulant preconditioned systems. An a prioribound of the number of iterations required for convergence is also given.

Original language	English
Pages (from-to)	164-171
Number of pages	8
Journal	SIAM Journal on Scientific Computing
Volume	15
Issue number	1
DOIs	https://doi.org/10.1137/0915011
Publication status	Published - Jan 1994
Externally published	Yes

Keywords

Toeplitz matrix
generating function
preconditioned conjugate gradient method
Chebyshev approximation
Remez algorithm

Access to Document

10.1137/0915011

Cite this

@article{0870b7e1a2364cfbb0f116d5719b61d8,

title = "Fast Band-Toeplitz Preconditioners for Hermitian Toeplitz Systems",

abstract = "This paper considers the solutions of Hermitian Toeplitz systems where the Toeplitz matrices are generated by nonnegative functions ƒ. The preconditioned conjugate gradient method withwell-known circulant preconditioners fails in the case when ƒ has zeros. This paper employs Toeplitz matrices offixed bandwidth as preconditioners. Their generating functions g are trigonometric polynomials of fixed degree and aredetermined by minimizing the maximum relative error ||(ƒ - g)/ƒ||∞. Itis shown that the condition number of systems preconditioned by theband-Toeplitz matrices are O(1) for ƒ, with or withoutzeros. When ƒ is positive, the preconditioned systems converge at thesame rate as other well-known circulant preconditioned systems. An a prioribound of the number of iterations required for convergence is also given.",

keywords = "Toeplitz matrix, generating function, preconditioned conjugate gradient method, Chebyshev approximation, Remez algorithm",

author = "CHAN, {Raymond H.} and TANG, {Ping Tak Peter}",

year = "1994",

month = jan,

doi = "10.1137/0915011",

language = "English",

volume = "15",

pages = "164--171",

journal = "SIAM Journal on Scientific Computing",

issn = "1064-8275",

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

number = "1",

}

TY - JOUR

T1 - Fast Band-Toeplitz Preconditioners for Hermitian Toeplitz Systems

AU - CHAN, Raymond H.

AU - TANG, Ping Tak Peter

PY - 1994/1

Y1 - 1994/1

N2 - This paper considers the solutions of Hermitian Toeplitz systems where the Toeplitz matrices are generated by nonnegative functions ƒ. The preconditioned conjugate gradient method withwell-known circulant preconditioners fails in the case when ƒ has zeros. This paper employs Toeplitz matrices offixed bandwidth as preconditioners. Their generating functions g are trigonometric polynomials of fixed degree and aredetermined by minimizing the maximum relative error ||(ƒ - g)/ƒ||∞. Itis shown that the condition number of systems preconditioned by theband-Toeplitz matrices are O(1) for ƒ, with or withoutzeros. When ƒ is positive, the preconditioned systems converge at thesame rate as other well-known circulant preconditioned systems. An a prioribound of the number of iterations required for convergence is also given.

AB - This paper considers the solutions of Hermitian Toeplitz systems where the Toeplitz matrices are generated by nonnegative functions ƒ. The preconditioned conjugate gradient method withwell-known circulant preconditioners fails in the case when ƒ has zeros. This paper employs Toeplitz matrices offixed bandwidth as preconditioners. Their generating functions g are trigonometric polynomials of fixed degree and aredetermined by minimizing the maximum relative error ||(ƒ - g)/ƒ||∞. Itis shown that the condition number of systems preconditioned by theband-Toeplitz matrices are O(1) for ƒ, with or withoutzeros. When ƒ is positive, the preconditioned systems converge at thesame rate as other well-known circulant preconditioned systems. An a prioribound of the number of iterations required for convergence is also given.

KW - Toeplitz matrix

KW - generating function

KW - preconditioned conjugate gradient method

KW - Chebyshev approximation

KW - Remez algorithm

UR - https://www.mendeley.com/catalogue/639a1c21-be36-31b4-b68f-e01cc341716c/

U2 - 10.1137/0915011

DO - 10.1137/0915011

M3 - Journal Article (refereed)

SN - 1064-8275

VL - 15

SP - 164

EP - 171

JO - SIAM Journal on Scientific Computing

JF - SIAM Journal on Scientific Computing

IS - 1

ER -

Fast Band-Toeplitz Preconditioners for Hermitian Toeplitz Systems

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this