Classical foundations of Toeplitz solvers
This thesis reviews the definition of Toeplitz matrices and discusses specific direct solvers for Toeplitz systems of equations. Direct solvers for a Toeplitz system of equations (Mx = b) can be considered as a two phase procedure: a factorization phase which determines the last column of M~l and a solution phase which computes M~lb. The focus of this thesis will be the solution phase (or second phase) of these solvers. We first present the connection between the classical theory of Szego polynomials and the inverse Cholesky factorization. This prominent association leads to the derivation and understanding of the Szego recursions and its equivalence to the Levinson-Durbin algorithm. In the factorization phase, the Levinson-Durbin algorithm is used to generate the coefficients of Szego polynomials for the last column of M~l. By performing direct multiplication of any arbitrary b with the coefficients of Szego polynomials, the Levinson algorithm is determined. The basics behind the factorization and solution phases is developed from the Christoffel-Darboux-Szego formula which is derived using the Szego recursions. The Christoffel-Darboux-Szego formula is used to derive Trench’s algorithm for constructing the M-1. The second part of the thesis examines the solution phase based on the Toeplitz inversion formulas given by Gohberg-Semencul and Ammar-Gader. The efficient implementation of the second phase relies on the use of fast Fourier transforms to evaluate cyclic convolutions. Some basic concepts of the fast Fourier transform and its use in the solution phase are described. The decomposition of the Toeplitz inversion formulas and the utilization of the properties of circulant matrices are combined with the techniques of fast Fourier transform to attain the solution for the second phase. This method of O(nlogn) is used for both fast and superfast algorithms.