Which circulant preconditioner is better?
HTML articles powered by AMS MathViewer
- by V. V. Strela and E. E. Tyrtyshnikov PDF
- Math. Comp. 65 (1996), 137-150 Request permission
Abstract:
The eigenvalue clustering of matrices $S_n^{-1}A_n$ and $C_n^{-1}A_n$ is experimentally studied, where $A_n$, $S_n$ and $C_n$ respectively are Toeplitz matrices, Strang, and optimal circulant preconditioners generated by the Fourier expansion of a function $f(x)$. Some illustrations are given to show how the clustering depends on the smoothness of $f(x)$ and which preconditioner is preferable. An original technique for experimental exploration of the clustering rate is presented. This technique is based on the bisection idea and on the Toeplitz decomposition of a three-matrix product $CAC$, where $A$ is a Toeplitz matrix and $C$ is a circulant. In particular, it is proved that the Toeplitz (displacement) rank of $CAC$ is not greater than 4, provided that $C$ and $A$ are symmetric.References
- Owe Axelsson and Gunhild Lindskog, On the eigenvalue distribution of a class of preconditioning methods, Numer. Math. 48 (1986), no. 5, 479–498. MR 839613, DOI 10.1007/BF01389447
- 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, 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
- 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
- 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
- I. Gohberg, T. Kailath, and I. Koltracht, Efficient solution of linear systems of equations with recursive structure, Linear Algebra Appl. 80 (1986), 81–113. MR 851934, DOI 10.1016/0024-3795(86)90279-X
- Thomas Kailath, Sun Yuan Kung, and Martin Morf, Displacement ranks of matrices and linear equations, J. Math. Anal. Appl. 68 (1979), no. 2, 395–407. MR 533501, DOI 10.1016/0022-247X(79)90124-0
- G. Strang, A proposal for Toeplitz matrix calculations, Stud. Appl. Math. 74 (1986), 171–176.
- V. Strela, Exploration of circulant preconditioning properties, Matrix Methods and Algorithms, IVM RAN, Moscow, 1993, pp. 9–46.
- 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
- E. Tyrtyshnikov, Toeplitz matrices, some of their analogues and applications, Dept. Numer. Math., USSR Acad. of Sci., Moscow (1989) (in Russian).
- 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
- —, A unifying approach to some old and new theorems on distribution and clustering, Linear Algebra Appl. (to appear).
- —, Circulant preconditioners with unbounded inverses, Linear Algebra Appl. 216 (1995), 1–23.
- —, Fast and parallel inertia finder for Toeplitz expanded matrices, to appear.
- Man-Chung Yeung and Raymond H. Chan, Circulant preconditioners for Toeplitz matrices with piecewise continuous generating functions, Math. Comp. 61 (1993), no. 204, 701–718. MR 1195423, DOI 10.1090/S0025-5718-1993-1195423-4
Additional Information
- V. V. Strela
- Affiliation: Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
- Email: strela@math.mit.edu
- E. E. Tyrtyshnikov
- Affiliation: Institute of Numerical Mathematics, Russian Academy of Sciences, Leninskij Prosp., 32–A, 117334, Moscow, Russia
- Email: tee@adonis.iasnet.com
- Received by editor(s): December 28, 1993
- Received by editor(s) in revised form: August 3, 1994
- © Copyright 1996 American Mathematical Society
- Journal: Math. Comp. 65 (1996), 137-150
- MSC (1991): Primary 15A18, 15A57, 65F15; Secondary 42A16, 15A23
- DOI: https://doi.org/10.1090/S0025-5718-96-00682-5
- MathSciNet review: 1325875