TW386

G. Codevico, G. Heinig, M. Van Barel
A Superfast Solver for Real Symmetric Toeplitz Systems Using Real Trigonometric Transformations

Abstract

A new superfast $O(n\log^2n)$ complexity direct solver for real symmetric Toeplitz systems is presented. The algorithm is based on 1. the reduction to symmetric right-hand sides, 2. a polynomial interpretation in terms of Chebyshev polynomials, 3. an inversion formula involving real trigonometric transformations, and 4. an interpretation of the equations as a tangential interpolation problem. The tangential interpolation problem is solved via a divide-and-conquer strategy and fast DCT.