P. G. Martinsson

P. Young, S. Hao, P. G. Martinsson

A scheme for rapidly and accurately computing solutions to boundary integral equations (BIEs) on rotationally symmetric surfaces in R^3 is presented. The scheme uses the Fourier transform to reduce the original BIE defined on a surface to a sequence of BIEs defined on a generating curve for the surface. It can handle loads that are not necessarily rotationally symmetric. Nystrom discretization is used to discretize the BIEs on the generating curve. The quadrature is a high-order Gaussian rule that is modified near the diagonal to retain high-order accuracy for singular kernels. The reduction in dimensionality, along with the use of high-order accurate quadratures, leads to small linear systems that can be inverted directly via, e.g., Gaussian elimination. This makes the scheme particularly fast in environments involving multiple right hand sides. It is demonstrated that for BIEs associated with the Laplace and Helmholtz equations, the kernel in the reduced equations can be evaluated very rapidly by exploiting recursion relations for Legendre functions. Numerical examples illustrate the performance of the scheme; in particular, it is demonstrated that for a BIE associated with Laplace's equation on a surface discretized using 320,800 points, the set-up phase of the algorithm takes 1 minute on a standard laptop, and then solves can be executed in 0.5 seconds.

S. Hao, A. H. Barnett, P. G. Martinsson et al.

Boundary integral equations and Nystrom discretization provide a powerful tool for the solution of Laplace and Helmholtz boundary value problems. However, often a weakly-singular kernel arises, in which case specialized quadratures that modify the matrix entries near the diagonal are needed to reach a high accuracy. We describe the construction of four different quadratures which handle logarithmically-singular kernels. Only smooth boundaries are considered, but some of the techniques extend straightforwardly to the case of corners. Three are modifications of the global periodic trapezoid rule, due to Kapur-Rokhlin, to Alpert, and to Kress. The fourth is a modification to a quadrature based on Gauss-Legendre panels due to Kolm-Rokhlin; this formulation allows adaptivity. We compare in numerical experiments the convergence of the four schemes in various settings, including low- and high-frequency planar Helmholtz problems, and 3D axisymmetric Laplace problems. We also find striking differences in performance in an iterative setting. We summarize the relative advantages of the schemes.

A. Gillman, P. G. Martinsson

The Fast Multipole Method (FMM) provides a highly efficient computational tool for solving constant coefficient partial differential equations (e.g. the Poisson equation) on infinite domains. The solution to such an equation is given as the convolution between a fundamental solution and the given data function, and the FMM is used to rapidly evaluate the sum resulting upon discretization of the integral. This paper describes an analogous procedure for rapidly solving elliptic \textit{difference} equations on infinite lattices. In particular, a fast summation technique for a discrete equivalent of the continuum fundamental solution is constructed. The asymptotic complexity of the proposed method is $O(N_{\rm source})$, where $N_{\rm source}$ is the number of points subject to body loads. This is in contrast to FFT based methods which solve a lattice Poisson problem at a cost $O(N_Ω\log N_Ω)$ independent of $N_{\rm source}$, where $Ω$ is an artificial rectangular box containing the loaded points and $N_Ω$ is the number of points in $Ω$.

P. G. Martinsson

A discretization scheme for variable coefficient Helmholtz problems on two-dimensional domains is presented. The scheme is based on high-order spectral approximations and is designed for problems with smooth solutions. The resulting system of linear equations is solved using a direct solver with O(N^1.5) complexity for the pre-computation and O(N log N) complexity for the solve. The fact that the solver is direct is a principal feature of the scheme, since iterative methods tend to struggle with the Helmholtz equation. Numerical examples demonstrate that the scheme is fast and highly accurate. For instance, using a discretization with 12 points per wave-length, a Helmholtz problem on a domain of size 100 x 100 wavelengths was solved to ten correct digits. The computation was executed on an office desktop; it involved 1.6M degrees of freedom and required 100 seconds for the pre-computation, and 0.3 seconds for the actual solve.

P. G. Martinsson

A numerical method for variable coefficient elliptic problems on two dimensional domains is described. The method is based on high-order spectral approximations and is designed for problems with smooth solutions. The resulting system of linear equations is solved using a direct solver with $O(N^{1.5})$ complexity for the pre-computation and $O(N \log N)$ complexity for the solve. The fact that the solver is direct is a principal feature of the scheme, and makes it particularly well suited to solving problems for which iterative solvers struggle; in particular for problems with highly oscillatory solutions. This note is intended as a tutorial description of the scheme, and draws heavily on previously published material.