Fast construction of hierarchical matrix representation from matrix-vector multiplication
This work addresses the problem of approximating dense matrices from implicit operators, offering a faster construction method for hierarchical matrices in scientific computing.
The authors propose an algorithm to construct hierarchical matrix representations using only matrix-vector products, achieving O(log n) matrix applications and O(n log n) extra cost. Numerical tests on 2D elliptic Green's functions demonstrate efficiency and accuracy.
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 $\mathcal{O}(\log n)$ applications of the matrix on structured random test vectors and $\mathcal{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.