Numerical Linear Algebra With Applications vol:12 issue:8 pages:699-713
A new superfast O(n log(2) n) complexity direct solver for real symmetric Toeplitz systems is presented. The algorithm is based on 1. the reduction to symmetric right-band 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 (c) 2005 John Wiley & Sons, Ltd.