Best-conditioned circulant preconditioners (Q1805202)

The solutions to a class of Hermitian positive definite systems \(Ax = b\) by the preconditioned conjugate gradient method (PCG) with circulant preconditioner \(C\) are discussed. The rate of convergence of the PCG method depends on how small the condition number \(\kappa (C^{-{1\over 2}} AC^{-{1\over 2}})\) is. It is shown that if the matrix \(FAF^*\) has property A, then \(C_F = F^*\delta (FAF^*)F\) minimizes \(\kappa (C^{-{1\over 2}} AC^{-{1\over 2}})\) over all Hermitian positive definite circulant matrices \(C\), where \(F\) is the Fourier matrix and \(\delta(B)\) is the diagonal matrix such that \(\delta (B)_{i,i} = (B)_{i,i}\), \(1 \leq i \leq n\). It is also shown that there exists a noncirculant Toeplitz matrix \(A\) such that \(FAF^*\) has property A.