An efficient method for block low-rank approximations for kernel matrix systems
For researchers working on hierarchical matrix methods for kernel matrices, this work reduces the construction cost of low-rank approximations, making large-scale problems more tractable.
The paper proposes an efficient method for low-rank approximation of kernel matrix blocks using interpolative decomposition combined with analytic kernel information, reducing construction cost from O(r|X0||Y0|) to O(r|X0|). Numerical experiments show that H² matrix construction with the proposed algorithm achieves linear computational cost in matrix dimension.
In the iterative solution of dense linear systems from boundary integral equations or systems involving kernel matrices, the main challenges are the expensive matrix-vector multiplication and the storage cost which are usually tackled by hierarchical matrix techniques such as $\mathcal{H}$ and $\mathcal{H}^2$ matrices. However, hierarchical matrices also have a high construction cost that is dominated by the low-rank approximations of the sub-blocks of the kernel matrix. In this paper, an efficient method is proposed to give a low-rank approximation of the kernel matrix block $K(X_0, Y_0)$ in the form of an interpolative decomposition (ID) for a kernel function $K(x,y)$ and two properly located point sets $X_0, Y_0$. The proposed method combines the ID using strong rank-revealing QR (sRRQR), which is purely algebraic, with analytic kernel information to reduce the construction cost of a rank-$r$ approximation from $O(r|X_0||Y_0|)$, for ID using sRRQR alone, to $O(r|X_0|)$ which is not related to $|Y_0|$. Numerical experiments show that $\mathcal{H}^2$ matrix construction with the proposed algorithm only requires a computational cost linear in the matrix dimension.