A parallel hierarchical blocked adaptive cross approximation algorithm

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 trunca...

Full description

Saved in:
Bibliographic Details
Published in:The international journal of high performance computing applications 2020-07, Vol.34 (4), p.394-408
Main Authors: Liu, Yang, Sid-Lakhdar, Wissam, Rebrova, Elizaveta, Ghysels, Pieter, Li, Xiaoye Sherry
Format: Article
Language:English
Subjects:
Adaptive algorithms
adaptive cross approximation
Algorithms
Approximation
Decomposition
Mathematical analysis
MATHEMATICS AND COMPUTING
multi-level algorithms
parallelization
rank-revealing decomposition
singular value decomposition
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1094-3420
1741-2846
DOI:10.1177/1094342020918305