  In this paper, 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 the column and
row spaces for far-field interaction kernel matrices. We show that a uniform
column/row sampling (with a given sample size) of a far-field kernel matrix,
with- out 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(N logN) random compression method. Error and
complexity analysis for the HRCM are included. Numerical results for
electrostatic and Helmholtz wave kernels have vali- dated 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.
