Wavelet based preconditioners for solving the exterior Helmholtz equation with low wavenumbers

Stuart Hawkins Ke Chen

Department of Mathematical Sciences,

The University of Liverpool,

Liverpool L69 7ZL,

UK.

The exterior Helmholtz problem in three dimensions can be reformulated as a boundary integral equation (BIE) over a closed surface. Boundary element methods (BEMs) using multiscale wavelet basis functions give rise to nearly sparse linear systems. This is in contrast to BEMs using single scale piecewise polynomial basis functions, which give rise to dense linear systems. Although sparse preconditioners can be found from dense single scale BEM matrices, we aim to get a better preconditioner from the nearly sparse wavelet BEM matrix because the matrix data is compressed by the wavelets. We present recent work from an ongoing project to develop effective sparse preconditioners for nearly sparse linear systems obtained by discretisation using a wavelet basis.

Many wavelet families are available for one-dimensional problems. Most of these are hard to extend to two-dimensional surfaces, which are typically not periodic. We use an approach that is suitable for problems over complicated two-dimensional surfaces, utilizing partition of the surface into patches, and tensor product wavelets by Harbrect, Schneider, Dahmen, Cohen, and Masson, for the Laplace equation. Optimal preconditioners that yield a condition number independent of the number of unknowns can be found for elliptic problems represented with a wavelet basis. Iterative solution will be efficient for some of these problems. In the general case further preconditioning, using off-diagonal entries, may be required because the resulting condition number may not be small, or because the preconditioned matrix may not be symmetric. Further preconditioning is required when the BIE formulation includes the hypersingular operator. Our BIE uses the Burton and milelr formulation, which includes the hypersingular operator, so that a unique solution to the BIE exisits for all wavenumbers. Often the product $hk$ of the wavenumber $k$ and mesh size $h$ is fixed in BEM computations. This preserves accuracy as the wavenumber increases. We consider fixed, low wavenumber problems with small $h$. This gives high accuracy in the solution.

In the first part of our work we apply a basis transformation from a single scale basis to a wavelet basis using a discrete wavelet transform defined over a two dimensional surface. The result is that the dense non-Hermitian linear system is transformed into a sparse linear system. A preconditioner is obtained by taking a sparse approximation to the system matrix, and inverting it by LU factorization. Fill-in the factorization is reduced by carefully ordering the unknowns. The preconditioned linear system is solved using GMRES. Other preconditioning strategies are applicable.

In the second part of our work the representation of the system matrix in the wavelet basis can be obtained directly by applying a BEM using the wavelet basis. The sparsity pattern of the matrix is known{\em a-priori} so the cost of the BEM is reduced in terms of both complexity and storage. Development of such software is in progress.