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 prove that these are, in fact, necessary and sufficient. In particular, we prove that, when applied to the Neumann BIEs when the obstacle is a ball, the Galerkin method $\textit{suffers from the pollution effect}$; i.e., $N$ growing like $k^{d-1}$ is not sufficient for $k$-uniform quasi-optimality. For the Dirichlet BIEs, we prove that pollution occurs for the ball for certain choices of coupling parameter, and we give numerical experiments illustrating pollution for trapping domains with the standard coupling parameter. For all the methods involving trigonometric polynomials, we show that, up to potential factors of $k^\varepsilon$ for any $\varepsilon>0$, these methods do not suffer from the pollution effect (even for trapping obstacles). These are the first results about $k$-explicit convergence of collocation or Nystr\"om methods applied to the Dirichlet BIEs, and the first results about $k$-explicit convergence of any method used to solve the standard second-kind Neumann BIEs.