Communications in Mathematical Sciences

Volume 17 (2019)

Number 6

Fast algorithm for computing nonlocal operators with finite interaction distance

Pages: 1653 – 1670



Xiaochuan Tian (Department of Mathematics, University of Texas, Austin, Tx., U.S.A.)

Björn Engquist (Department of Mathematics and the Oden Institute, University of Texas, Austin, Tx., U.S.A.)


Developments of nonlocal operators for modeling processes that traditionally have been described by local differential operators have been increasingly active during the last few years. One example is peridynamics for brittle materials and another is nonstandard diffusion including the use of fractional derivatives. A major obstacle for application of these methods is the high computational cost from the numerical implementation of the nonlocal operators. It is natural to consider fast methods of fast multipole or hierarchical matrix type to overcome this challenge. Unfortunately the relevant kernels do not satisfy the standard necessary conditions. In this work a new class of fast algorithms is developed and analyzed, which in some cases reduces the computational complexity of applying nonlocal operators to essentially the same order of magnitude as the complexity of standard local numerical methods.


nonlocal operator, fast algorithm, nonlocal diffusion, peridynamics, heterogeneous material, fast multipole method, finite interaction

2010 Mathematics Subject Classification

45K05, 65F05, 65R20, 82C21

The research of Bjorn Engquist is supported in part by the U.S. NSF grant DMS-1620396. The research of Xiaochuan Tian is supported in part by the U.S. NSF grant DMS-1819233.

Received 23 January 2019

Accepted 1 July 2019

Published 26 December 2019