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 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.**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**

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