arrow
Volume 29, Issue 5
Fast One-Dimensional Convolution with General Kernels Using Sum-of-Exponential Approximation

Yong Zhang, Chijie Zhuang & Shidong Jiang

Commun. Comput. Phys., 29 (2021), pp. 1570-1582.

Published online: 2021-03

Export citation
  • 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∗ρ=∫^1_{0}K(x−y)ρ(y)dy$ at (non)uniformly distributed target grid points {$x_i$}$^M_{i=1}$, where the kernel $K(x)$ might be singular at the origin and the source density function $ρ(x)$ is given on a source grid ${{{y_i}}}^N_{j=1}$ which can be different from the target grid. It achieves an optimal accuracy, inherited from the interpolation of the density $ρ(x)$, within $\mathcal{O}(M+N)$ operations. Using the kernel's SOE approximation $K_{ES}$, the potential is split into two integrals: the exponential convolution $φ_{ES}$=$K_{ES}∗ρ$ and the local correction integral $φ_{cor}=(K−K_{ES})∗ρ$. 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.

  • AMS Subject Headings

68Q25, 65R20, 65D15, 65T50

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address
  • BibTex
  • RIS
  • TXT
@Article{CiCP-29-1570, author = {Zhang , YongZhuang , Chijie and Jiang , Shidong}, title = {Fast One-Dimensional Convolution with General Kernels Using Sum-of-Exponential Approximation}, journal = {Communications in Computational Physics}, year = {2021}, volume = {29}, number = {5}, pages = {1570--1582}, 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∗ρ=∫^1_{0}K(x−y)ρ(y)dy$ at (non)uniformly distributed target grid points {$x_i$}$^M_{i=1}$, where the kernel $K(x)$ might be singular at the origin and the source density function $ρ(x)$ is given on a source grid ${{{y_i}}}^N_{j=1}$ which can be different from the target grid. It achieves an optimal accuracy, inherited from the interpolation of the density $ρ(x)$, within $\mathcal{O}(M+N)$ operations. Using the kernel's SOE approximation $K_{ES}$, the potential is split into two integrals: the exponential convolution $φ_{ES}$=$K_{ES}∗ρ$ and the local correction integral $φ_{cor}=(K−K_{ES})∗ρ$. 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.

}, issn = {1991-7120}, doi = {https://doi.org/10.4208/cicp.OA-2020-0116}, url = {http://global-sci.org/intro/article_detail/cicp/18731.html} }
TY - JOUR T1 - Fast One-Dimensional Convolution with General Kernels Using Sum-of-Exponential Approximation AU - Zhang , Yong AU - Zhuang , Chijie AU - Jiang , Shidong JO - Communications in Computational Physics VL - 5 SP - 1570 EP - 1582 PY - 2021 DA - 2021/03 SN - 29 DO - http://doi.org/10.4208/cicp.OA-2020-0116 UR - https://global-sci.org/intro/article_detail/cicp/18731.html KW - One dimensional convolution, sum of exponentials, singular kernel, discrete density. AB -

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∗ρ=∫^1_{0}K(x−y)ρ(y)dy$ at (non)uniformly distributed target grid points {$x_i$}$^M_{i=1}$, where the kernel $K(x)$ might be singular at the origin and the source density function $ρ(x)$ is given on a source grid ${{{y_i}}}^N_{j=1}$ which can be different from the target grid. It achieves an optimal accuracy, inherited from the interpolation of the density $ρ(x)$, within $\mathcal{O}(M+N)$ operations. Using the kernel's SOE approximation $K_{ES}$, the potential is split into two integrals: the exponential convolution $φ_{ES}$=$K_{ES}∗ρ$ and the local correction integral $φ_{cor}=(K−K_{ES})∗ρ$. 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.

Zhang , YongZhuang , Chijie and Jiang , Shidong. (2021). Fast One-Dimensional Convolution with General Kernels Using Sum-of-Exponential Approximation. Communications in Computational Physics. 29 (5). 1570-1582. doi:10.4208/cicp.OA-2020-0116
Copy to clipboard
The citation has been copied to your clipboard