A FAST, PRECONDITIONED CONJUGATE-GRADIENT TOEPLITZ AND TOEPLITZ-LIKE SOLVERS

For a Toeplitz or Toeplita-like matrix T, we define a preconditioning applied to the symmetrized matrix (TT)-T-H, which decreases the condit ion number compared to the one of (TT)-T-H and even the one of T. This enables us to accelerate the conjugate gradient algorithm for solving Toepiltz and Toeplitz-like linear systems, thus extending the previou s results of [1], restricted to the Hermitian positive definite case. The extension relies on some recent formulae of Gohberg and Olshevsky for the inverses of Toeplitz-like matrices.