Search

Multiple scattering methods are widely used to reduce the computational complexity of acoustic or electromagnetic scattering problems when waves propagate through media containing many identical inclusions. Historically, this numerical technique has been limited to situations in which the inclusions (particles) can be covered by nonoverlapping disks in two dimensions or spheres in three dimensions. This allows for the use of separation of variables in cylindrical or spherical coordinates to represent the solution to the governing partial differential equation. Here, we provide a more flexible approach, applicable to a much larger class of geometries. We use a Green's representation formula and the associated layer potentials to construct incoming and outgoing solutions on rectangular enclosures. The performance and flexibility of the resulting scattering operator formulation in two-dimensions is demonstrated via several numerical examples for multi-particle scattering in free space as well as in layered media. The mathematical formalism extends directly to the three dimensional case as well, and can easily be coupled with several commercial numerical PDE software packages., Comment: 14 pages, 7 figures

In Chakraborti's yard-sale model of an economy, identical agents engage in pairwise trades, resulting in wealth exchanges that conserve each agent's expected wealth. Doob's martingale convergence theorem immediately implies almost sure wealth condensation, i.e., convergence to a state in which a single agent owns the entire economy. If some pairs of agents are not allowed to trade with each other, the martingale convergence theorem still implies local wealth condensation, i.e., convergence to a state in which some agents are wealthy, while all their trading partners are impoverished. In this note, we propose a new, more elementary proof of this result. Unlike the proof based on the martingale convergence theorem, our argument applies to models with a wealth-acquired advantage, and even to certain models with a poverty-acquired advantage., Comment: 8 pages, 1 figure

Low-Rank Adaptation (LoRA) is a widely-used parameter-efficient finetuning method for large language models. LoRA saves memory by training only low rank perturbations to selected weight matrices. In this work, we compare the performance of LoRA and full finetuning on two target domains, programming and mathematics. We consider both the instruction finetuning ($\approx$100K prompt-response pairs) and continued pretraining ($\approx$10B unstructured tokens) data regimes. Our results show that, in most settings, LoRA substantially underperforms full finetuning. Nevertheless, LoRA exhibits a desirable form of regularization: it better maintains the base model's performance on tasks outside the target domain. We show that LoRA provides stronger regularization compared to common techniques such as weight decay and dropout; it also helps maintain more diverse generations. We show that full finetuning learns perturbations with a rank that is 10-100X greater than typical LoRA configurations, possibly explaining some of the reported gaps. We conclude by proposing best practices for finetuning with LoRA.

Label bias occurs when the outcome of interest is not directly observable and instead modeling is performed with proxy labels. When the difference between the true outcome and the proxy label is correlated with predictors, this can yield systematic disparities in predictions for different groups of interest. We propose Bayesian hierarchical measurement models to address these issues. Through practical examples, we demonstrate how our approach improves accuracy and helps with algorithmic fairness.

We propose a simple approach for memory-efficient adaptation of pretrained language models. Our approach uses an iterative algorithm to decompose each pretrained matrix into a high-precision low-rank component and a memory-efficient quantized component. During finetuning, the quantized component remains fixed and only the low-rank component is updated. We present an integer linear programming formulation of the quantization component which enables dynamic configuration of quantization parameters (e.g., bit-width, block size) for each matrix given an overall target memory budget. We further explore a data-aware version of the algorithm which uses an approximation of the Fisher information matrix to weight the reconstruction objective during matrix decomposition. Experiments on finetuning RoBERTa and LLaMA-2 (7B and 70B) demonstrate that our low-rank plus quantized matrix decomposition approach (LQ-LoRA) outperforms strong QLoRA and GPTQ-LoRA baselines and enables aggressive quantization to sub-3 bits with only minor performance degradations. When finetuned on a language modeling calibration dataset, LQ-LoRA can also be used for model compression; in this setting our 2.75-bit LLaMA-2-70B model (which has 2.85 bits on average when including the low-rank components and requires 27GB of GPU memory) performs respectably compared to the 16-bit baseline.

In Chakraborti's yard-sale model of an economy, identical agents engage in trades that result in wealth exchanges, but conserve the combined wealth of all agents and each agent's expected wealth. In this model, wealth condensation, that is, convergence to a state in which one agent owns everything and the others own nothing, occurs almost surely. We give a proof of this fact that is much shorter than existing ones and extends to a modified model in which there is a wealth-acquired advantage, i.e., the wealthier of two trading partners is more likely to benefit from the trade., Comment: 5 pages

We introduce a new class of multilevel, adaptive, dual-space methods for computing fast convolutional transforms. These methods can be applied to a broad class of kernels, from the Green's functions for classical partial differential equations (PDEs) to power functions and radial basis functions such as those used in statistics and machine learning. The DMK (dual-space multilevel kernel-splitting) framework uses a hierarchy of grids, computing a smoothed interaction at the coarsest level, followed by a sequence of corrections at finer and finer scales until the problem is entirely local, at which point direct summation is applied. The main novelty of DMK is that the interaction at each scale is diagonalized by a short Fourier transform, permitting the use of separation of variables, but without requiring the FFT for its asymptotic performance. The DMK framework substantially simplifies the algorithmic structure of the fast multipole method (FMM) and unifies the FMM, Ewald summation, and multilevel summation, achieving speeds comparable to the FFT in work per gridpoint, even in a fully adaptive context. For continuous source distributions, the evaluation of local interactions is further accelerated by approximating the kernel at the finest level as a sum of Gaussians with a highly localized remainder. The Gaussian convolutions are calculated using tensor product transforms, and the remainder term is calculated using asymptotic methods. We illustrate the performance of DMK for both continuous and discrete sources with extensive numerical examples in two and three dimensions., Comment: 53 pages, 15 figures

Many integral equation-based methods are available for problems of time-harmonic electromagnetic scattering from perfect electric conductors. Moreover, there are numerous ways in which the geometry can be represented, numerous ways to represent the relevant surface current and/or charge densities, numerous quadrature methods that can be deployed, and numerous fast methods that can be used to accelerate the solution of the large linear systems which arise from discretization. Among the many issues that arise in such scattering calculations are the avoidance of spurious resonances, the applicability of the chosen method to scatterers of non-trivial topology, the robustness of the method when applied to objects with multiscale features, the stability of the method under mesh refinement, the ease of implementation with high-order basis functions, and the behavior of the method as the frequency tends to zero. Since three-dimensional scattering is a challenging, large-scale problem, many of these issues have been historically difficult to investigate. It is only with the advent of fast algorithms and modern iterative methods that a careful study of these issues can be carried out effectively. In this paper, we use GMRES as our iterative solver and the fast multipole method as our acceleration scheme in order to investigate some of these questions. In particular, we compare the behavior of the following integral equation formulations with regard to the issues noted above: the standard electric, magnetic, and combined field integral equations with standard RWG basis functions, the non-resonant charge-current integral equation, the electric charge-current integral equation, the augmented regularized combined source integral equation and the decoupled potential integral equation DPIE. Various numerical results are provided to demonstrate the behavior of each of these schemes., Comment: 27 pages, 9 figures

The high efficiency of a recently proposed method for computing with Gaussian processes relies on expanding a (translationally invariant) covariance kernel into complex exponentials, with frequencies lying on a Cartesian equispaced grid. Here we provide rigorous error bounds for this approximation for two popular kernels -- Mat\'ern and squared exponential -- in terms of the grid spacing and size. The kernel error bounds are uniform over a hypercube centered at the origin. Our tools include a split into aliasing and truncation errors, and bounds on sums of Gaussians or modified Bessel functions over various lattices. For the Mat\'ern case, motivated by numerical study, we conjecture a stronger Frobenius-norm bound on the covariance matrix error for randomly-distributed data points. Lastly, we prove bounds on, and study numerically, the ill-conditioning of the linear systems arising in such regression problems., Comment: arXiv admin note: substantial text overlap with arXiv:2210.10210

We present a new version of the fast Gauss transform (FGT) for discrete and continuous sources. Classical Hermite expansions are avoided entirely, making use only of the plane-wave representation of the Gaussian kernel and a new hierarchical merging scheme. For continuous source distributions sampled on adaptive tensor-product grids, we exploit the separable structure of the Gaussian kernel to accelerate the computation. For discrete sources, the scheme relies on the nonuniform fast Fourier transform (NUFFT) to construct near field plane wave representations. The scheme has been implemented for either free-space or periodic boundary conditions. In many regimes, the speed is comparable to or better than that of the conventional FFT in work per gridpoint, despite being fully adaptive., Comment: 26 pages, 10 figures

Bayesian Improved Surname Geocoding (BISG) is a ubiquitous tool for predicting race and ethnicity using an individual's geolocation and surname. Here we demonstrate that statistical dependence of surname and geolocation within racial/ethnic categories in the United States results in biases for minority subpopulations, and we introduce a raking-based improvement. Our method augments the data used by BISG--distributions of race by geolocation and race by surname--with the distribution of surname by geolocation obtained from state voter files. We validate our algorithm on state voter registration lists that contain self-identified race/ethnicity.

Scaling transformers has led to significant breakthroughs in many domains, leading to a paradigm in which larger versions of existing models are trained and released on a periodic basis. New instances of such models are typically trained completely from scratch, despite the fact that they are often just scaled-up versions of their smaller counterparts. How can we use the implicit knowledge in the parameters of smaller, extant models to enable faster training of newer, larger models? This paper describes an approach for accelerating transformer training by learning to grow pretrained transformers, where we learn to linearly map the parameters of the smaller model to initialize the larger model. For tractable learning, we factorize the linear transformation as a composition of (linear) width- and depth-growth operators, and further employ a Kronecker factorization of these growth operators to encode architectural knowledge. Extensive experiments across both language and vision transformers demonstrate that our learned Linear Growth Operator (LiGO) can save up to 50% computational cost of training from scratch, while also consistently outperforming strong baselines that also reuse smaller pretrained models to initialize larger models., Comment: International Conference on Learning Representations (ICLR), 2023

The canonical formulation of federated learning treats it as a distributed optimization problem where the model parameters are optimized against a global loss function that decomposes across client loss functions. A recent alternative formulation instead treats federated learning as a distributed inference problem, where the goal is to infer a global posterior from partitioned client data (Al-Shedivat et al., 2021). This paper extends the inference view and describes a variational inference formulation of federated learning where the goal is to find a global variational posterior that well-approximates the true posterior. This naturally motivates an expectation propagation approach to federated learning (FedEP), where approximations to the global posterior are iteratively refined through probabilistic message-passing between the central server and the clients. We conduct an extensive empirical study across various algorithmic considerations and describe practical strategies for scaling up expectation propagation to the modern federated setting. We apply FedEP on standard federated learning benchmarks and find that it outperforms strong baselines in terms of both convergence speed and accuracy.

We describe a new, adaptive solver for the two-dimensional Poisson equation in complicated geometries. Using classical potential theory, we represent the solution as the sum of a volume potential and a double layer potential. Rather than evaluating the volume potential over the given domain, we first extend the source data to a geometrically simpler region with high order accuracy. This allows us to accelerate the evaluation of the volume potential using an efficient, geometry-unaware fast multipole-based algorithm. To impose the desired boundary condition, it remains only to solve the Laplace equation with suitably modified boundary data. This is accomplished with existing fast and accurate boundary integral methods. The novelty of our solver is the scheme used for creating the source extension, assuming it is provided on an adaptive quad-tree. For leaf boxes intersected by the boundary, we construct a universal "stencil" and require that the data be provided at the subset of those points that lie within the domain interior. This universality permits us to precompute and store an interpolation matrix which is used to extrapolate the source data to an extended set of leaf nodes with full tensor-product grids on each. We demonstrate the method's speed, robustness and high-order convergence with several examples, including domains with piecewise smooth boundaries.

The formation of the large-scale structure, the evolution and distribution of galaxies, quasars, and dark matter on cosmological scales, requires numerical simulations. Differentiable simulations provide gradients of the cosmological parameters, that can accelerate the extraction of physical information from statistical analyses of observational data. The deep learning revolution has brought not only myriad powerful neural networks, but also breakthroughs including automatic differentiation (AD) tools and computational accelerators like GPUs, facilitating forward modeling of the Universe with differentiable simulations. Because AD needs to save the whole forward evolution history to backpropagate gradients, current differentiable cosmological simulations are limited by memory. Using the adjoint method, with reverse time integration to reconstruct the evolution history, we develop a differentiable cosmological particle-mesh (PM) simulation library pmwd (particle-mesh with derivatives) with a low memory cost. Based on the powerful AD library JAX, pmwd is fully differentiable, and is highly performant on GPUs., Comment: repo at https://github.com/eelregit/pmwd

Rapid advances in deep learning have brought not only myriad powerful neural networks, but also breakthroughs that benefit established scientific research. In particular, automatic differentiation (AD) tools and computational accelerators like GPUs have facilitated forward modeling of the Universe with differentiable simulations. Based on analytic or automatic backpropagation, current differentiable cosmological simulations are limited by memory, and thus are subject to a trade-off between time and space/mass resolution, usually sacrificing both. We present a new approach free of such constraints, using the adjoint method and reverse time integration. It enables larger and more accurate forward modeling at the field level, and will improve gradient based optimization and inference. We implement it in an open-source particle-mesh (PM) $N$-body library pmwd (particle-mesh with derivatives). Based on the powerful AD system JAX, pmwd is fully differentiable, and is highly performant on GPUs., Comment: 5 figures + 2 tables; repo at https://github.com/eelregit/pmwd ; v2 matches published version with better typesetting

The acoustic inverse obstacle scattering problem consists of determining the shape of a domain from measurements of the scattered far field due to some set of incident fields (probes). For a penetrable object with known sound speed, this can be accomplished by treating the boundary alone as an unknown curve. Alternatively, one can treat the entire object as unknown and use a more general volumetric representation, without making use of the known sound speed. Both lead to strongly nonlinear and nonconvex optimization problems for which recursive linearization provides a useful framework for numerical analysis. After extending our shape optimization approach developed earlier for impenetrable bodies, we carry out a systematic study of both methods and compare their performance on a variety of examples. Our findings indicate that the volumetric approach is more robust, even though the number of degrees of freedom is significantly larger. We conclude with a discussion of this phenomenon and potential directions for further research., Comment: 24 pages, 9 figures

We introduce a Fourier-based fast algorithm for Gaussian process regression in low dimensions. It approximates a translationally-invariant covariance kernel by complex exponentials on an equispaced Cartesian frequency grid of $M$ nodes. This results in a weight-space $M\times M$ system matrix with Toeplitz structure, which can thus be applied to a vector in ${\mathcal O}(M \log{M})$ operations via the fast Fourier transform (FFT), independent of the number of data points $N$. The linear system can be set up in ${\mathcal O}(N + M \log{M})$ operations using nonuniform FFTs. This enables efficient massive-scale regression via an iterative solver, even for kernels with fat-tailed spectral densities (large $M$). We provide bounds on both kernel approximation and posterior mean errors. Numerical experiments for squared-exponential and Mat\'ern kernels in one, two and three dimensions often show 1-2 orders of magnitude acceleration over state-of-the-art rank-structured solvers at comparable accuracy. Our method allows 2D Mat\'ern-$\mbox{$\frac{3}{2}$}$ regression from $N=10^9$ data points to be performed in 2 minutes on a standard desktop, with posterior mean accuracy $10^{-3}$. This opens up spatial statistics applications 100 times larger than previously possible.

We present an efficient method for propagating the time-dependent Kohn-Sham equations in free space, based on the recently introduced Fourier contour deformation (FCD) approach. For potentials which are constant outside a bounded domain, FCD yields a high-order accurate numerical solution of the time-dependent Schrodinger equation directly in free space, without the need for artificial boundary conditions. Of the many existing artificial boundary condition schemes, FCD is most similar to an exact nonlocal transparent boundary condition, but it works directly on Cartesian grids in any dimension, and runs on top of the fast Fourier transform rather than fast algorithms for the application of nonlocal history integral operators. We adapt FCD to time-dependent density functional theory (TDDFT), and describe a simple algorithm to smoothly and automatically truncate long-range Coulomb-like potentials to a time-dependent constant outside of a bounded domain of interest, so that FCD can be used. This approach eliminates errors originating from the use of artificial boundary conditions, leaving only the error of the potential truncation, which is controlled and can be systematically reduced. The method enables accurate simulations of ultrastrong nonlinear electronic processes in molecular complexes in which the inteference between bound and continuum states is of paramount importance. We demonstrate results for many-electron TDDFT calculations of absorption and strong field photoelectron spectra for one and two-dimensional models, and observe a significant reduction in the size of the computational domain required to achieve high quality results, as compared with the popular method of complex absorbing potentials.

Single particle cryo-electron microscopy has become a critical tool in structural biology over the last decade, able to achieve atomic scale resolution in three dimensional models from hundreds of thousands of (noisy) two-dimensional projection views of particles frozen at unknown orientations. This is accomplished by using a suite of software tools to (i) identify particles in large micrographs, (ii) obtain low-resolution reconstructions, (iii) refine those low-resolution structures, and (iv) finally match the obtained electron scattering density to the constituent atoms that make up the macromolecule or macromolecular complex of interest. Here, we focus on the second stage of the reconstruction pipeline: obtaining a low resolution model from picked particle images. Our goal is to create an algorithm that is capable of ab initio reconstruction from small data sets (on the order of a few thousand selected particles). More precisely, we propose an algorithm that is robust, automatic, and fast enough that it can potentially be used to assist in the assessment of particle quality as the data is being generated during the microscopy experiment., Comment: 43 pages, 15 figures

This paper studies the problem of computing a linear approximation of quadratic Wasserstein distance $W_2$. In particular, we compute an approximation of the negative homogeneous weighted Sobolev norm whose connection to Wasserstein distance follows from a classic linearization of a general Monge-Amp\'ere equation. Our contribution is threefold. First, we provide expository material on this classic linearization of Wasserstein distance including a quantitative error estimate. Second, we reduce the computational problem to solving an elliptic boundary value problem involving the Witten Laplacian, which is a Schr\"odinger operator of the form $H = -\Delta + V$, and describe an associated embedding. Third, for the case of probability distributions on the unit square $[0,1]^2$ represented by $n \times n$ arrays we present a fast code demonstrating our approach. Several numerical examples are presented., Comment: 24 pages, 6 figures

We present a fast direct solver for boundary integral equations on complex surfaces in three dimensions using an extension of the recently introduced recursive strong skeletonization scheme. For problems that are not highly oscillatory, our algorithm computes an ${LU}$-like hierarchical factorization of the dense system matrix, permitting application of the inverse in $\mathcal O(n)$ time, where $n$ is the number of unknowns on the surface. The factorization itself also scales linearly with the system size, albeit with a somewhat larger constant. The scheme is built on a level-restricted adaptive octree data structure, and therefore it is compatible with highly nonuniform discretizations. Furthermore, the scheme is coupled with high-order accurate locally-corrected Nystr\"om quadrature methods to integrate the singular and weakly-singular Green's functions used in the integral representations. Our method has immediate applications to a variety of problems in computational physics. We concentrate here on studying its performance in acoustic scattering (governed by the Helmholtz equation) at low to moderate frequencies, and provide rigorous justification for compression of submatrices via proxy surfaces.

A new scheme is presented for imposing periodic boundary conditions on unit cells with arbitrary source distributions. We restrict our attention here to the Poisson, modified Helmholtz, Stokes and modified Stokes equations. The approach extends to the oscillatory equations of mathematical physics, including the Helmholtz and Maxwell equations, but we will address these in a companion paper, since the nature of the problem is somewhat different and includes the consideration of quasiperiodic boundary conditions and resonances. Unlike lattice sum-based methods, the scheme is insensitive to the unit cell's aspect ratio and is easily coupled to adaptive fast multipole methods (FMMs). Our analysis relies on classical "plane-wave" representations of the fundamental solution, and yields an explicit low-rank representation of the field due to all image sources beyond the first layer of neighboring unit cells. When the aspect ratio of the unit cell is large, our scheme can be coupled with the nonuniform fast Fourier transform (NUFFT) to accelerate the evaluation of the induced field. Its performance is illustrated with several numerial examples., Comment: 46 pages, 5 figures

We describe a class of algorithms for evaluating posterior moments of certain Bayesian linear regression models with a normal likelihood and a normal prior on the regression coefficients. The proposed methods can be used for hierarchical mixed effects models with partial pooling over one group of predictors, as well as random effects models with partial pooling over two groups of predictors. We demonstrate the performance of the methods on two applications, one involving U.S. opinion polls and one involving the modeling of COVID-19 outbreaks in Israel using survey data. The algorithms involve analytical marginalization of regression coefficients followed by numerical integration of the remaining low-dimensional density. The dominant cost of the algorithms is an eigendecomposition computed once for each value of the outside parameter of integration. Our approach drastically reduces run times compared to state-of-the-art Markov chain Monte Carlo (MCMC) algorithms. The latter, in addition to being computationally expensive, can also be difficult to tune when applied to hierarchical models.

We introduce a class of algorithms for constructing Fourier representations of Gaussian processes in $1$ dimension that are valid over ranges of hyperparameter values. The scaling and frequencies of the Fourier basis functions are evaluated numerically via generalized quadratures. The representations introduced allow for $O(m^3)$ inference, independent of $N$, for all hyperparameters in the user-specified range after $O(N + m^2\log{m})$ precomputation where $N$, the number of data points, is usually significantly larger than $m$, the number of basis functions. Inference independent of $N$ for various hyperparameters is facilitated by generalized quadratures, and the $O(N + m^2\log{m})$ precomputation is achieved with the non-uniform FFT. Numerical results are provided for Mat\'ern kernels with $\nu \in [3/2, 7/2]$ and lengthscale $\rho \in [0.1, 0.5]$ and squared-exponential kernels with lengthscale $\rho \in [0.1, 0.5]$. The algorithms of this paper generalize mathematically to higher dimensions, though they suffer from the standard curse of dimensionality.

In this work we introduce a reduced-rank algorithm for Gaussian process regression. Our numerical scheme converts a Gaussian process on a user-specified interval to its Karhunen-Lo\`eve expansion, the $L^2$-optimal reduced-rank representation. Numerical evaluation of the Karhunen-Lo\`eve expansion is performed once during precomputation and involves computing a numerical eigendecomposition of an integral operator whose kernel is the covariance function of the Gaussian process. The Karhunen-Lo\`eve expansion is independent of observed data and depends only on the covariance kernel and the size of the interval on which the Gaussian process is defined. The scheme of this paper does not require translation invariance of the covariance kernel. We also introduce a class of fast algorithms for Bayesian fitting of hyperparameters, and demonstrate the performance of our algorithms with numerical experiments in one and two dimensions. Extensions to higher dimensions are mathematically straightforward but suffer from the standard curses of high dimensions.

In some scientific fields, it is common to have certain variables of interest that are of particular importance and for which there are many studies indicating a relationship with different explanatory variables. In such cases, particularly those where no relationships are known among the explanatory variables, it is worth asking under what conditions it is possible for all such claimed effects to exist simultaneously. This paper addresses this question by reviewing some theorems from multivariate analysis showing that, unless the explanatory variables also have sizable dependencies with each other, it is impossible to have many such large effects. We discuss implications for the replication crisis in social science.

We develop a fast method for computing the electrostatic energy and forces for a collection of charges in doubly-periodic slabs with jumps in the dielectric permittivity at the slab boundaries. Our method achieves spectral accuracy by using Ewald splitting to replace the original Poisson equation for nearly-singular sources with a smooth far-field Poisson equation, combined with a localized near-field correction. Unlike existing spectral Ewald methods, which make use of the Fourier transform in the aperiodic direction, we recast the problem as a two-point boundary value problem in the aperiodic direction for each transverse Fourier mode, for which exact analytic boundary conditions are available. We solve each of these boundary value problems using a fast, well-conditioned Chebyshev method. In the presence of dielectric jumps, combining Ewald splitting with the classical method of images results in smoothed charge distributions which overlap the dielectric boundaries themselves. We show how to preserve spectral accuracy in this case through the use of a harmonic correction which involves solving a simple Laplace equation with smooth boundary data. We implement our method on Graphical Processing Units, and combine our doubly-periodic Poisson solver with Brownian Dynamics to study the equilibrium structure of double layers in binary electrolytes confined by dielectric boundaries. Consistent with prior studies, we find strong charge depletion near the interfaces due to repulsive interactions with image charges, which points to the need for incorporating polarization effects in understanding confined electrolytes, both theoretically and computationally., Comment: 60 pages, 7 figures

We describe a numerical scheme for evaluating the posterior moments of Bayesian linear regression models with partial pooling of the coefficients. The principal analytical tool of the evaluation is a change of basis from coefficient space to the space of singular vectors of the matrix of predictors. After this change of basis and an analytical integration, we reduce the problem of finding moments of a density over k + m dimensions, to finding moments of an m-dimensional density, where k is the number of coefficients and k + m is the dimension of the posterior. Moments can then be computed using, for example, MCMC, the trapezoid rule, or adaptive Gaussian quadrature. An evaluation of the SVD of the matrix of predictors is the dominant computational cost and is performed once during the precomputation stage. We demonstrate numerical results of the algorithm. The scheme described in this paper generalizes naturally to multilevel and multi-group hierarchical regression models where normal-normal parameters appear.

While fast multipole methods (FMMs) are in widespread use for the rapid evaluation of potential fields governed by the Laplace, Helmholtz, Maxwell or Stokes equations, their coupling to high-order quadratures for evaluating layer potentials is still an area of active research. In three dimensions, a number of issues need to be addressed, including the specification of the surface as the union of high-order patches, the incorporation of accurate quadrature rules for integrating singular or weakly singular Green's functions on such patches, and their coupling to the oct-tree data structures on which the FMM separates near and far field interactions. Although the latter is straightforward for point distributions, the near field for a patch is determined by its physical dimensions, not the distribution of discretization points on the surface. Here, we present a general framework for efficiently coupling locally corrected quadratures with FMMs, relying primarily on what are called generalized Gaussian quadratures rules, supplemented by adaptive integration. The approach, however, is quite general and easily applicable to other schemes, such as Quadrature by Expansion (QBX). We also introduce a number of accelerations to reduce the cost of quadrature generation itself, and present several numerical examples of acoustic scattering that demonstrate the accuracy, robustness, and computational efficiency of the scheme. On a single core of an Intel i5 2.3GHz processor, a Fortran implementation of the scheme can generate near field quadrature corrections for between 1000 and 10,000 points per second, depending on the order of accuracy and the desired precision. A Fortran implementation of the algorithm described in this work is available at https://gitlab.com/fastalgorithms/fmm3dbie.

In coherent diffraction imaging (CDI) experiments, the intensity of the scattered wave impinging on an object is measured on an array of detectors. This signal can be interpreted as the square of the modulus of the Fourier transform of the unknown scattering density. A beam-stop obstructs the forward scattered wave and, hence, the modulus Fourier data from a neighborhood of k=0 cannot be measured. In this note, we describe a linear method for recovering this unmeasured modulus Fourier data from the measured values and an estimate of the support of the image's autocorrelation function without consideration of phase retrieval. We analyze the conditioning of this problem, which grows exponentially with the modulus of the maximum spatial frequency not measured, and the effects of noise., Comment: Version 2 is a substantial revision with a stronger focus on the conditioning of our algorithm

We introduce a numerical method for the solution of the time-dependent Schrodinger equation with a smooth potential, based on its reformulation as a Volterra integral equation. We present versions of the method both for periodic boundary conditions, and for free space problems with compactly supported initial data and potential. A spatially uniform electric field may be included, making the solver applicable to simulations of light-matter interaction. The primary computational challenge in using the Volterra formulation is the application of a space-time history dependent integral operator. This may be accomplished by projecting the solution onto a set of Fourier modes, and updating their coefficients from one time step to the next by a simple recurrence. In the periodic case, the modes are those of the usual Fourier series, and the fast Fourier transform (FFT) is used to alternate between physical and frequency domain grids. In the free space case, the oscillatory behavior of the spectral Green's function leads us to use a set of complex-frequency Fourier modes obtained by discretizing a contour deformation of the inverse Fourier transform, and we develop a corresponding fast transform based on the FFT. Our approach is related to pseudo-spectral methods, but applied to an integral rather than the usual differential formulation. This has several advantages: it avoids the need for artificial boundary conditions, admits simple, inexpensive high-order implicit time marching schemes, and naturally includes time-dependent potentials. We present examples in one and two dimensions showing spectral accuracy in space and eighth-order accuracy in time for both periodic and free space problems., Comment: 38 pages, 11 figures

We present a family of integral equation-based solvers for the linear or semilinear heat equation in complicated moving (or stationary) geometries. This approach has significant advantages over more standard finite element or finite difference methods in terms of accuracy, stability and space-time adaptivity. In order to be practical, however, a number of technical capabilites are required: fast algorithms for the evaluation of heat potentials, high-order accurate quadratures for singular and weakly integrals over space-time domains, and robust automatic mesh refinement and coarsening capabilities. We describe all of these components and illustrate the performance of the approach with numerical examples in two space dimensions., Comment: 53 pages, 9 figures

In this work we present an algorithm to construct an infinitely differentiable smooth surface from an input consisting of a (rectilinear) triangulation of a surface of arbitrary shape. The original surface can have non-trivial genus and multiscale features, and our algorithm has computational complexity which is linear in the number of input triangles. We use a smoothing kernel to define a function $\Phi$ whose level set defines the surface of interest. Charts are subsequently generated as maps from the original user-specified triangles to $\mathbb R^3$. The degree of smoothness is controlled locally by the kernel to be commensurate with the fineness of the input triangulation. The expression for~$\Phi$ can be transformed into a boundary integral, whose evaluation can be accelerated using a fast multipole method. We demonstrate the effectiveness and cost of the algorithm with polyhedral and quadratic skeleton surfaces obtained from CAD and meshing software.

We present an efficient method to solve the narrow capture and narrow escape problems for the sphere. The narrow capture problem models the equilibrium behavior of a Brownian particle in the exterior of a sphere whose surface is reflective, except for a collection of small absorbing patches. The narrow escape problem is the dual problem: it models the behavior of a Brownian particle confined to the interior of a sphere whose surface is reflective, except for a collection of small patches through which it can escape. Mathematically, these give rise to mixed Dirichlet/Neumann boundary value problems of the Poisson equation. They are numerically challenging for two main reasons: (1) the solutions are non-smooth at Dirichlet-Neumann interfaces, and (2) they involve adaptive mesh refinement and the solution of large, ill-conditioned linear systems when the number of small patches is large. By using the Neumann Green's functions for the sphere, we recast each boundary value problem as a system of first-kind integral equations on the collection of patches. A block-diagonal preconditioner together with a multiple scattering formalism leads to a well-conditioned system of second-kind integral equations and a very efficient approach to discretization. This system is solved iteratively using GMRES. We develop a hierarchical, fast multipole method-like algorithm to accelerate each matrix-vector product. Our method is insensitive to the patch size, and the total cost scales with the number N of patches as O(N log N), after a precomputation whose cost depends only on the patch size and not on the number or arrangement of patches. We demonstrate the method with several numerical examples, and are able to achieve highly accurate solutions with 100,000 patches in one hour on a 60-core workstation., Comment: 29 pages, 11 figures

We develop a high-order, explicit method for acoustic scattering in three space dimensions based on a combined-field time-domain integral equation. The spatial discretization, of Nystr\"om type, uses Gaussian quadrature on panels combined with a special treatment of the weakly singular kernels arising in near-neighbor interactions. In time, a new class of convolution splines is used in a predictor-corrector algorithm. Experiments on a torus and a perturbed torus are used to explore the stability and accuracy of the proposed scheme. This involved around one thousand solver runs, at up to 8th order and up to around 20,000 spatial unknowns, demonstrating 5-9 digits of accuracy. In addition we show that parameters in the combined field formulation, chosen on the basis of analysis for the sphere and other convex scatterers, work well in these cases., Comment: 24 pages, 10 figures

Many physical and biological processes are modeled by "particles" undergoing L\'evy random walks. A feature of significant interest in these systems is the mean square displacement (MSD) of the particles. Long-time asymptotic approximations of the MSD have been established, via the Tauberian Theorem, for systems in which the distribution of the step durations is asymptotically a power law of infinite variance. We extend these results, using elementary analysis, and obtain closed-form expressions as well as power law bounds for the MSD in equilibrium, and representations of the MSD as sums of super-linear, linear, and sub-linear terms. We show that the super-linear components are determined by the mean and asymptotics of the step durations, but that the linear and sub-linear components (whose size has implications for the accuracy of the asymptotic approximation) depend on the entire distribution function., Comment: 21 pages

We study the stability properties of explicit marching schemes for second-kind Volterra integral equations that arise when solving boundary value problems for the heat equation by means of potential theory. It is well known that explicit finite difference or finite element schemes for the heat equation are stable only if the time step $\Delta t$ is of the order $O(\Delta x^2)$, where $\Delta x$ is the finest spatial grid spacing. In contrast, for the Dirichlet and Neumann problems on the unit ball in all dimensions $d\ge 1$, we show that the simplest Volterra marching scheme, i.e., the forward Euler scheme, is unconditionally stable. Our proof is based on an explicit spectral radius bound of the marching matrix, leading to an estimate that an $L^2$-norm of the solution to the integral equation is bounded by $c_dT^{d/2}$ times the norm of the right hand side. For the Robin problem on the half space in any dimension, with constant Robin (heat transfer) coefficient $\kappa$, we exhibit a constant $C$ such that the forward Euler scheme is stable if $\Delta t < C/\kappa^2$, independent of any spatial discretization. This relies on new lower bounds on the spectrum of real symmetric Toeplitz matrices defined by convex sequences. Finally, we show that the forward Euler scheme is unconditionally stable for the Dirichlet problem on any smooth convex domain in any dimension, in $L^\infty$-norm., Comment: 37 pages

We consider the problem of constructing transparent boundary conditions for the time-dependent Schr\"odinger equation with a compactly supported binding potential and, if desired, a spatially uniform, time-dependent electromagnetic vector potential. Such conditions prevent nonphysical boundary effects from corrupting a numerical solution in a bounded computational domain. We use ideas from potential theory to build exact nonlocal conditions for arbitrary piecewise-smooth domains. These generalize the standard Dirichlet-to-Neumann and Neumann-to-Dirichlet maps known for the equation in one dimension without a vector potential. When the vector potential is included, the condition becomes non-convolutional in time. For the one-dimensional problem, we propose a simple discretization scheme and a fast algorithm to accelerate the evaluation of the boundary condition., Comment: 12 pages, 3 figures

Generalized prolate spheroidal functions (GPSFs) arise naturally in the study of bandlimited functions as the eigenfunctions of a certain truncated Fourier transform. In one dimension, the theory of GPSFs (typically referred to as prolate spheroidal wave functions) has a long history and is fairly complete. Furthermore, more recent work has led to the development of numerical algorithms for their computation and use in applications. In this paper we consider the more general problem, extending the one dimensional analysis and algorithms to the case of arbitrary dimension. Specifically, we introduce algorithms for efficient evaluation of GPSFs and their corresponding eigenvalues, quadrature rules for bandlimited functions, formulae for interpolation via GPSF expansion, and various analytical properties of GPSFs. We illustrate the numerical and analytical results with several numerical examples.

Zernike polynomials are a basis of orthogonal polynomials on the unit disk that are a natural basis for representing smooth functions. They arise in a number of applications including optics and atmospheric sciences. In this paper, we provide a self-contained reference on Zernike polynomials, algorithms for evaluating them, and what appear to be new numerical schemes for quadrature and interpolation. We also introduce new properties of Zernike polynomials in higher dimensions. The quadrature rule and interpolation scheme use a tensor product of equispaced nodes in the angular direction and roots of certain Jacobi polynomials in the radial direction. An algorithm for finding the roots of these Jacobi polynomials is also described. The performance of the interpolation and quadrature schemes is illustrated through numerical experiments. Discussions of higher dimensional Zernike polynomials are included in appendices.

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.