A Fast Summation Tree Code for Matérn Kernel

The Matérn family of functions is a widely used covariance kernel in spatial statistics for Gaussian process modeling, which in many instances requires calculations with a covariance matrix. In this paper, we design a fast summation algorithm for the Matérn kernel in order to efficiently perform matrix-vector multiplications. This algorithm is based on the Barnes--Hut tree code framework and addresses several practical issues: the anisotropy of the kernel, the nonuniform distribution of the point set, and a tight error estimate of the approximation. Even though the algorithmic details differ from the standard tree code in several aspects, empirically the computational cost of our algorithm scales as O(nlog n) for n points. Comprehensive numerical experiments are shown to demonstrate the practicality of the design.