Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Extreme eigenvalues of real symmetric Toeplitz matrices

Author: A. Melman
Journal: Math. Comp. 70 (2001), 649-669
MSC (2000): Primary 65F15, 15A18
Published electronically: April 12, 2000
MathSciNet review: 1813143
Full-text PDF

Abstract | References | Similar Articles | Additional Information


We exploit the even and odd spectrum of real symmetric Toeplitz matrices for the computation of their extreme eigenvalues, which are obtained as the solutions of spectral, or secular, equations. We also present a concise convergence analysis for a method to solve these spectral equations, along with an efficient stopping rule, an error analysis, and extensive numerical results.

References [Enhancements On Off] (What's this?)

  • 1. Ammar, G.S. and Gragg, W.B. (1987): The generalized Schur algorithm for the superfast solution of Toeplitz systems.
    In Rational Approximations and its Applications in Mathematics and Physics, J. Gilewicz, M. Pindor and W. Siemaszko, eds., Lecture Notes in Mathematics 1237, Springer-Verlag, Berlin, pp. 315-330. MR 88c:65032
  • 2. Ammar, G.S. and Gragg, W.B. (1989): Numerical experience with a superfast Toeplitz solver.
    Linear Algebra Appl., 121, pp. 185-206. MR 90g:65030
  • 3. Andrew, A.L. (1973): Eigenvectors of certain matrices.
    Linear Algebra Appl., 7, pp. 151-162. MR 47:6726
  • 4. Bunch, J.R. (1985): Stability of methods for solving Toeplitz systems of equations.
    SIAM J. Sci. Stat. Comput., 6, pp. 349-364. MR 87a:65073
  • 5. Bunch, J.R., Nielsen, C.P., Sorensen, D.C. (1978): Rank-one modification of the symmetric eigenproblem.
    Numer. Math. 31, pp. 31-48. MR 80g:65038
  • 6. Cantoni, A. and Butler, F. (1976): Eigenvalues and eigenvectors of symmetric centrosymmetric matrices.
    Linear Algebra Appl., 13, pp. 275-288. MR 53:476
  • 7. Cuppen, J.J.M. (1981): A divide and conquer method for the symmetric tridiagonal eigenvalue problem.
    Numer. Math., 36, pp. 177-195. MR 82d:65038
  • 8. Cybenko, G. (1980): The numerical stability of the Levinson-Durbin algortihm for Toeplitz systems of equations.
    SIAM J. Sci. Stat. Comput., 1, pp. 303-319. MR 82i:65019
  • 9. Cybenko, G. and Van Loan, C.(1986): Computing the minimum eigenvalue of a symmetric positive definite Toeplitz matrix.
    SIAM J. Sci. Stat. Comput., 7, pp. 123-131. MR 87b:65042
  • 10. Delsarte, P. and Genin, Y (1983): Spectral properties of finite Toeplitz matrices.
    In Mathematical Theory of Networks and Systems, Proc. MTNS-83 International Symposium, Beer-Sheva, Israel, Lecture Notes in Computer Sci., vol. 58, Springer-Verlag, Berlin, pp. 194-213. MR 86k:15003
  • 11. Dembo, A. (1988): Bounds on the extreme eigenvalues of positive definite Toeplitz matrices.
    IEEE Trans. Inform. Theory, 34, pp. 352-355. MR 89b:15028
  • 12. Durbin, J. (1960): The fitting of time series model.
    Rev. Inst. Int. Stat., 28, pp. 233-243.
  • 13. Golub, G.H. (1973): Some modified matrix eigenvalue problems.
    SIAM Rev., 15, pp. 318-334. MR 48:7569
  • 14. Golub, G. and Van Loan, C. (1989): Matrix Computations.
    The Johns Hopkins University Press, Baltimore and London. MR 90d:65055
  • 15. Hertz, D. (1992): Simple bounds on the extreme eigenvalues of Toeplitz matrices.
    IEEE Trans. Inform. Theory, 38, pp. 175-176. MR 92j:15005
  • 16. Hu, Y.H. and Kung, S.Y. (1985) A Toeplitz eigensystem solver.
    IEEE Trans. Acoust. Speech Signal Process., 34, pp. 1264-1271. MR 87f:65044
  • 17. Huang, D. (1992): Symmetric solutions and eigenvalue problems of Toeplitz systems.
    IEEE Trans. Signal Processing, 40, pp. 3069-3074.
  • 18. Isaacson, E. and Keller, H.B. (1994): Analysis of Numerical Methods.
    Dover Publications, Inc., New York. CMP 94:14; MR 34:924 (original ed.)
  • 19. Kac, M., Murdock, W.L. and Szegö, G. (1953): On the eigenvalues of certain Hermitian forms. J. Rat. Mech. Anal., 2, pp. 767-800. MR 15:538b
  • 20. Levinson, N. (1947): The Wiener RMS (root mean square) error criterion in filter design and prediction.
    J. Math. and Phys., 25, pp. 261-278. MR 8:391e
  • 21. Mackens, W. and Voss, H. (1997): The minimum eigenvalue of a symmetric positive-definite Toeplitz matrix and rational Hermitian interpolation.
    SIAM J. Matrix Anal. Appl., 18, pp. 521-534. MR 98e:65029
  • 22. Melman, A. (1997): A unifying convergence analysis of second-order methods for secular equations.
    Math. Comp., 66, pp. 333-344. MR 97e:65036
  • 23. Melman, A. (1998): Spectral functions for real symmetric Toeplitz matrices.
    J. Comput. Appl. Math., 98, pp. 233-243. MR 99i:65036
  • 24. Slepian, D. and Landau, H.J. (1978): A note on the eigenvalues of Hermitian matrices.
    SIAM J. Math. Anal., 9, pp. 291-297. MR 57:6052
  • 25. Trench, W.F. (1989): Numerical solution of the eigenvalue problem for Hermitian Toeplitz matrices.
    SIAM J. Matrix Anal. Appl., 10, pp. 135-146. MR 90i:65068
  • 26. Voss, H. (1999): Symmetric schemes for computing the minimum eigenvalue of a symmetric Toeplitz matrix.
    Linear Algebra Appl., 287, pp. 359-371. MR 99m:65073

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 65F15, 15A18

Retrieve articles in all journals with MSC (2000): 65F15, 15A18

Additional Information

A. Melman
Affiliation: Ben-Gurion University, Beer-Sheva, Israel
Address at time of publication: Department of Computer Science, SCCM Program, Stanford University, Stanford, California 94305-9025

Keywords: Toeplitz matrix, extreme eigenvalues, odd and even spectra, spectral equation, secular equation, rational approximation
Received by editor(s): September 22, 1998
Received by editor(s) in revised form: May 24, 1999
Published electronically: April 12, 2000
Article copyright: © Copyright 2000 American Mathematical Society

American Mathematical Society