Title: A hierarchical random compression method for kernel matrices

Speaker:  Duan Chen(陈端) (University of North Carolina at Charlotte，North Carolina)
Time：2018年6月19日13:30-14:30
Location：Center for Mathematical Sciences, Room 813
Homepage： https://clas-math.uncc.edu/duan-chen/

Abstract：
In this work, we propose a hierarchical random compression method (HRCM) for kernel matrices in fast kernel summations. 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 matrices. 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 matrices, independent of the matrix sizes 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(Nlog N) random compression method. Error and complexity analysis for the HRCM are included. Numerical results for electrostatic and Helmholtz wave kernels have validated the efficiency and accuracy of the proposed method with a cross-over matrix size, in comparison of direct O(N^2) summations, in the order of thousands for a 3-4 digits relative accuracy for electrostatic and low frequency wave interaction kernels.