Extreme eigenvalues of real symmetric Toeplitz matrices
HTML articles powered by AMS MathViewer
- by A. Melman PDF
- Math. Comp. 70 (2001), 649-669 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
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
- MR Author ID: 293268
- Email: melman@sccm.stanford.edu
- Received by editor(s): September 22, 1998
- Received by editor(s) in revised form: May 24, 1999
- Published electronically: April 12, 2000
- © Copyright 2000 American Mathematical Society
- Journal: Math. Comp. 70 (2001), 649-669
- MSC (2000): Primary 65F15, 15A18
- DOI: https://doi.org/10.1090/S0025-5718-00-01258-8
- MathSciNet review: 1813143