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 T. Ku and C. Kuo, Design and analysis of Toeplitz preconditioners, IEEE Trans. Acoust. Speech Signal Process. (to appear). W. Rudin, Principles of mathematical analysis, 3rd ed., McGraw-Hill, New York, 1985. G. Strang, A proposal for Toeplitz matrix calculations, Stud. Appl. Math. 74 (1986), 171-176.
- 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
Additional Information
- © Copyright 1992 American Mathematical Society
- Journal: Math. Comp. 58 (1992), 233-240
- MSC: Primary 65F10; Secondary 65F15
- DOI: https://doi.org/10.1090/S0025-5718-1992-1106960-1
- MathSciNet review: 1106960