2018/11/09 by Xing, Xin, Chow, Edmond
#FOS: Mathematics #Numerical Analysis (math.NA)
paper · doi:10.48550/arxiv.1811.04134
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 H and H2 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(X0, Y0) in the form of an interpolative decomposition (ID) for a kernel function K(x,y) and two properly located point sets X0, Y0. 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|X0||Y0|), for ID using sRRQR alone, to O(r|X0|) which is not related to |Y0|. Numerical experiments show that H2 matrix construction with the proposed algorithm only requires a computational cost linear in the matrix dimension.