Preconditioners for ill-conditioned Toeplitz matrices

This paper is concerned with the solution of systems of linear equations A(N)x: = b, where {A(N)}(N is an element of N) denotes a sequence of positive definite Hermitian ill-conditioned Toeplitz matrices arising from a (real-valued) nonnegative generating function f is an element of C-2 pi with zeros. We construct positive definite Hermitian preconditioners MN such that the eigenvalues of M(N)(-1)A(N) are clustered at 1 and the corresponding PCG-method requires only O(N log N) arithmetical operations to achieve a prescribed precision. We sketch how our preconditioning technique can be extended to symmetric Toeplitz systems, doubly symmetric block Toeplitz systems with Toeplitz blocks and non-Hermitian Toeplitz systems. Numerical tests confirm the theoretical expectations.