An efficient method for block low-rank approximations for kernel matrix systems

MaRDI QIDQ6309480zbMATH OpenFDO

Authors Xin Xing, Edmond Chow

Publication date 9 November 2018

Abstract: 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 $mathcalH$ 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.

This page was built for publication: An efficient method for block low-rank approximations for kernel matrix systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6309480)