PBBFMM3D: a parallel black-box algorithm for kernel matrix-vector multiplication

Abstract

Kernel matrix-vector product is ubiquitous in many science and engineering applications. However, a naive method requires $O(N^2)$ operations, which becomes prohibitive for large-scale problems. We introduce a parallel method that provably requires $O(N)$ operations to reduce the computation cost. The distinct feature of our method is that it requires only the ability to evaluate the kernel function, offering a black-box interface to users. Our parallel approach targets multi-core shared-memory machines and is implemented using OpenMP. Numerical results demonstrate up to $19\times$ speedup on 32 cores. We also present a real-world application in geostatistics, where our parallel method was used to deliver fast principle component analysis of covariance matrices.

References in corpus (4)

• A Kalman filter powered by ${\mathcal{H}}^2$-matrices for quasi-continuous data assimilation problems
• Fast algorithms for evaluating the stress field of dislocation lines in anisotropic elastic media
• NFFT meets Krylov methods: Fast matrix-vector products for the graph Laplacian of fully connected networks
• Parallelization of the inverse fast multipole method with an application to boundary element method

Cited by in corpus (2)

• Distributed-memory $\mathcal{H}$-matrix Algebra I: Data Distribution and Matrix-vector Multiplication
• Overlapping Domain Decomposition Preconditioner for Integral Equations