1. A parallel hierarchical blocked adaptive cross approximation algorithm
- Author
-
Liu, Y, Sid-Lakhdar, W, Rebrova, E, Ghysels, P, and Li, XS
- Subjects
Adaptive cross approximation ,singular value decomposition ,rank-revealing decomposition ,parallelization ,multilevel algorithms ,math.NA ,cs.NA ,Distributed Computing - 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.
- Published
- 2020