Fast inversion of triangular Toeplitz matrices

In this paper, we present an approximate inversion method for triangular Toeplitz matrices based on trigonometric polynomial interpolation. To obtain an approximate inverse of high accuracy for a triangular Toeplitz matrix of size , our algorithm requires two fast Fourier transforms (FFTs) and one fast cosine transform of 2-vectors. We then revise the approximate method proposed by Bini (SIAM J. Comput. 13 (1984) 268). The complexity of the revised Bini algorithm is two FFTs of 2-vectors.