In this paper, we consider solving real triangular Toeplitz systems Tn[f] x = b, where the generating function f is complex valued and 2p-periodic. We will show how to obtain an accurate approximation of 1/f by the interpolation technique and prove that if f is continue and without zero point, then for sufficiently large n, the inverse of Tn[f] can be obtained with one FFT and one DCT of vectors of length n. We also consider the case where f has zero points. Numerical results are shown to illustrate the efficiency of the method.
1 Work supported by the Natural Science Foundation of China # 19901017.