×

Fast construction of optimal circulant preconditioners for matrices from the fast dense matrix method. (English) Zbl 0955.65095

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.

MSC:

65R20 Numerical methods for integral equations
45B05 Fredholm integral equations
65N38 Boundary element methods for boundary value problems involving PDEs
65F35 Numerical computation of matrix norms, conditioning, scaling
35J05 Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation
65F10 Iterative numerical methods for linear systems
45E10 Integral equations of the convolution type (Abel, Picard, Toeplitz and Wiener-Hopf type)
PDFBibTeX XMLCite
Full Text: DOI