@Article{CiCP-29-5,
author = {Zhang, Yong and Zhuang, Chijie and Shidong, Jiang},
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 = {<p style="text-align: justify;">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&#39;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.</p>},
issn = {1991-7120},
doi = {https://doi.org/10.4208/cicp.OA-2020-0116},
url = {https://global-sci.com/article/79667/fast-one-dimensional-convolution-with-general-kernels-using-sum-of-exponential-approximation}
}