Circulant preconditioners for Toeplitz matrices with piecewise continuous generating functions
HTML articles powered by AMS MathViewer
- by Man-Chung Yeung and Raymond H. Chan PDF
- Math. Comp. 61 (1993), 701-718 Request permission
Abstract:
We consider the solution of n-by-n Toeplitz systems ${T_n}x = b$ by preconditioned conjugate gradient methods. The preconditioner ${C_n}$ is the T. Chan circulant preconditioner, which is defined to be the circulant matrix that minimizes ${\left \| {{B_n} - {T_n}} \right \|_F}$ over all circulant matrices ${B_n}$. For Toeplitz matrices generated by positive $2\pi$-periodic continuous functions, we have shown earlier that the spectrum of the preconditioned system $C_n^{ - 1}{T_n}$ is clustered around 1 and hence the convergence rate of the preconditioned system is superlinear. However, in this paper, we show that if instead the generating function is only piecewise continuous, then for all $\varepsilon$ sufficiently small, there are $O(\log n)$ eigenvalues of $C_n^{ - 1}{T_n}$ that lie outside the interval $(1 - \varepsilon ,1 + \varepsilon )$. In particular, the spectrum of $C_n^{ - 1}{T_n}$ cannot be clustered around 1. Numerical examples are given to verify that the convergence rate of the method is no longer superlinear in general.References
- Gregory S. Ammar and William B. Gragg, Superfast solution of real positive definite Toeplitz systems, SIAM J. Matrix Anal. Appl. 9 (1988), no. 1, 61–76. SIAM Conference on Linear Algebra in Signals, Systems, and Control (Boston, Mass., 1986). MR 938136, DOI 10.1137/0609005
- 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, Toeplitz preconditioners for Toeplitz systems with nonnegative generating functions, IMA J. Numer. Anal. 11 (1991), no. 3, 333–345. MR 1118960, DOI 10.1093/imanum/11.3.333 R. Chan and K. Ng, Fast iterative solvers for Toeplitz-plus-band systems, SIAM J. Sci. Statist. Comput. (to appear).
- 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 and Man-Chung Yeung, Circulant preconditioners for Toeplitz matrices with positive continuous generating functions, Math. Comp. 58 (1992), no. 197, 233–240. MR 1106960, DOI 10.1090/S0025-5718-1992-1106960-1
- Raymond H. Chan and Man-Chung Yeung, Jackson’s theorem and circulant preconditioned Toeplitz systems, J. Approx. Theory 70 (1992), no. 2, 191–205. MR 1172018, DOI 10.1016/0021-9045(92)90084-2
- Raymond H. Chan and Man-Chung Yeung, Circulant preconditioners constructed from kernels, SIAM J. Numer. Anal. 29 (1992), no. 4, 1093–1103. MR 1173187, DOI 10.1137/0729066
- 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
- Thomas Huckle, Circulant and skewcirculant matrices for solving Toeplitz matrix problems, SIAM J. Matrix Anal. Appl. 13 (1992), no. 3, 767–777. Iterative methods in numerical linear algebra (Copper Mountain, CO, 1990). MR 1168078, DOI 10.1137/0613048 T. Ku and C. Kuo, Design and analysis of Toeplitz preconditioners, IEEE Trans. Signal Process. 40 (1991), 129-141.
- Zeev Nehari, On bounded bilinear forms, Ann. of Math. (2) 65 (1957), 153–162. MR 82945, DOI 10.2307/1969670 G. Strang, A proposal for Toeplitz matrix calculations, Stud. Appl. Math. 74 (1986), 171-176.
- Miron Tismenetsky, A decomposition of Toeplitz matrices and optimal circulant preconditioning, Linear Algebra Appl. 154/156 (1991), 105–121. MR 1113141, DOI 10.1016/0024-3795(91)90375-7
- L. N. Trefethen, Approximation theory and numerical linear algebra, Algorithms for approximation, II (Shrivenham, 1988) Chapman and Hall, London, 1990, pp. 336–360. MR 1071991
- 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
- Evgenij E. Tyrtyshnikov, A unifying approach to some old and new theorems on distribution and clustering, Linear Algebra Appl. 232 (1996), 1–43. MR 1366576, DOI 10.1016/0024-3795(94)00025-5
- James S. Walker, Fourier analysis, Oxford University Press, New York, 1988. MR 957507
- Harold Widom, Hankel matrices, Trans. Amer. Math. Soc. 121 (1966), 1–35. MR 187099, DOI 10.1090/S0002-9947-1966-0187099-X
- J. H. Wilkinson, The algebraic eigenvalue problem, Clarendon Press, Oxford, 1965. MR 0184422
Additional Information
- © Copyright 1993 American Mathematical Society
- Journal: Math. Comp. 61 (1993), 701-718
- MSC: Primary 65F35
- DOI: https://doi.org/10.1090/S0025-5718-1993-1195423-4
- MathSciNet review: 1195423