A Fast Stable Solver for Nonsymmetric Toeplitz and Quasi-Toeplitz Systems of Linear Equations (Q4389064)

The algorithm derived in this paper is determined to solve nonsymmetric linear systems of equations with Toeplitz, quasi-Toeplitz and shift structured matrices. The algorithm is based on ideas of displacement structure theory and relies on the generalized Schur algorithm because QR factorization of a structured matrix can be computed by \(2n\) steps of the generalized Schur algorithm on the augmented matrix. The first \(n\) steps lead to a generator matrix for the Schur complement. If it is possible to find an explicit generator matrix, the first \(n\) steps are saved. From the numerical point of view, such computing of the QR factors is not stable. First a stable algorithm for a well-conditioned coefficient matrix is derived, and the error analysis of the first \(n\) steps and the last \(n\) steps of the generalized Schur algorithm is discussed. Then a modification of the algorithm when the coefficient matrix is ill-conditioned is considered. Finally, the authors return to the problem of solving a linear system of equations, where the matrix is well conditioned or ill conditioned. Conditions imposed on the coefficient matrix in order to guarantee a fast backward stable solver are listed. The authors performed extensive experiments to verify the theoretical error bounds.