Stabilization by Perturbation of a 4 n 2 Toeplitz Solver
Per Christian Hansen, Plamen Y. Yalamov · SIAM Journal on Matrix Analysis and Applications · 2000
We consider a 4n 2 -algorithm for computing the Gohberg--Semencul representation of the inverse of a nonsymmetric Toeplitz matrix and for obtaining the solution of a Toeplitz system. The original algorithm is unstable when one or more of the leading principal submatrices are ill-conditioned. In our stabilized version we slightly perturb thematrix when we encounter a division by a small number. As a consequence, the solution is also perturbed, and its accuracy can be improved by taking a small number of iterative refinement steps. We present a roundoff error analysis of the new algorithm as well as numerical results that support our analysis.