Multigrid methods for indefinite Toeplitz matrices

In this paper we modify a multigrid technique introduced for ill- conditioned symmetric positive definite Toepliltz linear systems [22] in order to deal with the nondefinite case. This kind of linear systems arises in important applications such as image restoration, harmonic retrieval etc. We prove that the cost per iteration is O(nlog2n) ops and O(log2n) parallel steps while the convergence speed seems to be independent of the problem matrix-size. Therefore this technique results to be competitive with respect to the fast direct method devised by Chan and Hansen [16] and is alternative to the PCG-based algorithm introduced in [33, 32, 37].