A parallel hierarchical blocked adaptive cross approximation algorithm. (July 2020)

• Record Type: Journal Article
• Authors: Liu, Yang; Sid-Lakhdar, Wissam; Rebrova, Elizaveta; Ghysels, Pieter; Li, Xiaoye Sherry
• Is Part Of: International journal of high performance computing applications. Volume 34:Number 4(2020)
• Page Start: 394
• Page End: 408
• Publication Date: 2020-07
• Subjects: Adaptive cross approximation -- singular value decomposition -- rank-revealing decomposition -- parallelization -- multilevel algorithms; High performance computing -- Periodicals; Supercomputers -- Periodicals; 004.1105
• DOI: 10.1177/1094342020918305
• Languages: English
• ISSNs: 1094-3420

Abstract

This article presents a low-rank decomposition algorithm based on subsampling of matrix entries. The proposed algorithm first computes rank-revealing decompositions of submatrices with a blocked adaptive cross approximation (BACA) algorithm, and then applies a hierarchical merge operation via truncated singular value decompositions (H-BACA). The proposed algorithm significantly improves the convergence of the baseline ACA algorithm and achieves reduced computational complexity compared to the traditional decompositions such as rank-revealing QR. Numerical results demonstrate the efficiency, accuracy, and parallel scalability of the proposed algorithm.