Authors
Marc Van Barel, Georg Heinig, Peter Kravanja
Publication date
2001
Journal
SIAM Journal on Matrix Analysis and Applications
Volume
23
Issue
2
Pages
494-510
Publisher
Society for Industrial and Applied Mathematics
Description
We present a stabilized superfast solver for nonsymmetric Toeplitz systems Tx=b. An explicit formula for T-1 is expressed in such a way that the matrix-vector product T^-1b can be calculated via FFTs and Hadamard products. This inversion formula involves certain polynomials that can be computed by solving two linearized rational interpolation problems on the unit circle. The heart of our Toeplitz solver is a superfast algorithm to solve these interpolation problems. To stabilize the algorithm, i.e., to improve the accuracy, several techniques are used: pivoting, iterative improvement, downdating, and giving "difficult" interpolation points an adequate treatment. We have implemented our algorithm in Fortran 90. Numerical examples illustrate the effectiveness of our approach.
Total citations
Scholar articles
M Van Barel, G Heinig, P Kravanja - SIAM Journal on Matrix Analysis and Applications, 2001