Helmholtz boundary integral methods and the pollution effect

This paper is concerned with solving the Helmholtz exterior Dirichlet and Neumann problems with large wavenumber $k$ and smooth obstacles using the standard second-kind boundary integral equations (BIEs) for these problems. We consider Galerkin and collocation methods - with subspaces consisting of $\textit{either}$ piecewise polynomials (in 2-d for collocation, in any dimension for Galerkin) $\textit{or}$ trigonometric polynomials (in 2-d) - as well as a fully discrete quadrature (a.k.a., Nystr\"om) method based on trigonometric polynomials (in 2-d). For each of these methods, we address the fundamental question: how quickly must $N$, the dimension of the approximation space, grow with $k$ to maintain accuracy as $k\to\infty$? For the methods involving piecewise-polynomials, we give sufficient conditions for $k$-uniform quasi-optimality. For the Galerkin method we show that these conditions are, in fact, necessary and sufficient. In particular we prove that the Galerkin method $\textit{suffers from the pollution effect}$; i.e., $N$ growing like $k^{d-1}$ is often not sufficient for $k$-uniform quasi-optimality. For the Dirichlet BIEs, pollution occurs when the obstacle is trapping - and we also give numerical experiments illustrating this - but for the Neumann BIEs pollution occurs even when the obstacle is a ball. For all the methods involving trigonometric polynomials, we show that, up to potential factors of $k^\epsilon$ for any $\epsilon>0$, there is no pollution (even for trapping obstacles). These are the first results about $k$-explicit convergence of collocation or Nystr\"om methods applied to the Dirichlet BIEs, the first results about $k$-explicit convergence of any method used to solve the standard second-kind Neumann BIEs, and the first results proving that a boundary integral method applied to the Helmholtz equation suffers from the pollution effect.