Alex H. Barnett

Jiuyang Liang, Libin Lu, Alex Barnett et al.

The evaluation of long-range Coulomb interactions is a significant cost in molecular dynamics (MD), even when using Particle Mesh Ewald (PME) or Particle-Particle-Particle-Mesh (PPPM) methods, which rely on Ewald splitting and the fast Fourier transform to achieve near-linear scaling. We introduce ESP -- Ewald summation with prolate spheroidal wave functions (PSWFs) -- which leads to a more efficient Fourier representation and a reduction in the required grid size, global communication, and particle-grid operations, without loss of accuracy. We have integrated the ESP method into two widely-used open-source MD packages, LAMMPS and GROMACS, enabling rapid comparison and adoption. Relative to PME/PPPM baselines at error tolerances $10^{-3}$ to $10^{-4}$, ESP gives roughly a $3$-fold acceleration of electrostatic interactions, and a $2.5$-fold speed-up in the MD simulation when using about $10^3$ compute cores. At high accuracy ($10^{-5}$), these increase to $10$-fold for the far-field electrostatics and $5$-fold for MD simulation. Furthermore, we show that the accelerated codes have improved strong scaling with core count, and validate them in realistic long-time biological and material simulations. ESP thus offers a practical, drop-in path to reduce the time-to-solution and energy footprint of MD workflows.

Alex H. Barnett, Gary Marple, Shravan Veerapaneni et al.

We present a spectrally-accurate scheme to turn a boundary integral formulation for an elliptic PDE on a single unit cell geometry into one for the fully periodic problem. Applications include computing the effective permeability of composite media (homogenization), and microfluidic chip design. Our basic idea is to exploit a small least squares solve to apply periodicity without ever handling periodic Green's functions. We exhibit fast solvers for the two-dimensional (2D) doubly-periodic Neumann Laplace problem (flow around insulators), and Stokes non-slip fluid flow problem, that for inclusions with smooth boundaries achieve 12-digit accuracy, and can handle thousands of inclusions per unit cell. We split the infinite sum over the lattice of images into a directly-summed "near" part plus a small number of auxiliary sources which represent the (smooth) remaining "far" contribution. Applying physical boundary conditions on the unit cell walls gives an expanded linear system, which, after a rank-1 or rank-3 correction and a Schur complement, leaves a well-conditioned square system which can be solved iteratively using fast multipole acceleration plus a low-rank term. We are rather explicit about the consistency and nullspaces of both the continuous and discretized problems. The scheme is simple (no lattice sums, Ewald methods, nor particle meshes are required), allows adaptivity, and is essentially dimension- and PDE-independent, so would generalize without fuss to 3D and to other non-oscillatory elliptic problems such as elastostatics. We incorporate recently developed spectral quadratures that accurately handle close-to-touching geometries. We include many numerical examples, and provide a software implementation.

Lin Zhao, Alex Barnett

The drum problem-finding the eigenvalues and eigenfunctions of the Laplacian with Dirichlet boundary condition-has many applications, yet remains challenging for general domains when high accuracy or high frequency is needed. Boundary integral equations are appealing for large-scale problems, yet certain difficulties have limited their use. We introduce two ideas to remedy this: 1) We solve the resulting nonlinear eigenvalue problem using Boyd's method for analytic root-finding applied to the Fredholm determinant. We show that this is many times faster than the usual iterative minimization of a singular value. 2) We fix the problem of spurious exterior resonances via a combined field representation. This also provides the first robust boundary integral eigenvalue method for non-simply-connected domains. We implement the new method in two dimensions using spectrally accurate Nystrom product quadrature. We prove exponential convergence of the determinant at roots for domains with analytic boundary. We demonstrate 13-digit accuracy, and improved efficiency, in a variety of domain shapes including ones with strong exterior resonances.

Abtin Rahimian, Alex Barnett, Denis Zorin

We introduce a quadrature scheme--QBKIX--for the high-order accurate evaluation of layer potentials associated with general elliptic PDEs near to and on the domain boundary. Relying solely on point evaluations of the underlying kernel, our scheme is essentially PDE-independent; in particular, no analytic expansion nor addition theorem is required. Moreover, it applies to boundary integrals with singular, weakly singular, and hypersingular kernels. Our work builds upon Quadrature by Expansion (QBX), which approximates the potential by an analytic expansion in the neighborhood of each expansion center. In contrast, we use a sum of fundamental solutions lying on a ring enclosing the neighborhood, and solve a small dense linear system for their coefficients to match the potential on a smaller concentric ring. We test the new method with Laplace, Helmholtz, Yukawa, Stokes, and Navier (elastostatic) kernels in two dimensions (2D) using adaptive, panel-based boundary quadratures on smooth and corner domains. Advantages of the algorithm include its relative simplicity of implementation, immediate extension to new kernels, dimension-independence (allowing simple generalization to 3D), and compatibility with fast algorithms such as the kernel-independent FMM.

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.

Alex H. Barnett, Andrew Hassell

We present a new algorithm for numerical computation of large eigenvalues and associated eigenfunctions of the Dirichlet Laplacian in a smooth, star-shaped domain in $\mathbb{R}^d$, $d\ge 2$. Conventional boundary-based methods require a root-search in eigenfrequency $k$, hence take $O(N^3)$ effort per eigenpair found, using dense linear algebra, where $N=O(k^{d-1})$ is the number of unknowns required to discretize the boundary. Our method is O(N) faster, achieved by linearizing with respect to $k$ the spectrum of a weighted interior Neumann-to-Dirichlet (NtD) operator for the Helmholtz equation. Approximations $\hat{k}_j$ to the square-roots $k_j$ of all O(N) eigenvalues lying in $[k - ε, k]$, where $ε=O(1)$, are found with $O(N^3)$ effort. We prove an error estimate $$ |\hat k_j - k_j| \leq C \Big(\frac{ε^2}{k} + ε^3 \Big), $$ with $C$ independent of $k$. We present a higher-order variant with eigenvalue error scaling empirically as $O(ε^5)$ and eigenfunction error as $O(ε^3)$, the former improving upon the 'scaling method' of Vergini--Saraceno. For planar domains ($d=2$), with an assumption of absence of spectral concentration, we also prove rigorous error bounds that are close to those numerically observed. For $d=2$ we compute robustly the spectrum of the NtD operator via potential theory, Nyström discretization, and the Cayley transform. At high frequencies (400 wavelengths across), with eigenfrequency relative error $10^{-10}$, we show that the method is $10^3$ times faster than standard ones based upon a root-search.

A. H. Barnett, Andrew Hassell

We study eigenfunctions and eigenvalues of the Dirichlet Laplacian on a bounded domain $Ω\subset\RR^n$ with piecewise smooth boundary. We bound the distance between an arbitrary parameter $E > 0$ and the spectrum $\{E_j \}$ in terms of the boundary $L^2$-norm of a normalized trial solution $u$ of the Helmholtz equation $(Δ+ E)u = 0$. We also bound the $L^2$-norm of the error of this trial solution from an eigenfunction. Both of these results are sharp up to constants, hold for all $E$ greater than a small constant, and improve upon the best-known bounds of Moler--Payne by a factor of the wavenumber $\sqrt{E}$. One application is to the solution of eigenvalue problems at high frequency, via, for example, the method of particular solutions. In the case of planar, strictly star-shaped domains we give an inclusion bound where the constant is also sharp. We give explicit constants in the theorems, and show a numerical example where an eigenvalue around the 2500th is computed to 14 digits of relative accuracy. The proof makes use of a new quasi-orthogonality property of the boundary normal derivatives of the eigenmodes, of interest in its own right.

Anna Broms, Anna-Karin Tornberg, Alex H. Barnett

We tackle two key difficulties in the simulation of the viscous hydrodynamics of a large dense collection of rigid particles: (i) the poor convergence rate of an iterative solution of the discretized linear system as particle gaps shrink, and (ii) the large number of unknowns needed to accurately discretize the resulting lubrication-driven flows. Our focus is the 2D Stokes resistance and mobility boundary value problems for nearly-touching disks. To address both challenges, we introduce a general two-body preconditioning strategy, and implement it with the method of fundamental solutions. For each close particle pair, the hard-to-resolve interaction is represented in a basis precomputed by solving a local boundary value problem on a fine grid. In an iterative solve, the resulting flow field corrects that obtained from a coarse representation of all particles. The local fine-grid correction can even be compressed so that all particles except the pair itself are affected by an equivalent set of coarse sources. Numerical experiments demonstrate rapid GMRES convergence in challenging multi-particle settings, with iteration counts remaining low even in densely packed suspensions. For example, the mobility problem is solved for a random close packing with area fraction $φ= 0.65$, $P = 10000$ monodisperse disks, and minimum separation $10^{-3}$, in just 47 GMRES iterations, achieving five digits of accuracy with 72 vector unknowns per body.

A. H. Barnett, Andrew Hassell

We consider the "Method of particular solutions" for numerically computing eigenvalues and eigenfunctions of the Laplacian $Δ$ on a smooth, bounded domain Omega in RR^n with either Dirichlet or Neumann boundary conditions. This method constructs approximate eigenvalues E, and approximate eigenfunctions u that satisfy $Δu=Eu$ in Omega, but not the exact boundary condition. An inclusion bound is then an estimate on the distance of E from the actual spectrum of the Laplacian, in terms of (boundary data of) u. We prove operator norm estimates on certain operators on $L^2(\partial Ω)$ constructed from the boundary values of the true eigenfunctions, and show that these estimates lead to sharp inclusion bounds in the sense that their scaling with $E$ is optimal. This is advantageous for the accurate computation of large eigenvalues. The Dirichlet case can be treated using elementary arguments and has appeared in SIAM J. Num. Anal. 49 (2011), 1046-1063, while the Neumann case seems to require much more sophisticated technology. We include preliminary numerical examples for the Neumann case.

Chirag Modi, Alex Barnett, Bob Carpenter

The efficiency of Hamiltonian Monte Carlo (HMC) can suffer when sampling a distribution with a wide range of length scales, because the small step sizes needed for stability in high-curvature regions are inefficient elsewhere. To address this we present a delayed rejection variant: if an initial HMC trajectory is rejected, we make one or more subsequent proposals each using a step size geometrically smaller than the last. We extend the standard delayed rejection framework by allowing the probability of a retry to depend on the probability of accepting the previous proposal. We test the scheme in several sampling tasks, including multiscale model distributions such as Neal's funnel, and statistical applications. Delayed rejection enables up to five-fold performance gains over optimally-tuned HMC, as measured by effective sample size per gradient evaluation. Even for simpler distributions, delayed rejection provides increased robustness to step size misspecification. Along the way, we provide an accessible but rigorous review of detailed balance for HMC.

Alex Barnett, Leslie Greengard, Andras Pataki et al.

Determining the three-dimensional structure of proteins and protein complexes at atomic resolution is a fundamental task in structural biology. Over the last decade, remarkable progress has been made using "single particle" cryo-electron microscopy (cryo-EM) for this purpose. In cryo-EM, hundreds of thousands of two-dimensional images are obtained of individual copies of the same particle, each held in a thin sheet of ice at some unknown orientation. Each image corresponds to the noisy projection of the particle's electron-scattering density. The reconstruction of a high-resolution image from this data is typically formulated as a nonlinear, non-convex optimization problem for unknowns which encode the angular pose and lateral offset of each particle. Since there are hundreds of thousands of such parameters, this leads to a very CPU-intensive task---limiting both the number of particle images which can be processed and the number of independent reconstructions which can be carried out for the purpose of statistical validation. Here, we propose a deterministic method for high-resolution reconstruction that operates in an ab initio manner---that is, without the need for an initial guess. It requires a predictable and relatively modest amount of computational effort, by marching out radially in the Fourier domain from low to high frequency, increasing the resolution by a fixed increment at each step.

Alex H. Barnett, Jeremy F. Magland, Leslie F. Greengard

We describe a suite of validation metrics that assess the credibility of a given automatic spike sorting algorithm applied to a given electrophysiological recording, when ground-truth is unavailable. By rerunning the spike sorter two or more times, the metrics measure stability under various perturbations consistent with variations in the data itself, making no assumptions about the noise model, nor about the internal workings of the sorting algorithm. Such stability is a prerequisite for reproducibility of results. We illustrate the metrics on standard sorting algorithms for both in vivo and ex vivo recordings. We believe that such metrics could reduce the significant human labor currently spent on validation, and should form an essential part of large-scale automated spike sorting and systematic benchmarking of algorithms.

Gary Marple, Alex Barnett, Adrianna Gillman et al.

This paper presents a new boundary integral equation (BIE) method for simulating particulate and multiphase flows through periodic channels of arbitrary smooth shape in two dimensions. The authors consider a particular system---multiple vesicles suspended in a periodic channel of arbitrary shape---to describe the numerical method and test its performance. Rather than relying on the periodic Green's function as classical BIE methods do, the method combines the free-space Green's function with a small auxiliary basis, and imposes periodicity as an extra linear condition. As a result, we can exploit existing free-space solver libraries, quadratures, and fast algorithms, and handle a large number of vesicles in a geometrically complex channel. Spectral accuracy in space is achieved using the periodic trapezoid rule and product quadratures, while a first-order semi-implicit scheme evolves particles by treating the vesicle-channel interactions explicitly. New constraint-correction formulas are introduced that preserve reduced areas of vesicles, independent of the number of time steps taken. By using two types of fast algorithms, (i) the fast multipole method (FMM) for the computation of the vesicle-vesicle and the vesicle-channel hydrodynamic interaction, and (ii) a fast direct solver for the BIE on the fixed channel geometry, the computational cost is reduced to $O(N)$ per time step where $N$ is the spatial discretization size. Moreover, the direct solver inverts the wall BIE operator at $t = 0$, stores its compressed representation and applies it at every time step to evolve the vesicle positions, leading to dramatic cost savings compared to classical approaches. Numerical experiments illustrate that a simulation with $N=128, 000$ can be evolved in less than a minute per time step on a laptop.

Alex H. Barnett, Bowei Wu, Shravan K. Veerapaneni

Dense particulate flow simulations using integral equation methods demand accurate evaluation of Stokes layer potentials on arbitrarily close interfaces. In this paper, we generalize techniques for close evaluation of Laplace double-layer potentials in J. Helsing and R. Ojala, J. Comput. Phys. 227 (2008) 2899-2921. We create a "globally compensated" trapezoid rule quadrature for the Laplace single-layer potential on the interior and exterior of smooth curves. This exploits a complex representation, a product quadrature (in the style of Kress) for the sawtooth function, careful attention to branch cuts, and second-kind barycentric-type formulae for Cauchy integrals and their derivatives. Upon this we build accurate single- and double-layer Stokes potential evaluators by expressing them in terms of Laplace potentials. We test their convergence for vesicle-vesicle interactions, for an extensive set of Laplace and Stokes problems, and when applying the system matrix in a boundary value problem solver in the exterior of multiple close-to-touching ellipses. We achieve typically 12 digits of accuracy using very small numbers of discretization nodes per curve. We provide documented codes for other researchers to use.