A parallel hierarchical blocked adaptive cross approximation algorithm

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

doi:10.1177/1094342020918305

A parallel hierarchical blocked adaptive cross approximation algorithm

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

Research output: Contribution to journal › Article › peer-review

17 Scopus citations

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.

Original language	English (US)
Pages (from-to)	394-408
Number of pages	15
Journal	International Journal of High Performance Computing Applications
Volume	34
Issue number	4
DOIs	https://doi.org/10.1177/1094342020918305
State	Published - Jul 1 2020
Externally published	Yes

All Science Journal Classification (ASJC) codes

Software
Theoretical Computer Science
Hardware and Architecture

Keywords

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

Access to Document

10.1177/1094342020918305

Cite this

@article{30be8e85a9df49e9a44e22c3d91d28b6,

title = "A parallel hierarchical blocked adaptive cross approximation algorithm",

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.",

keywords = "Adaptive cross approximation, multilevel algorithms, parallelization, rank-revealing decomposition, singular value decomposition",

author = "Yang Liu and Wissam Sid-Lakhdar and Elizaveta Rebrova and Pieter Ghysels and Li, {Xiaoye Sherry}",

note = "Publisher Copyright: {\textcopyright} The Author(s) 2020.",

year = "2020",

month = jul,

day = "1",

doi = "10.1177/1094342020918305",

language = "English (US)",

volume = "34",

pages = "394--408",

journal = "International Journal of High Performance Computing Applications",

issn = "1094-3420",

publisher = "SAGE Publications Inc.",

number = "4",

}

TY - JOUR

T1 - A parallel hierarchical blocked adaptive cross approximation algorithm

AU - Liu, Yang

AU - Sid-Lakhdar, Wissam

AU - Rebrova, Elizaveta

AU - Ghysels, Pieter

AU - Li, Xiaoye Sherry

N1 - Publisher Copyright: © The Author(s) 2020.

PY - 2020/7/1

Y1 - 2020/7/1

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

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

KW - Adaptive cross approximation

KW - multilevel algorithms

KW - parallelization

KW - rank-revealing decomposition

KW - singular value decomposition

UR - http://www.scopus.com/inward/record.url?scp=85083796265&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85083796265&partnerID=8YFLogxK

U2 - 10.1177/1094342020918305

DO - 10.1177/1094342020918305

M3 - Article

AN - SCOPUS:85083796265

SN - 1094-3420

VL - 34

SP - 394

EP - 408

JO - International Journal of High Performance Computing Applications

JF - International Journal of High Performance Computing Applications

IS - 4

ER -

A parallel hierarchical blocked adaptive cross approximation algorithm

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this