A fast algorithm for the inversion of general Toeplitz matrices

We propose a “fast” algorithm for the construction of a data-sparse inverse of a generalToeplitz matrix. The computational cost for inverting an N × N Toeplitz matrix equals the cost of four length-N FFTs plus an O(N)-term. This cost should be compared to the O(N log2 N) cost of previously published methods. Moreover, while those earlier methods are based on algebraic considerations, the procedure of this paper is analysis-based; as a result, its stability does not depend on the symmetry and positive-definiteness of the matrix being inverted. The performance of the scheme is illustrated with numerical examples.