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

DOI:
https://doi.org/10.1090/S0025-5718-96-00682-5

MathSciNet review:
1325875

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: The eigenvalue clustering of matrices and is experimentally studied, where , and respectively are Toeplitz matrices, Strang, and optimal circulant preconditioners generated by the Fourier expansion of a function . Some illustrations are given to show how the clustering depends on the smoothness of 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 , where is a Toeplitz matrix and is a circulant. In particular, it is proved that the Toeplitz (displacement) rank of is not greater than 4, provided that and are symmetric.

**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**

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

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

DOI:
https://doi.org/10.1090/S0025-5718-96-00682-5

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