Preconditioners for Ill-Conditioned Toeplitz Systems Constructed from Positive Kernels
Daniel Potts, Gabriele Steidl · SIAM Journal on Scientific Computing · 2001
In this paper, we are interested in the iterative solution of ill-conditioned Toeplitz systems generated by continuous nonnegative real-valued functions f with a finite number of zeros. We construct new w-circulant preconditioners without explicit knowledge of the generating function f by approximating f by its convolution f * K N with a suitable positive reproducing kernel K N . By the restriction to positive kernels we obtain positive definite preconditioners. Moreover, if f has only zeros of even order $\le 2s$, then we can prove that the property $ \int_{-\pi}^{\pi} t^{2k} K_N (t) \, \mbox{d} t \le C N^{-2k} $ $(k=0,\hspace*{1.5pt}\ldots,s)$ of the kernel is necessary and sufficient to ensure the convergence of the PCG method in a number of iteration steps independent of the dimension N of the system. Our theoretical results were confirmed by numerical tests.