Computational & Applied Math Seminar

Fast Algorithm for Convolution-type Potential Evaluation in Different Dimensions

  • Speaker: Yong ZHANG (Tianjin University)

  • Time: Nov 4, 2020, 15:00-16:00

  • Location: Room 415, Block 3, Hui Yuan

Abstract

Convolution-type potential are common and important in many science and engineering fields. Efficient and accurate evaluation of such nonlocal potentials are essential in practical simulations. In this talk, I will focus on those arising from quantum physics/chemistry and lightning-shield protection, including Coulomb, dipolar and Yukawa potential that are generated by isotropic and anisotropic smooth and fast-decaying density, as well as convolutions defined on a one-dimensional adaptive finite difference grid. The convolution kernel is usually singular or discontinuous at the origin and/or at the far field, and density might be anisotropic, which together present great challenges for numerics in both accuracy and efficiency. The state-of-art fast algorithms include Wavelet based Method(WavM), kernel truncation method(KTM), NonUniform-FFT based method(NUFFT) and Gaussian-Sum based method(GSM). Gaussian-sum/exponential-sum approximation and kernel truncation technique, combined with finite Fourier series and Taylor expansion, finally lead to a O(N log N) algorithm achieving spectral accuracy. For the one-dimensional convolutions, we shall introduce the tree and sum-of-exponential based fast algorithm.