A parallel hierarchical blocked adaptive cross approximation algorithm

Yang Liu, Wissam Sid-Lakhdar, Elizaveta Rebrova, Pieter Ghysels, Xiaoye Sherry Li

Research output: Contribution to journalArticlepeer-review

16 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)394-408
Number of pages15
JournalInternational Journal of High Performance Computing Applications
Issue number4
StatePublished - Jul 1 2020
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture


  • Adaptive cross approximation
  • multilevel algorithms
  • parallelization
  • rank-revealing decomposition
  • singular value decomposition


Dive into the research topics of 'A parallel hierarchical blocked adaptive cross approximation algorithm'. Together they form a unique fingerprint.

Cite this