Uppsala University Department of Information Technology

Technical Report 2000-032

Preconditioners Based on Fundamental Solutions

Henrik Brandén and Per Sundqvist

November 2000

Abstract:

We consider a new convergence acceleration technique for the iterative solution of linear systems of equations that arise when discretizing partial differential equations. The method is applied to finite difference discretizations, but the ideas and the basic theory apply to other discretizations too.

If E is a fundamental solution of a differential operator P, we have E*(Pu)=u. Inspired by this, we choose the preconditioner to be a discretization of the approximative inverse K, given by

(Ku)(x)=intOmegaE(x-y)u(y)dy,      x∈Omegasubsetmathds{R}d,
where Omega is the domain of interest. The operator K is only an approximation of P-1 since we do not integrate over all of mathds{R}d as for the convolution, and since we impose boundary conditions. Two main advantages of this method are that we can perform analysis before we discretize the operators, and that there is a fast way of applying the preconditioner using FFT.

We present analysis showing that if P is a first order differential operator, KP is bounded. The analysis also describes how K differs from P-1. Implementation aspects are considered, and numerical results show grid independent convergence for first order partial differential equations. For the second order convection-diffusion equation convergence is no longer grid independent, a result that is consistent with our theory. However, if the grid is chosen to give a fixed number of grid points within boundary layers, the number of iterations is independent of the physical viscosity parameter.

Note: Revised version available as IT technical report 2005-001

Available as compressed Postscript (673 kB, no cover)

Download BibTeX entry.



Uppsala Universitet