On the asymptotic spectrum of Hermitian block Toeplitz matrices with Toeplitz blocks
HTML articles powered by AMS MathViewer
- by Paolo Tilli PDF
- Math. Comp. 66 (1997), 1147-1159 Request permission
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
- 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
- James R. Bunch, Stability of methods for solving Toeplitz systems of equations, SIAM J. Sci. Statist. Comput. 6 (1985), no. 2, 349–364. MR 779410, DOI 10.1137/0906025
- Raymond H. Chan, Toeplitz preconditioners for Toeplitz systems with nonnegative generating functions, IMA J. Numer. Anal. 11 (1991), no. 3, 333–345. MR 1118960, DOI 10.1093/imanum/11.3.333
- Raymond H. Chan and Xiao-Qing Jin, A family of block preconditioners for block systems, SIAM J. Sci. Statist. Comput. 13 (1992), no. 5, 1218–1235. MR 1177806, DOI 10.1137/0913070
- Fabio Di Benedetto, Giuseppe Fiorentino, and Stefano Serra, CG preconditioning for Toeplitz matrices, Comput. Math. Appl. 25 (1993), no. 6, 35–45. MR 1201877, DOI 10.1016/0898-1221(93)90297-9
- D. K. Faddeev and V. N. Faddeeva, Computational methods of linear algebra, W. H. Freeman and Co., San Francisco-London, 1963. Translated by Robert C. Williams. MR 0158519
- Herbert Federer, Geometric measure theory, Die Grundlehren der mathematischen Wissenschaften, Band 153, Springer-Verlag New York, Inc., New York, 1969. MR 0257325
- Gene H. Golub and Charles F. Van Loan, Matrix computations, Johns Hopkins Series in the Mathematical Sciences, vol. 3, Johns Hopkins University Press, Baltimore, MD, 1983. MR 733103
- Ulf Grenander and Gábor Szegő, Toeplitz forms and their applications, 2nd ed., Chelsea Publishing Co., New York, 1984. MR 890515
- Wolfgang Hackbusch, Multigrid methods and applications, Springer Series in Computational Mathematics, vol. 4, Springer-Verlag, Berlin, 1985. MR 814495, DOI 10.1007/978-3-662-02427-0
- P. Halmos, Measure Theory, Springer Verlag, New York, 1974.
- Sam Perlis, Maximal orders in rational cyclic algebras of composite degree, Trans. Amer. Math. Soc. 46 (1939), 82–96. MR 15, DOI 10.1090/S0002-9947-1939-0000015-X
- I. S. Iohvidov, Hankel and Toeplitz matrices and forms, Birkhäuser, Boston, Mass., 1982. Algebraic theory; Translated from the Russian by G. Philip A. Thijsse; With an introduction by I. Gohberg. MR 677503
- Serge Lang, Real and functional analysis, 3rd ed., Graduate Texts in Mathematics, vol. 142, Springer-Verlag, New York, 1993. MR 1216137, DOI 10.1007/978-1-4612-0897-6
- S. Serra, Preconditioning strategies for asymptotically ill-conditioned block Toeplitz systems, BIT 34 (1994), pp. 579–594.
- T. Venkatarayudu, The $7$-$15$ problem, Proc. Indian Acad. Sci., Sect. A. 9 (1939), 531. MR 0000001, DOI 10.1090/gsm/058
- Richard S. Varga, Matrix iterative analysis, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1962. MR 0158502
Additional Information
- Paolo Tilli
- Affiliation: Scuola Normale Superiore, Piazza Cavalieri 7, 56100 Pisa, Italy
- Email: tilli@cibs.sns.it
- Received by editor(s): January 24, 1996
- © Copyright 1997 American Mathematical Society
- Journal: Math. Comp. 66 (1997), 1147-1159
- MSC (1991): Primary 65F15
- DOI: https://doi.org/10.1090/S0025-5718-97-00840-5
- MathSciNet review: 1408378
Dedicated: In loving memory of Ennio de Georgi