The Levinson recurrence and fast algorithms for solving Toeplitz systems of linear equations

This work brings together classical polynomial theory as it relates to the Levinson recurrence for a Hermitian Toeplitz operator and matrix theory as it relates to the class of Hermitian centro-Hermitian matrices. A new computationally efficient alternative is presented to the Levinson recurrence on either the Hermitian or skew-Hermitian polynomial spaces. This approach also leads to an entirely new algorithm for solving systems of linear equations when the coefficient matrix is Hermitian Toeplitz or real symmetric Toeplitz. Analysis of the computational complexity of the algorithms presented is also performed, and it is shown that these algorithms lead to significant improvements in the computational complexity as compared to the previously best-known recursive algorithms. They also provide further insight into the mathematical properties of the structurally rich Toeplitz matrices.