Asymptotically fast solution of Toeplitz and related systems of linear equations. (English) Zbl 0458.65018


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


[1] Makhoul, J., Digital Signal Processing II (IEEE ASSP Soc. Ed.) (1976), IEEE Press: IEEE Press New York
[2] Gohberg, I. C.; Fel’dman, 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) · Zbl 0278.45008
[3] Kailath, T.; Vieira, A.; Morf, M., Inverses of Toeplitz operators, innovations and orthogonal polynomials, SIAM Rev., 20, 1, 106-119 (1978) · Zbl 0382.47013
[4] Wiener, N., Extrapolation, Interpolation and Smoothing of Stationary Time Series (1949), MIT Press: MIT Press Cambridge, Mass, Appendix B · Zbl 0036.09705
[5] Trench, W. F., An algorithm for the inversion of finite Toeplitz matrices, J. SIAM, 12, 515-522 (1964) · Zbl 0131.36002
[6] Zohar, S., The algorithm of W.F. Trench, J. Assoc. Comput. Mach., 16, 592-601 (1969) · Zbl 0194.18102
[7] Akaike, H., Block Toeplitz matrix inversion, SIAM J. Appl. Math., 24, 234-241 (1973) · Zbl 0251.65024
[8] Brent, R. P.; Gustavson, F. G.; Yun, D. Y.Y., Fast computation of Padé approximants and the solution of Toeplitz systems of equations, (Research Report RC 8173(#34952) (1980), IBM Research Center: IBM Research Center Yorktown Heights, NY) · Zbl 0475.65018
[9] Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., The Design and Analysis of Computer Algorithms (1974), Addison-Wesley: Addison-Wesley Reading, Mass · Zbl 0286.68029
[10] Morf, M.; Kailath, T., Recent results in least-squares estimation theory, Ann. Econ. and Soc. Meas., 6, 3, 261-274 (1977)
[11] Friedlander, B.; Morf, M.; Kailath, T.; Ljung, L., New inversion formulas for matrices classified in terms of their distance from Toeplitz matrices, Linear Algebra and Appl., 27, 31-60 (1979) · Zbl 0414.15005
[12] Kailath, T.; Kung, S.-Y.; Morf, M., Displacement ranks of matrices and linear equations, J. Math. Anal. Appl., 68, 2, 395-407 (1979) · Zbl 0433.15001
[13] Friedlander, B.; Kailath, T.; Morf, M.; Ljung, L., Extended Levinson and Chandrasekhar equations for general discrete-time linear estimation problems, IEEE Trans. Automatic Control, AC-23, 4, 653-659 (1978) · Zbl 0381.93044
[14] Dickinson, B. W., Efficient solution of linear equations with banded Toeplitz matrices, IEEE Trans. Acoust. Speech and Sig. Proc., ASSP-27, 4, 421-423 (1979) · Zbl 0434.65011
[15] Dickinson, B. W., Solution of linear equations with rational Toeplitz matrices, Math. Comp., 34, 227-233 (1980) · Zbl 0424.65007
[16] Ljung, S.; Ljung, L., Fast numerical solution of integral equations with stationary kernels, (Report LiTH-ISY-I-0200 (1978), Dept. of Electrical Engineering, Linköping Univ: Dept. of Electrical Engineering, Linköping Univ Sweden) · Zbl 0477.65091
[17] Gohberg, I. C.; Heinig, G., Inversion of finite Toeplitz matrices with entries from a noncommutative algebra, Rev. Roumaine Math. Pures Appl., 19, 5, 623-665 (1974)
[18] Bitmead, R. R.; Kung, S.-Y.; Anderson, B. D.O.; Kailath, T., Greatest common divisors via generalized Sylvester and Bezout matrices, IEEE Trans. Automatic Control, AC-23, 6, 1043-1047 (1978) · Zbl 0389.93008
[19] Jain, A. K., Fast inversion of banded Toeplitz matrices by circular decompositions, IEEE Trans. Acoust. Speech and Sig. Proc., ASSP-26, 2, 121-126 (1978) · Zbl 0429.65026
[20] Gohberg, I. C.; Semencul, A. A., On the inversion of finite Toeplitz matrices and their continuous analogs, Mat. Issled., 2, 201-233 (1972), (in Russian) · Zbl 0288.15004
[21] Chin, F.; Steiglitz, K., Discrete Szegö polynomials and an \(O(N\) log \(N)\) algorithm for error evaluation, Proceedings of the 12th Allerton Conference on Circuits and Systems, 120-129 (1975)
[22] Cybenko, G., Round-off error propagation in Durbin’s, Levinson’s, and Trench’s algorithms, Proceedings of the International Conference on Acoustics, Speech and Signal Processing (1979), Washington, D.C.
[23] Tewarson, R. P., Sparse Matrices (1972), Academic: Academic New York · Zbl 0234.65038
[24] Gustavson, F. G.; Yun, D. Y.Y., Fast algorithms for rational Hermite approximation and solution of Toeplitz systems, IEEE Trans. Circuits and Systems, CAS-26, 9, 750-755 (1979) · Zbl 0416.65008
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.