A superfast solver for real symmetric Toeplitz systems using real trigonometric transformations
Gianni Codevico, Georg Heinig, Marc Van Barel · Numerical Linear Algebra with Applications · 2005
Abstract A new superfast O(n log2 n) 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. Copyright © 2005 John Wiley & Sons, Ltd.