Fast Band-Toeplitz Preconditioners for Hermitian Toeplitz Systems

This paper considers the solutions of Hermitian Toeplitz systems where the Toeplitz matrices are generated by nonnegative functions ƒ. The preconditioned conjugate gradient method withwell-known circulant preconditioners fails in the case when ƒ has zeros. This paper employs Toeplitz matrices offixed bandwidth as preconditioners. Their generating functions g are trigonometric polynomials of fixed degree and aredetermined by minimizing the maximum relative error ||(ƒ - g)/ƒ||∞. Itis shown that the condition number of systems preconditioned by theband-Toeplitz matrices are O(1) for ƒ, with or withoutzeros. When ƒ is positive, the preconditioned systems converge at thesame rate as other well-known circulant preconditioned systems. An a prioribound of the number of iterations required for convergence is also given.