BEST-CONDITIONED CIRCULANT PRECONDITIONERS

We discuss the solutions to a class of Hermitian positive definite sys tems Ax = b by the preconditioned conjugate gradient method with circu lant preconditioner C. In general, the smaller the condition number ka ppa(C-1/2 AC-1/2) is, the faster the convergence of the method will be . The circulant matrix C(b) that minimizes kappa(C-1/2 AC-1/2) is call ed the best-conditioned circulant preconditioner for the matrix A. We prove that if F AF has Property A, where F is the Fourier matrix, the n C(b) minimizes parallel-to C - A parallel-to F over all circulant ma trices C. Here parallel-to . parallel-to F denotes the Frobenius norm. We also show that there exists a noncirculant Toeplitz matrix A such that F AF has Property A.