Convergence analysis of superoptimal PCG algorithm for Toeplitz systems with a Fisher–Hartwig singularity

AbstractRecently, Lu and Hurvich [Y. Lu, C. Hurvich, On the complexity of the preconditioned conjugate gradient algorithm for solving toeplitz systems with a Fisher–Hartwig singularity, SIAM J. Matrix Anal. Appl. 27 (2005) 638–653] used the preconditioned conjugate gradient method with the optimal circulant preconditioner proposed in Chan [T. Chan, An optimal circulant preconditioner for Toeplitz systems, SIAM J. Sci. Statist. Comput. 9 (1988) 766–771] for solving the Toeplitz system Tn(f)x=b where the generating function f is given byf(ω)=|1-e-iω|-2dh(ω)with d∈-12,12⧹{0}. The function h(ω) is positive continuous on [-π,π] and differentiable on [-π,π]⧹{0}. In this paper, we will use the superoptimal circulant preconditioner proposed by Tyrtyshnikov [E. Tyrtyshnikov, Optimal and superoptimal circulant preconditioners, SIAM J. Matrix Anal. Appl. 13 (1992) 459–473] to solve the same problem when 0<d