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

Melman, A.

doi:10.1090/S0025-5718-05-01796-5

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 PDF

Math. Comp. 75 (2006), 817-832 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 0353038
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