Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
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
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?)


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: http://dx.doi.org/10.1090/S0025-5718-05-01796-5
PII: S 0025-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