A Fast Stable Solver for Nonsymmetric Toeplitz and Quasi-Toeplitz Systems of Linear Equations
S. Chandrasekaran, Ali H. Sayed · SIAM Journal on Matrix Analysis and Applications · 1998
We derive a stable and fast solver for nonsymmetric linear systems of equations with shift structured coefficient matrices (e.g., Toeplitz, quasi-Toeplitz, and product of two Toeplitz matrices). The algorithm is based on a modified fast QR factorization of the coefficient matrix and relies on a stabilized version of the generalized Schur algorithm for matrices with displacement structure. All computations can be done in O(n 2 ) operations, where n is the matrix dimension, and the algorithm is backward stable.