Parallel solution of Toeplitzlike linear systems (Q1190529)

This paper presents a weakly numerically stable parallel algorithm for the numerical solution of well-conditioned Toeplitz linear systems that supports the desired parallel polylogarithmic time bound and preserves a near optimum total work bound. It is shown how to compute the inversion of Toeplitz like matrices for any well-conditioned matrix. A modification of Newton's iteration is used to preserve the Toeplitz like structure of the auxiliary matrices. An estimation of the computational cost for the solution of such a Toeplitz like linear system is presented.