OPTIMAL TRIGONOMETRIC PRECONDITIONERS FOR NONSYMMETRIC TOEPLITZ-SYSTEMS

This paper is concerned with the solution of systems of linear equatio ns T(N)x(N) = b(N), where {T-N}(N is an element of N) denotes a sequen ce of nonsingular nonsymmetric Toeplitz matrices arising from a genera ting function of the Wiener class. We present a technique for the fast construction of optimal trigonometric preconditioners M-N = M-N(T'T-N (N)) of the corresponding normal equation which can be extended to Toe plitz least squares problems in a straightforward way. Moreover, we pr ove that the spectrum of the preconditioned matrix MN-1T'T-N(N) is clu stered at 1 such that the PCG-method applied to the normal equation co nverges superlinearly. Numerical tests confirm the theoretical expecta tions. (C) 1998 Published by Elsevier Science Inc. All rights reserved .