Fast construction of hierarchical matrix representation from matrix-vector multiplication

Journal Article (Journal Article)

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(logn) applications of the matrix on structured random test vectors and O(nlogn) 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. © 2011 Elsevier Inc.

Full Text

Duke Authors

Cited Authors

  • Lin, L; Lu, J; Ying, L

Published Date

  • January 1, 2011

Published In

Volume / Issue

  • 230 / 10

Start / End Page

  • 4071 - 4087

Electronic International Standard Serial Number (EISSN)

  • 1090-2716

International Standard Serial Number (ISSN)

  • 0021-9991

Digital Object Identifier (DOI)

  • 10.1016/

Citation Source

  • Scopus