Fast Band-Toeplitz Preconditioners for Hermitian Toeplitz Systems
Raymond H. Chan, Ping Tak Peter Tang · SIAM Journal on Scientific Computing · 1994
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 $||(f - g)/f||_\infty $. 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.