New Algebraic Fast Algorithms for N-body Problems in Two and Three Dimensions

We present two new algebraic multilevel nested hierarchical matrix algorithms to perform fast matrix-vector product (MVP) for N-body problems in d dimensions. The hierarchical representations are based on our recently introduced weak admissibility condition in higher dimensions, where the admissible clusters are the far-field and the vertex-sharing clusters. Due to the use of nested form of the bases, the proposed hierarchical matrix algorithms are more efficient than the non-nested algorithms. We rely on purely algebraic low-rank approximation techniques (e.g., ACA and NCA) and develop both algorithms in a black-box (kernel-independent) fashion.