HODLRdD: A new black-box fast algorithm for N-body problems in d-dimensions with guaranteed error bounds: Applications to integral equations and support vector machines

We study rank of sub-matrices arising out of kernel functions. Such kernel functions are frequently encountered in a wide range of areas. To our knowledge, this is the first work to formally study rank growth of matrices arising out of a wide range of kernel functions in any dimension. In this article, we prove two new theorems bounding rank of different sub-matrices arising from these kernel functions. Bounds like these are often useful for analyzing the complexity of various hierarchical matrix algorithms. Another significant contribution of this article is that using the obtained rank bounds, we also propose a way to extend the notion of weak-admissibility for hierarchical matrices in higher dimensions. Based on this proposed weak-admissibility condition, we develop a black-box (kernel-independent) fast algorithm for N-body problems, hierarchically off-diagonal low-rank matrix in d dimensions (HODLRdD), which can perform matrix-vector products with quasi-linear complexity in any dimension d.