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 f. The preconditioned conjugate gradient method with well-known circulant preconditioners fails in the case when f has zeros. This paper employs Toeplitz matrices of fixed bandwidth as preconditioners. Their generating functions g are trigonometric polynomials of fixed degree and are determined by minimizing the maximum relative error parallel to(f - g)/f parallel to(infinity). It is shown that the condition number of systems preconditioned by the band-Toeplitz matrices are O(1) for f, with or without zeros. When f is positive, the preconditioned systems converge at the same rate as other well-known circulant preconditioned systems. An a priori bound of the number of iterations required for convergence is also given.