Stability analysis and fast algorithms for triangulation of Toeplitz matrices (Q1358161)

An algorithm for triangularizing an \(m \times n\) Toeplitz matrix is presented. This algorithm is a generalization of the classical algorithm due to Schur. In the QR decomposition of a Toeplitz matrix the new algorithm produces a more accurate R factor (upper triangular) than other existing fast methods, especially for ill-conditioned problems. In this generalized Schur algorithm, each row of the triangular factor is computed recursively via updating and downdating steps. A forward error analysis shows that the relative accuracy of the computed upper triangular factor is bounded essentially by the square condition number square of the given Toeplitz matrix, like in Cholesky decomposition. Five numerical tests are performed in order to verify the performance of the algorithm.