Search

By using Poisson's summation formula, we calculate periodic integrals over Gaussian basis functions by partitioning the lattice summations between the real and reciprocal space, where both sums converge exponentially fast with a large exponent. We demonstrate that the summation can be performed efficiently to calculate two-center Gaussian integrals over various kernels including overlap, kinetic, and Coulomb. The summation in real space is performed using an efficient flavor of the McMurchie-Davidson recurrence relation. The expressions for performing summation in the reciprocal space are also derived and implemented. The algorithm for reciprocal space summation allows us to reuse several terms and leads to a significant improvement in efficiency when highly contracted basis functions with large exponents are used. We find that the resulting algorithm is only between a factor of 5 and 15 slower than that for molecular integrals, indicating the very small number of terms needed in both the real and reciprocal space summations. An outline of the algorithm for calculating three-center Coulomb integrals is also provided.

We construct high-order derivative operators for smooth functions represented via discontinuous multiwavelet bases. The need for such operators arises in order to avoid artifacts when computing functionals involving high-order derivatives of solutions of integral equations. Previously high-order derivatives had to be formed by repeated application of a first-derivative operator that, while uniquely defined, has a spectral norm that grows quadratically with polynomial order and, hence, greatly amplifies numerical noise (truncation error) in the multiwavelet computation. The new constructions proceed via least-squares projection onto smooth bases and provide substantially improved numerical properties as well as permitting direct construction of high-order derivatives. We employ either b-splines or bandlimited exponentials as the intermediate smooth basis, with the former maintaining the concept of approximation order while the latter preserves the pure imaginary spectrum of the first-derivative operator and provides more direct control over the bandlimit and accuracy of computation. We demonstrate the properties of these new operators via several numerical tests as well as application to a problem in nuclear physics. Keywords: Multiwavelets, Multiresolution, Derivatives, Numerical, Discontinuous, Bandlimited exponentials

We present a new adaptive method for electronic structure calculations based on novel fast algorithms for reduction of multivariate mixtures. In our calculations, spatial orbitals are maintained as Gaussian mixtures whose terms are selected in the process of solving equations. Using a fixed basis leads to the so-called basis error since orbitals may not lie entirely within the linear span of the basis. To avoid such an error, multiresolution bases are used in adaptive algorithms so that basis functions are selected from a fixed collection of functions, large enough to approximate solutions within any user-selected accuracy. Our new method achieves adaptivity without using a multiresolution basis. Instead, as part of an iteration to solve nonlinear equations, our algorithm selects the ‘best’ subset of linearly independent terms of a Gaussian mixture from a collection that is much larger than any possible basis since the locations and shapes of the Gaussian terms are not fixed in advance. Approximating an orbital within a given accuracy, our algorithm yields significantly fewer terms than methods using multiresolution bases. We demonstrate our approach by solving the Hartree–Fock equations for two diatomic molecules, HeH + and LiH, matching the accuracy previously obtained using multiwavelet bases.

The standard particle-in-cell algorithm suffers from grid heating. There exists a gridless alternative which bypasses the deposition step and calculates each Fourier mode of the charge density directly from the particle positions. We show that a gridless method can be computed efficiently through the use of an Unequally Spaced Fast Fourier Transform (USFFT) algorithm. After a spectral field solve, the forces on the particles are calculated via the inverse USFFT (a rapid solution of an approximate linear system). We provide one and two dimensional implementations of this algorithm with an asymptotic runtime of $O(N_p + N_m^D \log N_m^D)$ for each iteration, identical to the standard PIC algorithm (where $N_p$ is the number of particles and $N_m$ is the number of Fourier modes, and $D$ is the spatial dimensionality of the problem) We demonstrate superior energy conservation and reduced noise, as well as convergence of the energy conservation at small time steps., 17 pages, 12 figures

We introduce a new approximate multiresolution analysis (MRA) using a single Gaussian as the scaling function, which we call Gaussian MRA (GMRA). As an initial application, we employ this new tool to accurately and efficiently compute the probability density function (PDF) of the product of independent random variables. In contrast with Monte-Carlo (MC) type methods (the only other universal approach known to address this problem), our method not only achieves accuracies beyond the reach of MC but also produces a PDF expressed as a Gaussian mixture, thus allowing for further efficient computations. We also show that an exact MRA corresponding to our GMRA can be constructed for a matching user-selected accuracy.

This paper introduces a randomized variation of the alternating least squares (ALS) algorithm for rank reduction of canonical tensor formats. The aim is to address the potential numerical ill-conditioning of least squares matrices at each ALS iteration. The proposed algorithm, dubbed randomized ALS, mitigates large condition numbers via projections onto random tensors, a technique inspired by well-established randomized projection methods for solving overdetermined least squares problems in a matrix setting. A probabilistic bound on the condition numbers of the randomized ALS matrices is provided, demonstrating reductions relative to their standard counterparts. Additionally, results are provided that guarantee comparable accuracy of the randomized ALS solution at each iteration. The performance of the randomized algorithm is studied with three examples, including manufactured tensors and an elliptic PDE with random inputs. In particular, for the latter, tests illustrate not only improvements in condition numbers, but also improved accuracy of the iterative solver for the PDE solution represented in a canonical tensor format.

International audience; no abstract

The wavefunction for the multiparticle Schr\"odinger equation is a function of many variables and satisfies an antisymmetry condition, so it is natural to approximate it as a sum of Slater determinants. Many current methods do so, but they impose additional structural constraints on the determinants, such as orthogonality between orbitals or an excitation pattern. We present a method without any such constraints, by which we hope to obtain much more efficient expansions, and insight into the inherent structure of the wavefunction. We use an integral formulation of the problem, a Green's function iteration, and a fitting procedure based on the computational paradigm of separated representations. The core procedure is the construction and solution of a matrix-integral system derived from antisymmetric inner products involving the potential operators. We show how to construct and solve this system with computational complexity competitive with current methods., Comment: 30 pages

International audience; Nearly every numerical analysis algorithm has computational complexity that scales exponentially in the underlying physical dimension. The separated representation, introduced previously , allows many operations to be performed with scaling that is formally linear in the dimension. In this paper we further develop this representation by (i) discussing the variety of mechanisms that allow it to be surprisingly efficient; (ii) addressing the issue of conditioning; (iii) presenting algorithms for solving linear systems within this framework; and (iv) demonstrating methods for dealing with antisymmetric functions, as arise in the multiparticle Schrödinger equation in quantum mechanics. Numerical examples are given.

We revisit the efficient approximation of functions by sums of exponentials or Gaussians in Beylkin and Monzon (2005) [16] to discuss several new results and applications of these approximations. By using the Poisson summation to discretize integral representations of e.g., power functions r − β , β > 0 , we obtain approximations with uniform relative error on the whole real line. Our approach is applicable to a class of functions and, in particular, yields a separated representation for the function e − x y . As a result, we obtain sharper error estimates and a simpler method to derive trapezoidal-type quadratures valid on finite intervals. We also introduce a new reduction algorithm for the case where our representation has an excessive number of terms with small exponents. As an application of these new estimates, we simplify and improve previous results on separated representations of operators with radial kernels. For any finite but arbitrary accuracy, we obtain new separated representations of solutions of Laplace's equation satisfying boundary conditions on the half-space or the sphere. These representations inherit a multiresolution structure from the Gaussian approximation leading to fast algorithms for the evaluation of the solutions. In the case of the sphere, our approach provides a foundation for a new multiresolution approach to evaluating and estimating models of gravitational potentials used for satellite orbit computations.

We present a simple algorithm for the factored polynomial (Finite Impulse Response, FIR) approximation of rational (Infinite Impulse Response, IIR) filters which may be used to construct inverse filters. When applied to quadrature mirror filters, our approach yields a simple way of generating an efficient FIR filter bank which inherits the properties of IIR filter bank with any desired accuracy.

We present a fast, adaptive multiresolution algorithm for applying integral operators with a wide class of radially symmetric kernels in dimensions one, two and three. This algorithm is made efficient by the use of separated representations of the kernel. We discuss operators of the class $(-\Delta+\mu^{2}I)^{-\alpha}$, where $\mu\geq0$ and $0, Comment: 37 pages, 7 figures. Revised version (reorganized for clarity) accepted for publication, Appl. Comput. Harmon. Anal

We introduce a new approach, and associated algorithms, for the efficient approximation of functions and sequences by short linear combinations of exponential functions with complex-valued exponents and coefficients. These approximations are obtained for a finite but arbitrary accuracy and typically have significantly fewer terms than Fourier representations. We present several examples of these approximations and discuss applications to fast algorithms. In particular, we show how to obtain a short separated representation (sum of products of one-dimensional functions) of certain multi-dimensional Green's functions.