Circulant preconditioners for Toeplitz matrices with positive continuous generating functions

Chan, Raymond H.; Yeung, Man-Chung

doi:10.1090/S0025-5718-1992-1106960-1

Circulant preconditioners for Toeplitz matrices with positive continuous generating functions
HTML articles powered by AMS MathViewer

by Raymond H. Chan and Man-Chung Yeung PDF

Math. Comp. 58 (1992), 233-240 Request permission

Abstract:

We consider the solution of n-by-n Toeplitz systems ${A_n}x = b$ by the preconditioned conjugate gradient method. The preconditioner ${C_n}$ is the circulant matrix that minimizes ${\left \| {{B_n} - {A_n}} \right \|_F}$ over all circulant matrices ${B_n}$. We show that if the generating function f is a positive $2\pi$-periodic continuous function, then the spectrum of the preconditioned system $C_n^{ - 1}{A_n}$ will be clustered around one. In particular, if the preconditioned conjugate gradient method is applied to solve the preconditioned system, the convergence rate is superlinear.

References

Raymond H. Chan and Gilbert Strang, Toeplitz equations by conjugate gradients with circulant preconditioner, SIAM J. Sci. Statist. Comput. 10 (1989), no. 1, 104–119. MR 976165, DOI 10.1137/0910009
Raymond H. Chan, The spectrum of a family of circulant preconditioned Toeplitz systems, SIAM J. Numer. Anal. 26 (1989), no. 2, 503–506. MR 987404, DOI 10.1137/0726029
Raymond H. Chan, Circulant preconditioners for Hermitian Toeplitz systems, SIAM J. Matrix Anal. Appl. 10 (1989), no. 4, 542–550. MR 1016802, DOI 10.1137/0610039
Raymond H. Chan, Xiao-Qing Jin, and Man-Chung Yeung, The circulant operator in the Banach algebra of matrices, Linear Algebra Appl. 149 (1991), 41–53. MR 1092868, DOI 10.1016/0024-3795(91)90324-P
Raymond H. Chan, Xiao-Qing Jin, and Man-Chung Yeung, The spectra of super-optimal circulant preconditioned Toeplitz systems, SIAM J. Numer. Anal. 28 (1991), no. 3, 871–879. MR 1098422, DOI 10.1137/0728046
Tony F. Chan, An optimal circulant preconditioner for Toeplitz systems, SIAM J. Sci. Statist. Comput. 9 (1988), no. 4, 766–771. MR 945937, DOI 10.1137/0909051
E. W. Cheney, Introduction to approximation theory, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1966. MR 0222517
Ulf Grenander and Gábor Szegő, Toeplitz forms and their applications, 2nd ed., Chelsea Publishing Co., New York, 1984. MR 890515

Design and analysis of Toeplitz preconditioners

Principles of mathematical analysis

A proposal for Toeplitz matrix calculations

74

Evgenij E. Tyrtyshnikov, Optimal and superoptimal circulant preconditioners, SIAM J. Matrix Anal. Appl. 13 (1992), no. 2, 459–473. MR 1152763, DOI 10.1137/0613030
J. H. Wilkinson, The algebraic eigenvalue problem, Clarendon Press, Oxford, 1965. MR 0184422
A. Zygmund, Trigonometric series. 2nd ed. Vols. I, II, Cambridge University Press, New York, 1959. MR 0107776