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

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 additional arithmetic operations, which is in contrast to existing methods, which rely on a recursion, requiring additional arithmetic operations.

**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.**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**, https://doi.org/10.1016/0024-3795(89)90701-5**3.**A. Cantoni and P. Butler,*Eigenvalues and eigenvectors of symmetric centrosymmetric matrices*, Linear Algebra and Appl.**13**(1976), no. 3, 275–288. MR**0396614****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.**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**0353038****9.**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****10.**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**, https://doi.org/10.1137/S1064827598342195**11.**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**, https://doi.org/10.1137/S106482759732229X**12.**A. Melman,*Extreme eigenvalues of real symmetric Toeplitz matrices*, Math. Comp.**70**(2001), no. 234, 649–669. MR**1813143**, https://doi.org/10.1090/S0025-5718-00-01258-8**13.**A. Melman,*A two-step even-odd split Levinson algorithm for Toeplitz systems*, Linear Algebra Appl.**338**(2001), 219–237. MR**1861123**, https://doi.org/10.1016/S0024-3795(01)00386-X**14.**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**, https://doi.org/10.1137/S0895479803423354

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