The best circulant preconditioners for Hermitian Toeplitz systems II: The multiple-zero case (Q1614992)

[For part I see SIAM J. Numer. Anal. 38, No. 3, 876-896 (2000; Zbl 0978.65035).] The authors discuss the construction of circulant preconditioners for systems of linear algebraic equations \(Ax=b\), where \(A\) is a Hermitian positive definite \((n \times n)\) Toeplitz matrix. Whereas in part I it is supposed that the generating function of the Toeplitz matrix has a zero of even order, the authors consider in the present paper generating functions having multiple zeros of even order. It is proved that the number of iterations of the conjugate gradient method with the proposed circulant preconditioners is of the order \({\mathcal O}(\log\varepsilon^{-1})\) (\(\varepsilon\) a prescribed relative accuracy) and each iteration requires \({\mathcal O}(n\log n)\) operations. The presented numerical experiments confirm the theoretical results.