Fast inversion of Hankel and Toeplitz matrices (Q1186587)

A computational algorithm for the inversion of Hankel and Toeplitz matrices is presented. The main goal of this note is to bring out the intimate connection between the Euclidean scheme and the inversion of Toeplitz and Hankel matrices without references to the Padé tables. The algorithm proposed here requires \(O(n\log^ 2n)\) arithmetic operations. Moreover, it is shown that the inversion of a Toeplitz matrix in both lower and upper Hessenberg form can be computed effectively by a sequential algorithm by \(n^ 2/2+5n/2\) multiplications and \(n^ 2/2+3n/2\) additions.