Fast inversion of triangular Toeplitz matrices

作者：Lin FR^*; Ching WK; Ng MK

来源：Theoretical Computer Science, 2004, 315(2-3): 511-523.

DOI：10.1016/j.tcs.2004.01.005

• triangular Toeplitz matrix
• interpolation
• fast Fourier transform
• fast cosine transform

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 n, our algorithm requires two fast Fourier transforms (FFTs) and one fast cosine transform of 2n-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 2n-vectors.

• 出版日期2004-5-6
• 单位汕头大学