×
de Hoog, Frank

A new algorithm for solving Toeplitz systems of equations. (English) Zbl 0621.65014

Linear Algebra Appl. 88-89, 123-138 (1987).
Some recurrences that are the basis for a new method to invert an \(n\times n\) Toeplitz system of linear equations with \(O(n\cdot \log^ 2n)\) are presented. Numerical exmples are not given.
Reviewer: S.Filippi

Cited in 1 Review
Cited in 43 Documents

MSC:

65F05 Direct numerical methods for linear systems and matrix inversion
68Q25 Analysis of algorithms and problem complexity

Keywords:

computational complexity; inversion of Toeplitz matrices; recurrences; Toeplitz system
PDF BibTeX XML Cite
\textit{F. de Hoog}, Linear Algebra Appl. 88--89, 123--138 (1987; Zbl 0621.65014)
Full Text: DOI

References:

[1] Bareiss, E. H., Numerical solution of linear equations with Toeplitz and vector Toeplitz matrices, Numer. Math., 13, 404-424 (1969) · Zbl 0174.20401
[3] Bitmead, R. R.; Anderson, B. D.O., Asymptotically fast solutions of Toeplitz and related systems of linear equations, Linear Algebra Appl., 34, 103-116 (1980) · Zbl 0458.65018
[4] Brent, R. P.; Gustavson, F. G.; Yun, D. Y.Y., Fast solutions of Toeplitz systems of equations and computation of Pade approximants, J. Algorithms, 1, 259-295 (1980) · Zbl 0475.65018
[5] Cybenko, G., The numerical stability of the Levinson-Durbin algorithm for Toeplitz systems of equations, SIAM J. Sci. Statist. Comput., 1, 303-319 (1980) · Zbl 0474.65026
[6] Friedlander, B.; Morf, M.; Kailath, T.; Ljung, L., New inversion formulas for matrices classified in terms of their distance from Toeplitz matrices, Linear Algebra Appl., 27, 31-60 (1979) · Zbl 0414.15005
[7] Gohberg, L. C.; Feldman, I. A., Convolution Equations and Projection Methods for their Solution, (Translations of Mathematical Monographs, Vol. 41 (1974), Amer. Math. Soc: Amer. Math. Soc Providence, R.I)
[8] Gohberg, I. C.; Semencul, A. A., On the inversion of finite Toeplitz matrices and their continuous analogs, Mat. Issled., 2, 201-233 (1972) · Zbl 0288.15004
[9] Jain, A. K., An efficient algorithm for a large Toeplitz set of linear equations, IEEE Trans. Acoust. Speech Signal Process, 27, 612-615 (1979)
[10] Kailath, T.; Kung, S. Y.; Morf, M., Displacement ranks of matrices and linear equations, J. Math. Anal. Appl., 68, 395-407 (1979) · Zbl 0433.15001
[11] Kailath, T.; Viera, A.; Morf, M., Inverses of Toeplitz operators, innovations and orthogonal polynomials, SIAM Rev., 20, 106-119 (1978) · Zbl 0382.47013
[12] Levinson, N., The Wiener RMS error criterion in filter design and prediction, J. Math. Phys., 25, 261-278 (1947)
[13] Morf, M., Doubling algorithms for Toeplitz and related equations, Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing, 954-959 (1980), Denver
[14] Sexton, H., An analysis of an algorithm of Bitmead and Anderson for the inversion of Toeplitz systems, Naval Oceans Systems Center Technical Report No. 756 (1982)
[15] Sweet, D. R., Numerical methods for Toeplitz matrices, (Ph.D. Thesis (1982), Dept. of Computing Science, Univ. of Adelaide) · Zbl 0504.65017
[16] Trench, W., An algorithm for the inversion of finite Toeplitz matrices, J. Soc. Indust. Appl. Math., 12, 512-522 (1966)
[17] Zohar, S., The algorithm of W.F. Trench, J. Assoc. Comput. Mach., 16, 592-601 (1969) · Zbl 0194.18102
[18] Zohar, S., The solution of a Toeplitz set of linear equations, J. Assoc. Comput. Mach., 21, 272-276 (1974) · Zbl 0276.65014
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.