New algebraic fast algorithms for $N$-body problems in two and three dimensions

This article presents two new algebraic algorithms to perform fast matrix-vector product for $N$-body problems in $d$ dimensions, namely nHODLR$d$D (nested algorithm) and s-nHODLR$d$D (semi-nested or partially nested algorithm). The nHODLR$d$D and s-nHODLR$d$D algorithms are the nested and semi-nested version of our previously proposed fast algorithm, the hierarchically off-diagonal low-rank matrix in $d$ dimensions (HODLR$d$D), respectively, where the admissible clusters are the certain far-field and the vertex-sharing clusters. We rely on algebraic low-rank approximation techniques (ACA and NCA) and develop both algorithms in a black-box (kernel-independent) fashion. The initialization time of the proposed hierarchical structures scales quasi-linearly. Using the nHODLR$d$D and s-nHODLR$d$D hierarchical structures, one can perform the multiplication of a dense matrix (arising out of $N$-body problems) with a vector that scales as $\mathcal{O}(pN)$ and $\mathcal{O}(pN \log(N))$, respectively, where $p$ grows at most poly logarithmically with $N$. The numerical results in $2$D and $3$D $(d=2,3)$ show that the proposed nHODLR$d$D algorithm is competitive to the algebraic Fast Multipole Method in $d$ dimensions with respect to the matrix-vector product time and space complexity. The C++ implementation with OpenMP parallelization of the proposed algorithms is available at \url{https://github.com/riteshkhan/nHODLRdD/}.