Best-Conditioned Circulant Preconditioners

We discuss the solutions to a class of Hermitian positive definite systems Ax = b by the preconditioned conjugate gradient method with circulant preconditioner C. In general, the smaller the condition number κ(C^−1/2 AC^−1/2) is, the faster the convergence of the method will be. The circulant matrix C_b that minimizes κ(C^−1/2 AC^−1/2) is called the best-conditioned circulant preconditioner for the matrix A. We prove that if F AF^∗ has Property A, where F is the Fourier matrix, then C_b minimizes ∥C − A∥_F over all circulant matrices C. Here ∥·∥_F denotes the Frobenius norm. We also show that there exists a noncirculant Toeplitz matrix A such that F AF^∗ has Property A.