Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Which Circulant Preconditioner is Better?

Authors: V. V. Strela and E. E. Tyrtyshnikov
Journal: Math. Comp. 65 (1996), 137-150
MSC (1991): Primary 15A18, 15A57, 65F15; Secondary 42A16, 15A23
MathSciNet review: 1325875
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1 O. Axelsson and G. Lindskog, On the rate of convergence of the preconditioned conjugate gradient method, Numer. Math. 48 (1986), 499--523. MR 88a:65037b
  • 2 R. H. Chan, The spectrum of a family of circulant preconditioned Toeplitz systems, SIAM J. Numer. Anal. 26 (1989), 503--506. MR 90f:65048
  • 3 R. H. Chan, X-Q. Jin, and M.-C. Yeung, The spectra of super-optimal circulant preconditioned Toeplitz systems, SIAM J. Numer. Anal. 28 (1991), 871--879. MR 92a:65099
  • 4 R. H. Chan and G. Strang, Toeplitz equations by conjugate gradients with circulant preconditioner, SIAM J. Sci. Statist. Comput.10 (1989), 104--119. MR 90d:65069
  • 5 T. Chan, An optimal circulant preconditioner for Toeplitz systems, SIAM J. Sci. Statist. Comput. 9 (1988), 766--771. MR 89e:65046
  • 6 I. Gohberg, T. Kailath, I. Koltracht, and T. Lancaster, Efficient solution of linear systems of equations with recursive structure, Linear Algebra Appl. 80 (1986), 80--113. MR 87i:65058
  • 7 T. Kailath, S. Kung, M. Morf, Displacement ranks of matrices and linear equations, J. Math. Anal. Appl. 68 (1979), 395--407. MR 80k:65029
  • 8 G. Strang, A proposal for Toeplitz matrix calculations, Stud. Appl. Math. 74 (1986), 171--176.
  • 9 V. Strela, Exploration of circulant preconditioning properties, Matrix Methods and Algorithms, IVM RAN, Moscow, 1993, pp. 9--46.
  • 10 M. Tismenetsky, A decomposition of Toeplitz matrices and optimal circulant preconditioning, Linear Algebra Appl. 154/156 (1991), 105--121. MR 92c:65056
  • 11 E. Tyrtyshnikov, Toeplitz matrices, some of their analogues and applications, Dept. Numer. Math., USSR Acad. of Sci., Moscow (1989) (in Russian).
  • 12 ------, Optimal and superoptimal circulant preconditioners, SIAM J. Matrix Anal. Appl. 13 (1992), 459--453. MR 92k:65062
  • 13 ------, A unifying approach to some old and new theorems on distribution and clustering, Linear Algebra Appl. (to appear).
  • 14 ------, Circulant preconditioners with unbounded inverses, Linear Algebra Appl. 216 (1995), 1--23.
  • 15 ------, Fast and parallel inertia finder for Toeplitz expanded matrices, to appear.
  • 16 M. Yeung and R. Chan, Circulant preconditioners for Toeplitz matrices with piecewise continuous generating functions, Math. Comp. 61 (1993), 701--718. MR 94a:65024

Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 15A18, 15A57, 65F15, 42A16, 15A23

Retrieve articles in all journals with MSC (1991): 15A18, 15A57, 65F15, 42A16, 15A23

Additional Information

V. V. Strela
Affiliation: Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139

E. E. Tyrtyshnikov
Affiliation: Institute of Numerical Mathematics, Russian Academy of Sciences, Leninskij Prosp., 32–A, 117334, Moscow, Russia

Keywords: Preconditioning, eigenvalue clustering, circulants, Toeplitz matrices, Fourier series
Received by editor(s): December 28, 1993
Received by editor(s) in revised form: August 3, 1994
Article copyright: © Copyright 1996 American Mathematical Society

American Mathematical Society