Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



On the asymptotic spectrum of Hermitian block Toeplitz matrices with Toeplitz blocks

Author: Paolo Tilli
Journal: Math. Comp. 66 (1997), 1147-1159
MSC (1991): Primary 65F15
MathSciNet review: 1408378
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We study the asymptotic behaviour of the eigenvalues of Hermitian $n\times n$ block Toeplitz matrices $A_{n,m}$, with $m\times m$ Toeplitz blocks. Such matrices are generated by the Fourier coefficients of an integrable bivariate function $f$, and we study their eigenvalues for large $n$ and $m$, relating their behaviour to some properties of $f$ as a function; in particular we show that, for any fixed $k$, the first $k$ eigenvalues of $A_{n,m}$ tend to $\inf f$, while the last $k$ tend to $\sup f$, so extending to the block case a well-known result due to Szegö. In the case the $A_{n,m}$'s are positive-definite, we study the asymptotic spectrum of $P_{n,m}^{-1}A_{n,m}$, where $P_{n,m}$ is a block Toeplitz preconditioner for the conjugate gradient method, applied to solve the system $A_{n,m}x=b$, obtaining strict estimates, when $n$ and $m$ are fixed, and exact limit values, when $n$ and $m$ tend to infinity, for both the condition number and the conjugate gradient convergence factor of the previous matrices. Extensions to the case of a deeper nesting level of the block structure are also discussed.

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 (1988), pp. 499-523. MR 88a:65037b
  • 2. J. R. Bunch, Stability of methods for solving Toeplitz systems of equations, SIAM J. Sci. Stat. Comp. 6 (1985), pp. 349-364. MR 87a:65073
  • 3. R. H. Chan, Toeplitz preconditioniers for Toeplitz systems wit nonnegative generating functions, IMA J. Numer. Anal. 11 (1991), pp. 333-345. MR 92f:65041
  • 4. R. H. Chan and X. Q. Jin, A family of block preconditioners for block systems, SIAM J. Sci. Stat. Comp. 13 (1992), pp. 1218-1235. MR 93e:65050
  • 5. F. Di Benedetto, G. Fiorentino and S. Serra, C.G. preconditioning for Toeplitz matrices, Comput. Math. Appl. 25 (1993), pp. 33-45. MR 93h:65063
  • 6. D. K. Faddeev and V. N. Faddeeva, Computational Methods of Linear Algebra, Freeman and Co., San Francisco, 1963. MR 28:1742
  • 7. H. Federer, Geometric Measure Theory, Springer-Verlag, New York, 1969. MR 41:1976
  • 8. G. H. Golub and C. F. Van Loan, Matrix Computation, The Johns Hopkins University Press, 1983. MR 85h:65063
  • 9. U. Grenander and G. Szegö, Toeplitz forms and their applications, Chelsea, New York, second edition, 1984. MR 88b:42031
  • 10. W. Hackbusch, Multigrid Methods and Applications, Springer Verlag, 1985. MR 87e:65082
  • 11. P. Halmos, Measure Theory, Springer Verlag, New York, 1974.
  • 12. M. R. Hestenes and E. Stiefel, Methods of conjugate gradients for solving linear systems, Nat. Bur. Standards, J. of Res. 49 (1952), pp. 409-436. MR 15:651a
  • 13. I. S. Iokhvidov, Hankel and Toeplitz forms: Algebraic Theory, Birkhäuser, Boston, 1982. MR 83k:15021
  • 14. S. Lang, Real and Functional Analysis, Springer-Verlag, third edition, 1993. MR 94b:00005
  • 15. S. Serra, Preconditioning strategies for asymptotically ill-conditioned block Toeplitz systems, BIT 34 (1994), pp. 579-594.
  • 16. G. Szegö, Orthogonal Polynomials, American Mathematical Society Colloquium Publications, 1939. MR 1:14b
  • 17. R. S. Varga, Matrix Iterative Analysis, Prentice-Hall, 1962. MR 28:1725

Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 65F15

Retrieve articles in all journals with MSC (1991): 65F15

Additional Information

Paolo Tilli
Affiliation: Scuola Normale Superiore, Piazza Cavalieri 7, 56100 Pisa, Italy

Keywords: Toeplitz matrix, eigenvalues, preconditioning, conjugate gradient
Received by editor(s): January 24, 1996
Dedicated: In loving memory of Ennio de Georgi
Article copyright: © Copyright 1997 American Mathematical Society

American Mathematical Society