Efficient sum-of-exponentials approximations for the heat kernel and their applications

DOI10.1007/S10444-014-9372-1zbMATH Open1318.31010arXiv1308.3883OpenAlexW1963803459MaRDI QIDQ2355178FDOQ2355178

Authors: Shidong Jiang, Shaobo Wang, Leslie Greengard 

Publication date: 21 July 2015

Published in: Advances in Computational Mathematics (Search for Journal in Brave)

Abstract: In this paper, we show that efficient separated sum-of-exponentials approximations can be constructed for the heat kernel in any dimension. In one space dimension, the heat kernel admits an approximation involving a number of terms that is of the order $O(log(fracTdelta)(log(frac1epsilon)+loglog(fracTdelta)))$ for any $$ and $deltaleqtleqT$, where $epsilon$ is the desired precision. In all higher dimensions, the corresponding heat kernel admits an approximation involving only $O(lo{g}^2(fracTdelta))$ terms for fixed accuracy $epsilon$. These approximations can be used to accelerate integral equation-based methods for boundary value problems governed by the heat equation in complex geometry. The resulting algorithms are nearly optimal. For $N_S$ points in the spatial discretization and $N_T$ time steps, the cost is $O(N_S{N}_{T}lo{g}^{2}fracTdelta)$ in terms of both memory and CPU time for fixed accuracy $epsilon$. The algorithms can be parallelized in a straightforward manner. Several numerical examples are presented to illustrate the accuracy and stability of these approximations.

Full work available at URL: https://arxiv.org/abs/1308.3883

Recommendations

• scientific article; zbMATH DE number 5785741
• A kernel-independent sum-of-exponentials method
• Heat kernels, smoothness estimates, and exponential decay
• scientific article; zbMATH DE number 4042897
• scientific article; zbMATH DE number 1583954
• A Mellin transform technique for the heat kernel expansion
• scientific article; zbMATH DE number 956708
• scientific article; zbMATH DE number 1028743
• scientific article; zbMATH DE number 1064913
• Heat kernel expansions for distributional backgrounds

zbMATH Keywords

heat kernelinverse Laplace transformsum-of-exponentials approximation

Mathematics Subject Classification ID

General theory of numerical methods in complex analysis (potential theory, etc.) (65E05) Connections of harmonic functions with differential equations in higher dimensions (31B35) Heat kernel (35K08) Approximation in the complex plane (30E10) Asymptotic representations in the complex plane (30E15)

Cites Work

• Data-sparse approximation by adaptive \({\mathcal H}^2\)-matrices
• A nonlinear optimization procedure for generalized Gaussian quadratures
• On the efficient computation of high-dimensional integrals and the approximation by exponential sums
• Generalized Gaussian Quadrature Rules for Systems of Arbitrary Functions
• Approximation of 1/x by exponential sums in [1, ∞)
• Title not available (Why is that?)
• On generalized Gaussian quadratures for exponentials and their applications
• Approximation by exponential sums revisited
• On approximation of functions by exponential sums
• Linear integral equations.
• Talbot quadratures and rational approximations
• Hybrid Gauss-Trapezoidal Quadrature Rules
• Title not available (Why is that?)
• A kernel-independent adaptive fast multipole algorithm in two and three dimensions
• On the numerical inversion of the Laplace transform of certain holomorphic mappings
• Title not available (Why is that?)
• A Spectral Order Method for Inverting Sectorial Laplace Transforms
• The Accurate Numerical Inversion of Laplace Transforms
• A fast adaptive multipole algorithm in three dimensions
• Numerical Methods Based on Whittaker Cardinal, or Sinc Functions
• Title not available (Why is that?)
• Spectral approximation of the free-space heat kernel
• High order accurate methods for the evaluation of layer heat potentials
• Adaptive, Fast, and Oblivious Convolution in Evolution Equations with Memory
• Fast Convolution for Nonreflecting Boundary Conditions
• A fast direct solver for structured linear systems by recursive skeletonization
• Efficient representation of nonreflecting boundary conditions for the time‐dependent Schrödinger equation in two dimensions
• A Fast Solver for HSS Representations via Sparse Matrices
• Fast and Oblivious Convolution Quadrature
• A fast algorithm for the evaluation of heat potentials
• A direct solver with \(O(N)\) complexity for integral equations on one-dimensional domains
• Nonreflecting boundary conditions for the time-dependent wave equation
• A fast method for solving the heat equation by layer potentials
• Approximations via Whittaker's cardinal function
• Rothe's method for the heat equation and boundary integral equations
• Integral equation methods for unsteady Stokes flow in two dimensions
• Rapid Evaluation of Nonreflecting Boundary Kernels for Time-Domain Wave Propagation
• Fast evaluation of nonreflecting boundary conditions for the Schrödinger equation in one dimension
• An Improved Fast Multipole Algorithm for Potential Fields on the Line
• On the numerical solution of the heat equation. I: Fast solvers in free space
• Crystal growth and dendritic solidification
• Numerical Simulations of Unsteady Crystal Growth
• A bootstrap method for sum-of-poles approximations
• Title not available (Why is that?)
• An efficient direct BEM numerical scheme for phase change problems using Fourier series
• Boundary integral solutions of the heat equation

Cited In (18)

• Two-dimensional finite element method solution of a class of integro-differential equations: application to non-Fickian transport in disordered media
• Several effective algorithms for nonlinear time fractional models
• A fast, high-order numerical method for the simulation of single-excitation states in quantum optics
• Fast high-order integral equation methods for solving boundary value problems of two dimensional heat equation in complex geometry
• On an approach for evaluating certain trigonometric character sums using the discrete time heat kernel
• Long time numerical behaviors of fractional pantograph equations
• A fast time domain solver for the equilibrium Dyson equation
• A kernel-independent sum-of-exponentials method
• Method of lines transpose: high order L-stable \(\mathcal O(N)\) schemes for parabolic equations using successive convolution
• Approximating the Gaussian as a sum of exponentials and its applications to the fast Gauss transform
• Approximation by exponential sums revisited
• Fast Evaluation of the Caputo Fractional Derivative and its Applications to Fractional Diffusion Equations
• Numerical approximation and fast evaluation of the overdamped generalized Langevin equation with fractional noise
• How much can one learn a partial differential equation from its solution?
• Numerical methods for fractional partial differential equations
• Integral formulation of Klein-Gordon singular waveguides
• Artificial boundary conditions for the semi-discretized one-dimensional nonlocal Schrödinger equation
• Fast \(\theta\)-Maruyama scheme for stochastic Volterra integral equations of convolution type: mean-square stability and strong convergence analysis

This page was built for publication: Efficient sum-of-exponentials approximations for the heat kernel and their applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2355178)