2003/01/01 by Michael Stewart · 1 citation
Computer Science · Mathematics · #Matrix Theory and Algorithms #Advanced Topics in Algebra #Advanced Algebra and Geometry #Toeplitz matrix #Solver #Mathematics #FLOPS #Inverse #Matrix (chemical analysis) #Positive-definite matrix #Algorithm #Numerical stability #Block (permutation group theory) #Inversion (geology) #Divide and conquer algorithms #Applied mathematics #Combinatorics #Parallel computing #Numerical analysis #Computer science #Mathematical optimization #Pure mathematics #Mathematical analysis #Geometry #Eigenvalues and eigenvectors
paper · doi:10.1137/s089547980241791x
openalex publication_date 2003/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2025/11/06
This paper describes a new O(n log3(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.