Fast construction of hierarchical matrix representation from matrix-vector multiplication

JOURNAL OF COMPUTATIONAL PHYSICS

卷:230

Article

Lin, Lin¹  Lu, Jianfeng²  Ying, Lexing^3,4 

[1] Princeton Univ, Program Appl & Computat Math, Princeton, NJ 08544 USA

[2] NYU, Courant Inst Math Sci, Dept Math, New York, NY 10012 USA

[3] Univ Texas Austin, Dept Math, Austin, TX 78712 USA

[4] Univ Texas Austin, ICES, Austin, TX 78712 USA

关键词: Fast algorithm;    Hierarchical matrix construction;    Randomized singular value decomposition;    Matrix-vector multiplication;    Elliptic operator;    Green's Junction;   

DOI  :  10.1016/j.jcp.2011.02.033

来源: Elsevier

【 摘 要 】

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. (C) 2011 Elsevier Inc. All rights reserved.

【 授权许可】

Free