Approximate inverse-free preconditioners for Toeplitz matrices (Q716080)

The authors study the inverse-free preconditioners for solving Toeplitz systems by utilizing the relation with the Gohberg-Semencul formula, in particular the result that the inverse of a Toeplitz matrix can be written as a sum of multiplications of lower-triangular and upper-triangular Toeplitz matrices. Theoretical convergence results include that if a Toeplitz matrix is generated by a positive bounded function and its entries enjoys the off-diagonal decay property, then the eigenvalues of the preconditioned matrix are clustered around one. Numerical experiments demonstrate that the proposed preconditioners are superior to many existing preconditioners including Strang's circulant preconditioner, T. Chan's circulant preconditioner, the best circulant preconditioner of order 6, and the recursive-based preconditioner method.