Fast construction of hierarchical matrix representation from matrix–vector multiplication

We develop a hierarchical matrix construction algorithm using matrix–vector multiplications, based on the randomized singular value decomposition of low-rank matrices. The algorithm uses O ( log n ) applications of the matrix on structured random test vectors and O ( n log n ) extra computational cost, where n is the dimension of the unknown matrix. Numerical examples on constructing Green’s functions for elliptic operators in two dimensions show efficiency and accuracy of the proposed algorithm.