Computation of the Newton step for the even and odd characteristic polynomials of a symmetric positive definite Toeplitz matrix
HTML articles powered by AMS MathViewer
- by A. Melman;
- Math. Comp. 75 (2006), 817-832
- DOI: https://doi.org/10.1090/S0025-5718-05-01796-5
- Published electronically: December 1, 2005
- PDF | Request permission
Abstract:
We compute the Newton step for the characteristic polynomial and for the even and odd characteristic polynomials of a symmetric positive definite Toeplitz matrix as the reciprocal of the trace of an appropriate matrix. We show that, after the Yule–Walker equations are solved, this trace can be computed in ${\mathcal O}(n)$ additional arithmetic operations, which is in contrast to existing methods, which rely on a recursion, requiring ${\mathcal O}(n^2)$ additional arithmetic operations.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
- 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
- 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
- Philippe Delsarte and Yves V. Genin, The split Levinson algorithm, IEEE Trans. Acoust. Speech Signal Process. 34 (1986), no. 3, 470–478. MR 844658, DOI 10.1109/TASSP.1986.1164830
- Durbin, J. (1960): The fitting of time series model. Rev. Inst. Int. Stat., 28, pp. 233–243.
- I. C. Gohberg and A. A. Semencul, The inversion of finite Toeplitz matrices and their continual analogues, Mat. Issled. 7 (1972), no. 2(24), 201–223, 290 (Russian). MR 353038
- Gene H. Golub and Charles F. Van Loan, Matrix computations, 3rd ed., Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 1996. MR 1417720
- Wolfgang Mackens and Heinrich Voss, Computing the minimum eigenvalue of a symmetric positive definite Toeplitz matrix by Newton-type methods, SIAM J. Sci. Comput. 21 (1999/00), no. 4, 1650–1656. MR 1756049, DOI 10.1137/S1064827598342195
- Nicola Mastronardi and Daniel Boley, Computing the smallest eigenpair of a symmetric positive definite Toeplitz matrix, SIAM J. Sci. Comput. 20 (1999), no. 5, 1921–1927. MR 1694690, DOI 10.1137/S106482759732229X
- A. Melman, Extreme eigenvalues of real symmetric Toeplitz matrices, Math. Comp. 70 (2001), no. 234, 649–669. MR 1813143, DOI 10.1090/S0025-5718-00-01258-8
- A. Melman, A two-step even-odd split Levinson algorithm for Toeplitz systems, Linear Algebra Appl. 338 (2001), 219–237. MR 1861123, DOI 10.1016/S0024-3795(01)00386-X
- A. Melman, Computation of the smallest even and odd eigenvalues of a symmetric positive-definite Toeplitz matrix, SIAM J. Matrix Anal. Appl. 25 (2004), no. 4, 947–963. MR 2081125, DOI 10.1137/S0895479803423354
Bibliographic Information
- A. Melman
- Affiliation: Department of Applied Mathematics, School of Engineering, Santa Clara University, Santa Clara, California 95053
- MR Author ID: 293268
- Email: amelman@scu.edu
- Received by editor(s): April 29, 2004
- Received by editor(s) in revised form: November 11, 2004
- Published electronically: December 1, 2005
- © Copyright 2005 American Mathematical Society
- Journal: Math. Comp. 75 (2006), 817-832
- MSC (2000): Primary 65F15; Secondary 15A18
- DOI: https://doi.org/10.1090/S0025-5718-05-01796-5
- MathSciNet review: 2196993