Publications

The nonuniform fast Fourier transform (NUFFT) generalizes the FFT to off-grid data. Its many applications include image reconstruction, data analysis, and the numerical solution of differential equations. We present FINUFFT, an efficient parallel library for type 1 (nonuiform to uniform), type 2 (uniform to nonuniform), or type 3 (nonuniform to nonuniform) transforms, in dimensions 1, 2, or 3. It uses minimal RAM, requires no precomputation or plan steps, and has a simple interface to several languages. We perform the expensive spreading/interpolation between nonuniform points and the fine grid via a simple new kernel---the `exponential of semicircle' $e^{\beta \sqrt{1-x^2}}$ in $x\in[-1,1]$---in a cache-aware load-balanced multithreaded implementation. The deconvolution step requires the Fourier transform of the kernel, for which we propose efficient numerical quadrature. For types 1 and 2, rigorous error bounds asymptotic in the kernel width approach the fastest known exponential rate, namely that of the Kaiser--Bessel kernel. We benchmark against several popular CPU-based libraries, showing favorable speed and memory footprint, especially in three dimensions when high accuracy and/or clustered point distributions are desired.

We present a hybrid asymptotic/numerical method for the accurate computation of single and double layer heat potentials in two dimensions. It has been shown in previous work that simple quadrature schemes suffer from a phenomenon called "geometrically-induced stiffness," meaning that formally high-order accurate methods require excessively small time steps before the rapid convergence rate is observed. This can be overcome by analytic integration in time, requiring the evaluation of a collection of spatial boundary integral operators with non-physical, weakly singular kernels. In our hybrid scheme, we combine a local asymptotic approximation with the evaluation of a few boundary integral operators involving only Gaussian kernels, which are easily accelerated by a new version of the fast Gauss transform. This new scheme is robust, avoids geometrically-induced stiffness, and is easy to use in the presence of moving geometries. Its extension to three dimensions is natural and straightforward, and should permit layer heat potentials to become flexible and powerful tools for modeling diffusion processes.

The brain is a massive neuronal network, organized into anatomically distributed sub-circuits, with functionally relevant activity occurring at timescales ranging from milliseconds to years. Current methods to monitor neural activity, however, lack the necessary conjunction of anatomical spatial coverage, temporal resolution, and long-term stability to measure this distributed activity. Here we introduce a large-scale, multi-site, extracellular recording platform that integrates polymer electrodes with a modular stacking headstage design supporting up to 1,024 recording channels in freely behaving rats. This system can support months-long recordings from hundreds of well-isolated units across multiple brain regions. Moreover, these recordings are stable enough to track large numbers of single units for over a week. This platform enables large-scale electrophysiological interrogation of the fast dynamics and long-timescale evolution of anatomically distributed circuits, and thereby provides a new tool for understanding brain activity.

For smooth bounded domains in ℝn, we prove upper and lower L2 bounds on the boundary data of Neumann eigenfunctions, and we prove quasiorthogonality of this boundary data in a spectral window. The bounds are tight in the sense that both are independent of the eigenvalues; this is achieved by working with an appropriate norm for boundary functions, which includes a spectral weight, that is, a function of the boundary Laplacian. This spectral weight is chosen to cancel concentration at the boundary that can happen for whispering gallery-type eigenfunctions. These bounds are closely related to wave equation estimates due to Tataru. Using this, we bound the distance from an arbitrary Helmholtz parameter E>0 to the nearest Neumann eigenvalue in terms of boundary normal derivative data of a trial function u solving the Helmholtz equation (Δ−E)u=0. This inclusion bound improves over previously known bounds by a factor of E5/6, analogously to a recently improved inclusion bound in the Dirichlet case due to the first two authors. Finally, we apply our theory to present an improved numerical implementation of the method of particular solutions for computation of Neumann eigenpairs on smooth planar domains. We show that the new inclusion bound improves the relative accuracy in a computed Neumann eigenvalue (around the 42000th) from nine to fourteen digits, with negligible extra numerical effort.

Two fundamental difficulties are encountered in the numerical evaluation of time-dependent layer potentials. One is the quadratic cost of history dependence, which has been successfully addressed by splitting the potentials into two parts - a local part that contains the most recent contributions and a history part that contains the contributions from all earlier times. The history part is smooth, easily discretized using high-order quadratures, and straightforward to compute using a variety of fast algorithms. The local part, however, involves complicated singularities in the underlying Green's function. Existing methods, based on exchanging the order of integration in space and time, are able to achieve high order accuracy, but are limited to the case of stationary boundaries. Here, we present a new quadrature method that leaves the order of integration unchanged, making use of a change of variables that converts the singular integrals with respect to time into smooth ones. We have also derived asymptotic formulas for the local part that lead to fast and accurate hybrid schemes, extending earlier work for scalar heat potentials and applicable to moving boundaries. The performance of the overall scheme is demonstrated via numerical examples.

A variety of problems in acoustic and electromagnetic scattering require the evaluation of impedance or layered media Green's functions. Given a point source located in an unbounded half-space or an infinitely extended layer, Sommerfeld and others showed that Fourier analysis combined with contour integration provides a systematic and broadly effective approach, leading to what is generally referred to as the Sommerfeld integral representation. When either the source or target is at some distance from an infinite boundary, the number of degrees of freedom needed to resolve the scattering response is very modest. When both are near an interface, however, the Sommerfeld integral involves a very large range of integration and its direct application becomes unwieldy. Historically, three schemes have been employed to overcome this difficulty: the method of images, contour deformation, and asymptotic methods of various kinds. None of these methods make use of classical layer potentials in physical space, despite their advantages in terms of adaptive resolution and high-order accuracy. The reason for this is simple: layer potentials are impractical in layered media or half-space geometries since they require the discretization of an infinite boundary. In this paper, we propose a hybrid method which combines layer potentials (physical-space) on a finite portion of the interface together with a Sommerfeld-type (Fourier) correction. We prove that our method is efficient and rapidly convergent for arbitrarily located sources and targets, and show that the scheme is particularly effective when solving scattering problems for objects which are close to the half-space boundary or even embedded across a layered media interface.

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.

We present a collection of well-conditioned integral equation methods for the solution of electrostatic, acoustic or electromagnetic scattering problems involving anisotropic, inhomogeneous media. In the electromagnetic case, our approach involves a minor modification of a classical formulation. In the electrostatic or acoustic setting, we introduce a new vector partial differential equation, from which the desired solution is easily obtained. It is the vector equation for which we derive a well-conditioned integral equation. In addition to providing a unified framework for these solvers, we illustrate their performance using iterative solution methods coupled with the FFT-based technique of [1] to discretize and apply the relevant integral operators.

A variety of problems in computational physics and engineering require the convolution of the heat kernel (a Gaussian) with either discrete sources, densities supported on boundaries, or continuous volume distributions. We present a unified fast Gauss transform for this purpose in two dimensions, making use of an adaptive quad-tree discretization on a unit square which is assumed to contain all sources. Our implementation permits either free-space or periodic boundary conditions to be imposed, and is efficient for any choice of variance in the Gaussian.

We present a new method for the analysis of electromagnetic scattering from homogeneous penetrable bodies. Our approach is based on a reformulation of the governing Maxwell equations in terms of two uncoupled vector Helmholtz systems: one for the electric feld and one for the magnetic field. This permits the derivation of resonance-free Fredholm equations of the second kind that are stable at all frequencies, insensitive to the genus of the scatterers, and invertible for all passive materials including those with negative permittivities or permeabilities. We refer to these as decoupled field integral equations.