Extreme eigenvalues of real symmetric Toeplitz matrices

Melman, A.

doi:10.1090/S0025-5718-00-01258-8

Extreme eigenvalues of real symmetric Toeplitz matrices
HTML articles powered by AMS MathViewer

by A. Melman;

Math. Comp. 70 (2001), 649-669

DOI: https://doi.org/10.1090/S0025-5718-00-01258-8

Published electronically: April 12, 2000

PDF | Request permission

Abstract:

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

Gregory S. Ammar and William B. Gragg, The generalized Schur algorithm for the superfast solution of Toeplitz systems, Rational approximation and applications in mathematics and physics (Łańcut, 1985) Lecture Notes in Math., vol. 1237, Springer, Berlin, 1987, pp. 315–330. MR 886705, DOI 10.1007/BFb0072474
Gregory S. Ammar and William B. Gragg, Numerical experience with a superfast real Toeplitz solver, Linear Algebra Appl. 121 (1989), 185–206. Linear algebra and applications (Valencia, 1987). MR 1011737, DOI 10.1016/0024-3795(89)90701-5
Alan L. Andrew, Eigenvectors of certain matrices, Linear Algebra Appl. 7 (1973), 151–162. MR 318179, DOI 10.1016/0024-3795(73)90049-9
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
Dunham Jackson, A class of orthogonal functions on plane curves, Ann. of Math. (2) 40 (1939), 521–532. MR 80, DOI 10.2307/1968936
A. Cantoni and P. Butler, Eigenvalues and eigenvectors of symmetric centrosymmetric matrices, Linear Algebra Appl. 13 (1976), no. 3, 275–288. MR 396614, DOI 10.1016/0024-3795(76)90101-4
J. J. M. Cuppen, A divide and conquer method for the symmetric tridiagonal eigenproblem, Numer. Math. 36 (1980/81), no. 2, 177–195. MR 611491, DOI 10.1007/BF01396757
George Cybenko, The numerical stability of the Levinson-Durbin algorithm for Toeplitz systems of equations, SIAM J. Sci. Statist. Comput. 1 (1980), no. 3, 303–319. MR 596026, DOI 10.1137/0901021
George Cybenko and Charles Van Loan, Computing the minimum eigenvalue of a symmetric positive definite Toeplitz matrix, SIAM J. Sci. Statist. Comput. 7 (1986), no. 1, 123–131. MR 819462, DOI 10.1137/0907009
P. Delsarte and Y. Genin, Spectral properties of finite Toeplitz matrices, Mathematical theory of networks and systems (Beer Sheva, 1983) Lect. Notes Control Inf. Sci., vol. 58, Springer, London, 1984, pp. 194–213. MR 792106, DOI 10.1007/BFb0031053
A. Dembo, Bounds on the extreme eigenvalues of positive-definite Toeplitz matrices, IEEE Trans. Inform. Theory 34 (1988), no. 2, 352–355. MR 945333, DOI 10.1109/18.2651
Durbin, J. (1960): The fitting of time series model. Rev. Inst. Int. Stat., 28, pp. 233–243.
Gene H. Golub, Some modified matrix eigenvalue problems, SIAM Rev. 15 (1973), 318–334. MR 329227, DOI 10.1137/1015032
Gene H. Golub and Charles F. Van Loan, Matrix computations, 2nd ed., Johns Hopkins Series in the Mathematical Sciences, vol. 3, Johns Hopkins University Press, Baltimore, MD, 1989. MR 1002570
David Hertz, Simple bounds on the extreme eigenvalues of Toeplitz matrices, IEEE Trans. Inform. Theory 38 (1992), no. 1, 175–176. MR 1146078, DOI 10.1109/18.108267
Yu Hen Hu and Sun Yuan Kung, Toeplitz eigensystem solver, IEEE Trans. Acoust. Speech Signal Process. 33 (1985), no. 5, 1264–1271. MR 811331, DOI 10.1109/TASSP.1985.1164672
Huang, D. (1992): Symmetric solutions and eigenvalue problems of Toeplitz systems. IEEE Trans. Signal Processing, 40, pp. 3069–3074.
Reinhold Baer, Groups with Abelian norm quotient group, Amer. J. Math. 61 (1939), 700–708. MR 34, DOI 10.2307/2371324
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
A. R. Collar, On the reciprocation of certain matrices, Proc. Roy. Soc. Edinburgh 59 (1939), 195–206. MR 8
Wolfgang Mackens and Heinrich Voss, The minimum eigenvalue of a symmetric positive-definite Toeplitz matrix and rational Hermitian interpolation, SIAM J. Matrix Anal. Appl. 18 (1997), no. 3, 521–534. MR 1453538, DOI 10.1137/S0895479895288851
A. Melman, A unifying convergence analysis of second-order methods for secular equations, Math. Comp. 66 (1997), no. 217, 333–344. MR 1370854, DOI 10.1090/S0025-5718-97-00787-4
A. Melman, Spectral functions for real symmetric Toeplitz matrices, J. Comput. Appl. Math. 98 (1998), no. 2, 233–243. MR 1657002, DOI 10.1016/S0377-0427(98)00129-0
David Slepian and Henry J. Landau, A note on the eigenvalues of Hermitian matrices, SIAM J. Math. Anal. 9 (1978), no. 2, 291–297. MR 466171, DOI 10.1137/0509020
William F. Trench, Numerical solution of the eigenvalue problem for Hermitian Toeplitz matrices, SIAM J. Matrix Anal. Appl. 10 (1989), no. 2, 135–146. MR 988625, DOI 10.1137/0610010
Heinrich Voss, Symmetric schemes for computing the minimum eigenvalue of a symmetric Toeplitz matrix, Linear Algebra Appl. 287 (1999), no. 1-3, 359–371. Special issue celebrating the 60th birthday of Ludwig Elsner. MR 1662878, DOI 10.1016/S0024-3795(98)10147-7