Circulant preconditioners for complex Toeplitz matrices

The solution of n-by-n complex Toeplitz systems A_nx = b by the preconditioned conjugate gradient method is studied. The preconditioner C_n is the circulant matrix that minimizes ||B_n-A_n||_F over all circulant matrices B_n. The authors prove that if the generating function of A_n is a 2μ-periodic continuous complex-valued function without any zeros, then the spectrum of the normalized preconditioned matrix (C_n^-1A_n)*(C_n^-1A_n) will be clustered around one. Hence they show that if the condition number of A_n is of O (n^α), the conjugate gradient method, when applied to solving the normalized preconditioned system, converges in at most O (α log n+1) steps. Thus the total complexity of the algorithm is O (αn log² n + 1 log n).