Superfast algorithms for solving Toeplitz systems of equations
We describe a method for solving a linear system of equations Mx = y, where M is an n X n Toeplitz matrix, which takes 0(n log² n) arithmetic operations. The algorithm discussed in this thesis is based on the method developed independently by de Hoog and Musicus. We show that when M is (Hermitian) positive definite the algorithm reduces to the Generalized Schur algorithm as discussed by Ammar and Gragg. Finally, since the above algorithms require n to be a power of 2, we show how this constraint can be relaxed to include other values of n for the positive definite case.