A Superfast Toeplitz Solver with Improved Numerical Stability
Michael Stewart · SIAM Journal on Matrix Analysis and Applications · 2003
This paper describes a new O(n log 3 (n)) solver for the positive definite Toeplitz system Tx=b. Instead of computing generators for the inverse of T, the new algorithm adjoins b to T and applies a superfast Schur algorithm to the resulting augmented matrix. The generators of this augmented matrix and its Schur complements are used by a divide-and-conquer block back-substitution routine to complete the solution of the system. The goal is to avoid the well-known numerical instability inherent in explicit inversion. Experiments suggest that the algorithm is backward stable in most cases.