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 $\varepsilon >0$, only ${\cal O} (\log N)$ eigenvalues of our preconditioned Toeplitz systems of size N × N are not contained in $[-1-\varepsilon, -1+\varepsilon] \cup [1 -\varepsilon, 1+\varepsilon]$. 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 ${\cal 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 ${\cal O} (N \log ^2 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.