An O(NlogN) hierarchical random compression method for kernel matrices by sampling partial matrix entries
An O(NlogN) hierarchical random compression method for kernel matrices by sampling partial matrix entries
复制标题
DOI：
10.1016/j.jcp.2019.07.027
复制
发表时间：
2019-11
期刊：
影响因子：
--
通讯作者：
Duan Chen;W. Cai
中科院分区：
文献类型：
--
作者：
Duan Chen;W. Cai
In this paper, we propose an O (N log N) hierarchical random compression method (HRCM) for kernel matrix compressing, which only requires sampling O (N log N) entries of a matrix. The HRCM combines the hierarchical framework of the H-matrix and a randomized sampling technique of column and row spaces for far-field interaction kernel matrix. We show that a uniform column/row sampling of a far-field kernel matrix, thus without the need and associated cost to pre-compute a costly sampling distribution, will give a low-rank compression of such low-rank matrix, independent of the matrix size and only dependent on the separation of the source and target locations. This far-field random compression technique is then implemented at each level of the hierarchical decomposition for general kernel matrices, resulting in an O (N log N) random compression method. Error and complexity analysis for the HRCM are included. Numerical results for electrostatic and low frequency Helmholtz wave kernels have validated the efficiency and accuracy of the proposed method in comparison of direct O (N 2) summations.
