A fast algorithm for solving a Toeplitz system of equations

A fast algorithm for the solution of a Toeplitz system of equations is presented. The algorithm requires order <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N(log N)²</tex> computations where N is the number of equations. For banded Toeplitz matrices the order of computations is reduced to only <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N log N + m(log m)²</tex> where 2m is the maximum number of nonzero principal subdiagonals of the Toeplitz matrix. The algorithm is in essence a fast implementation of the Trench algorithm in reverse. Thus, the algorithm involves imbedding of the given matrix in a cyclic matrix and a fast HD (half-divisor) algorithm to compute the first row of the inverse matrix. The desired solution is then obtained directly from the first row by applying fast Fourier transform techniques in order <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N log N</tex> computations. Finally, the extension of the algorithm to block Toeplitz matrices is also presented.