Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

Computation of the Newton step for the even and odd characteristic polynomials of a symmetric positive definite Toeplitz matrix


Author: A. Melman
Journal: Math. Comp. 75 (2006), 817-832
MSC (2000): Primary 65F15; Secondary 15A18
DOI: https://doi.org/10.1090/S0025-5718-05-01796-5
Published electronically: December 1, 2005
MathSciNet review: 2196993
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [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, Berlin, pp. 315-330. MR 0886705 (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 1011737 (90g:65030)
  • 3. Cantoni, A. and Butler, F. (1976): Eigenvalues and eigenvectors of symmetric centrosymmetric matrices.
    Linear Algebra Appl., 13, pp. 275-288. MR 0396614 (53:476)
  • 4. Cybenko, G. and Van Loan, C. (1986): Computing the minimum eigenvalue of a symmetric positive definite Toeplitz matrix. SIAM J. Sci. Stat. Comput., Vol. 7, No. 1, pp. 123-131. MR 0819462 (87b:65042)
  • 5. 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, pp. 194-213. MR 0792106 (86k:15003)
  • 6. Delsarte, P. and Genin, Y. (1986): The split Levinson algorithm.
    IEEE Trans. Acoust. Speech, Signal Processing, ASSP-34, pp. 470-478.MR 0844658 (87f:94007)
  • 7. Durbin, J. (1960): The fitting of time series model.
    Rev. Inst. Int. Stat., 28, pp. 233-243.
  • 8. Gohberg, I.C. and Semencul, A.A. (1972): The inversion of finite Toeplitz matrices and their continual analogues. (Russian)
    Mat. Issled. 7 (1972), No. 2(24), 201-223. MR 0353038 (50:5524)
  • 9. Golub, G. and Van Loan, C. (1996): Matrix Computations.
    The Johns Hopkins University Press, Baltimore and London. MR 1417720 (97g:65006)
  • 10. Mackens, W. and Voss, H. (2000): Computing the minimum eigenvalue of a symmetric positive definite Toeplitz matrix by Newton-type methods.
    SIAM J. Sci. Comput., Vol. 21, no. 4, 1650-1656. MR 1756049 (2001g:65043)
  • 11. Mastronardi, N. and Boley, D. (1999): Computing the smallest eigenpair of a symmetric positive definite Toeplitz matrix.
    SIAM J. Sci. Comput., Vol. 20, No. 5, pp. 1921-1927. MR 1694690 (2000b:65066)
  • 12. Melman, A. (2000): Extreme eigenvalues of real symmetric Toeplitz matrices.
    Math. Comp., 70, No. 234, pp. 649-669. MR 1813143 (2002b:65059)
  • 13. Melman, A. (2001): A two-step even-odd split Levinson algorithm for Toeplitz systems.
    Linear Algebra Appl., 338, pp. 219-237. MR 1861123 (2002h:65034)
  • 14. Melman, A. (2004): Computation of the smallest even and odd eigenvalues of a symmetric positive definite Toeplitz matrix.
    SIAM J. Matrix Anal. Appl., Vol. 25, No. 4, pp. 947-963. MR 2081125

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: Department of Applied Mathematics, School of Engineering, Santa Clara University, Santa Clara, California 95053
Email: amelman@scu.edu

DOI: https://doi.org/10.1090/S0025-5718-05-01796-5
Keywords: Toeplitz matrix, even, odd, eigenvalue, characteristic polynomial, Newton's method
Received by editor(s): April 29, 2004
Received by editor(s) in revised form: November 11, 2004
Published electronically: December 1, 2005
Article copyright: © Copyright 2005 American Mathematical Society

American Mathematical Society