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 Free Access

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?)

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