Preconditioners for Ill-Conditioned Toeplitz Matrices

This paper is concerned with the solution of systems of linear equations A_Nx = b, where denotes a sequence of positive definite Hermitian ill-conditioned Toeplitz matrices arising from a (real-valued) nonnegative generating function f C₂ with zeros. We construct positive definite Hermitian preconditioners M_N such that the eigenvalues of M_N^–1A_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.