Which circulant preconditioner is better?

Strela, V.; Tyrtyshnikov, E.

doi:10.1090/S0025-5718-96-00682-5

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