|
Extreme eigenvalues of real symmetric Toeplitz matrices
Author(s):
A.
Melman.
Journal:
Math. Comp.
70
(2001),
649-669.
MSC (2000):
Primary 65F15, 15A18
Posted:
April 12, 2000
Retrieve article in:
PDF
This article is available free of charge
Abstract |
References |
Similar articles |
Additional information
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:
- 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
Email:
melman@sccm.stanford.edu
DOI:
10.1090/S0025-5718-00-01258-8
PII:
S 0025-5718(00)01258-8
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
Posted:
April 12, 2000
Copyright of article:
Copyright
2000,
American Mathematical Society
|
Comments: webmaster@ams.org