An approximate inverse preconditioner for Toeplitz systems with multiple right-hand sides

We are interested in preconditioning techniques for symmetric positive definite, but ill-conditioned, Toeplitz systems with multiple right-hand sides TX=BTX=B. Here the right-hand sides are available simultaneously. Our main idea is to use an approximate inverse of T as a preconditioner for T. The approximate inverse of T is generated by the inverse formula given by Lv and Huang [X.-G. Lv, T.-Z. Huang, A note on inversion of Toeplitz matrices, Appl. Math. Lett., 20 (2007) 1189–1193]. The construction of the preconditioner is of low computational cost, requires only the entries of T and does not require explicit knowledge of the generating function f of T  . We show that if given a proper parameter, then the approximate inverse preconditioner approximates T-1T-1 accurately, and thus the spectra of these preconditioned matrices are clustered around 1. It follows that the conjugate gradient method converges very quickly when applied to solve the preconditioned systems. Numerical results are given to demonstrate the effectiveness of our preconditioner.