Fast one-dimensional convolution with general kernels using sum-of-exponential approximation

Yong Zhang, Chijie Zhuang, Shidong Jiang

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

Abstract

Based on the recently-developed sum-of-exponential (SOE) approximation, in this article, we propose a fast algorithm to evaluate the one-dimensional convolution potential φ(x)=K∗ρ=R01K(x−y)ρ(y)dyat (non)uniformly distributed target grid points {xi}iM=1, where the kernel K(x) might be singular at the origin and the source density function ρ(x) is given on a source grid {yj}Nj=1 which can be different from the target grid. It achieves an optimal accuracy, inherited from the interpolation of the density ρ(x), within O(M+N) operations. Using the kernel's SOE approximation KES, the potential is split into two integrals: the exponential convolution φES =KES∗ρ and the local correction integral φcor = (K−KES)∗ρ. The exponential convolution is evaluated via the recurrence formula that is typical of the exponential function. The local correction integral is restricted to a small neighborhood of the target point where the kernel singularity is considered. Rigorous estimates of the optimal accuracy are provided. The algorithm is ideal for parallelization and favors easy extensions to complicated kernels. Extensive numerical results for different kernels are presented.

Original languageEnglish (US)
Pages (from-to)1570-1582
Number of pages13
JournalCommunications in Computational Physics
Volume29
Issue number5
DOIs
StatePublished - Mar 2021

All Science Journal Classification (ASJC) codes

  • Physics and Astronomy (miscellaneous)

Keywords

  • Discrete density
  • One dimensional convolution
  • Singular kernel
  • Sum of exponentials

Fingerprint

Dive into the research topics of 'Fast one-dimensional convolution with general kernels using sum-of-exponential approximation'. Together they form a unique fingerprint.

Cite this