Doubling algorithms for Toeplitz and related equations
- 24 March 2005
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 5, 954-959
- https://doi.org/10.1109/icassp.1980.1171074
Abstract
A new class of doubling or halving algorithms for solving Toeplitz and related equations is presented. For scalar n by n Toeplitz matrices, they requireO(n \log^{2}n)computations, similarly to the HGCD (half-greatest-common-divisor) based algorithm of Gustavson and Yun. However, these new algorithms are based on the notions of "shift" or displacement rank1 \leq \alpha \leq n, an index of how close a matrix is to being Toeplitz, requiringO(\alpha^{d} n \log^{2}n)operations, (d \leq 2). A basic version of a doubling algorithm for such "α-Toeplitz matrices" is presented, and the applications of these results to related problems are mentioned, such as the inversion of banded-, block- and Hankel matrices.Keywords
This publication has 9 references indexed in Scilit:
- Recursive square-root ladder estimation algorithmsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Arithmetic Complexity of ComputationsPublished by Society for Industrial & Applied Mathematics (SIAM) ,1980
- Square-root algorithms for parallel processing in optimal estimationAutomatica, 1979
- Displacement ranks of matrices and linear equationsJournal of Mathematical Analysis and Applications, 1979
- Fast inversion of banded Toeplitz matrices by circular decompositionsIEEE Transactions on Acoustics, Speech, and Signal Processing, 1978
- On Computing the Discrete Fourier TransformMathematics of Computation, 1978
- Direct Methods for Solving Symmetric Indefinite Systems of Linear EquationsSIAM Journal on Numerical Analysis, 1971
- Shift-register synthesis and BCH decodingIEEE Transactions on Information Theory, 1969
- The Wiener (Root Mean Square) Error Criterion in Filter Design and PredictionJournal of Mathematics and Physics, 1946