Chan, Raymond H.; Ng, Wingfai; Sun, Haiwei Fast construction of optimal circulant preconditioners for matrices from the fast dense matrix method. (English) Zbl 0955.65095 BIT 40, No. 1, 024-040 (2000). 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. Reviewer: Nikolay Yakovlevich Tikhonenko (Odessa) 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) Keywords:potential equations; optimal circulant preconditioners; conjugate gradient method; fast dense matrix method; non-convolution tyepe integral equations; Fredholm integral equations of the first kind; convergence; preconditioning; boundary integral equations; numerical examples PDFBibTeX XMLCite \textit{R. H. Chan} et al., BIT 40, No. 1, 024--040 (2000; Zbl 0955.65095) Full Text: DOI