A fast stable solver for nonsymmetric Toeplitz and quasi-Toeplitz systems of linear equations

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.