ADAPTIVE NESTED CROSS APPROXIMATION OF NON-LOCAL OPERATORS ∗

Abstract. A new fast algebraic method for obtaining an H2-approximation of a matrix from its entries is presented. The main idea behind the method is based on the nested representation and the maximum-volume principle to select submatrices in low-rank matrices. A special iterative approach for the computation of so-called representor sets is established. The main advantage of the method is that it uses only the hierarchical partitioning of the matrix and does not require special “proxy surfaces ” to be selected in advance. The numerical experiments for the N-body problem and for the boundary integral operator confirm the effectiveness and robustness of the approach. The complexity is linear in the matrix size and polynomial in the ranks. The algorithm is implemented as an open-source Python package that is available online. 1. Introduction. Cross approximation [2, 21] is a basic reduction technique for the approx-imation of large low-rank matrices. These matrices often appear as blocks of dense matrices, coming from the discretization of non-local operators. The whole matrix is split into large blocks related to geometrically separated sets of sources and receivers, and those blocks are approximated by low-rank matrices. This partitioning forms the basis for the mosaic-skeleton method [20] o