Fast construction of optimal circulant preconditioners for matrices from the fast dense matrix method (Q1569881)

The authors consider the solution of non-convolution type integral equations by the preconditioned conjugate gradient method. If this method is used to solve the discretized system, the cost per iteration is \(O(n\log n)\) operations. However, for some integral equations, such as the Fredholm integral equations of the first kind, the system is ill-conditioned and therefore the convergence rate of the method is slow. In these cases, preconditioning is required to speed up the convergence rate of the method. A good choice of preconditioner is the optimal circulant preconditioner which is the minimizer of \(\|C - A\|_F\) in Frobenius norm over all circulant matrices \(C.\) It can be obtained by taking arithmetic averages of all the entries of \(A\) and therefore the cost of constructing the preconditioner is of \(O(n^2)\) operations for general dense matrices. In this paper, an \(O(n\log n)\) method of constructing the preconditioner for dense matrices \(A\) obtained from the fast dense matrix method is developed. Application of these ideas to boundary integral equations from potential theory are given. These equations are ill-conditioned whereas their optimal circulant preconditioned equations are well-conditioned. The accuracy of the approximation \(A,\) the fast construction of the preconditioner and the fast convergence of the preconditioned systems are illustrated by numerical examples.