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

Raymond H. CHAN*, Wing Fai NG, Hai Wei SUN

*Corresponding author for this work

Research output: Journal PublicationsJournal Article (refereed)peer-review

3 Citations (Scopus)


In this paper, we consider solving non-convolution type integral equations by the preconditioned conjugate gradient method. The fast dense matrix method is a fast multiplication scheme that provides a dense discretization matrix A approximating a given integral equation. The dense matrix A can be constructed in O(n) operations and requires only O(n) storage where n is the size of the matrix. Moreover, the matrix-vector multiplication Ax can be done in O(nlogn) operations. Thus if the conjugate gradient method is used to solve the discretized system, the cost per iteration is O(nlogn) operations. However, for some integral equations, such as the Fredholm integral equations of the first kind, the system will be ill-conditioned and therefore the convergence rate of the method will be 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(n2) operations for general dense matrices. In this paper, we develop an O(nlogn) method of constructing the preconditioner for dense matrices A obtained from the fast dense matrix method. Application of these ideas to boundary integral equations from potential theory will be given. These equations are ill-conditioned whereas their optimal circulant preconditioned equations will be well-conditioned. The accuracy of the approximation A, the fast construction of the preconditioner and the fast convergence of the preconditioned systems will be illustrated by numerical examples.

Original languageEnglish
Pages (from-to)24-40
Number of pages17
JournalBIT Numerical Mathematics
Issue number1
Publication statusPublished - Mar 2000
Externally publishedYes


  • Circulant preconditioners
  • Conjugate gradient method
  • Integral equations


Dive into the research topics of 'Fast construction of optimal circulant preconditioners for matrices from the fast dense matrix method'. Together they form a unique fingerprint.

Cite this