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