Premium
A superfast solver for real symmetric Toeplitz systems using real trigonometric transformations
Author(s) -
Codevico G.,
Heinig G.,
Van Barel M.
Publication year - 2005
Publication title -
numerical linear algebra with applications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.02
H-Index - 53
eISSN - 1099-1506
pISSN - 1070-5325
DOI - 10.1002/nla.445
Subject(s) - toeplitz matrix , mathematics , solver , trigonometric interpolation , trigonometry , interpolation (computer graphics) , chebyshev polynomials , interpretation (philosophy) , trigonometric polynomial , inversion (geology) , polynomial , algorithm , polynomial interpolation , algebra over a field , mathematical analysis , pure mathematics , linear interpolation , mathematical optimization , computer science , animation , paleontology , computer graphics (images) , structural basin , biology , programming language
Abstract 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‐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.