Fast construction of hierarchical matrix representation from matrixvector multiplication
We develop a hierarchical matrix construction algorithm using matrixvector multiplications, based on the randomized singular value decomposition of low-rank matrices. The algorithm uses O(logn) O ( log n ) applications of the matrix on structured random test vectors and O(nlogn) O ( n log n ) extra computational cost, where n is the dimension of the unknown matrix. Numerical examples on constructing Greens functions for elliptic operators in two dimensions show efficiency and accuracy of the proposed algorithm.
matrixvector multiplication hierarchical matrix construction randomized singular value decomposition greens function elliptic operator fast algorithm