Fast Band-Toeplitz Preconditioners (Chan and Tang)

======================================================================
SIAM Journal on Scientific Computing
Volume 15-1, January 1994, pp.  164-171
(C) 1994 by Society for Industrial and Applied Mathematics
All rights reserved


Title:            Fast Band-Toeplitz Preconditioners for Hermitian
                  Toeplitz Systems

Author:           Raymond H. Chan and Ping Tak Peter Tang

AMS Subject
Classifications:  65F10, 65F15

Key words:        Toeplitz matrix, generating function, preconditioned 
                  conjugate gradient method, Chebyshev approximation, 
                  Remez algorithm

----

ABSTRACT

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. 


======================================================================

SIAM
3600 University City Science Center
Philadelphia, PA  19104-2688, USA

Phone:  215-382-9800, 800-447-7426 (USA only)
Fax:  215-386-7999
E-mail:  journals@siam.org