PRECONDITIONERS FOR NONDEFINITE HERMITIAN TOEPLITZ SYSTEMS

       This paper is concerned with the construction of circulant preconditioners for Toeplitz systems arising from a piecewise continuous generating function with sign changes.

       If the generating function is given, we prove that for any ε > 0, only script O(log N) eigenvalues of our preconditioned Toeplitz systems of size N × N are not contained in [-1-ε, -1+ε]∪[1-ε, 1+ε]. The result can be modified for trigonometric preconditioners. We also suggest circulant preconditioners for the case that the generating function is not explicitly known and show that only script O(log N) absolute values of the eigenvalues of the preconditioned Toeplitz systems are not contained in a positive interval on the real axis.

       Using the above results, we conclude that the preconditioned minimal residual method requires only script O(N log² N) arithmetical operations to achieve a solution of prescribed precision if the spectral condition numbers of the Toeplitz systems increase at most polynomial in N. We present various numerical tests.