Linear-Complexity Black-Box Randomized Compression of Rank-Structured Matrices
SIAM Journal on Scientific Computing · 30.06.2024 · 46 (3) · A1747-A1763
DOI: 10.1137/22m1528574 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Scientific Computing, online erschienen am 17.05.2024. Verfasst von James Levitt und 1 weiteren Autor:innen. Die Arbeit wurde bisher 12-mal zitiert (Crossref) und nennt 27 Literaturangaben. Gefördert von: Office of Naval Research, National Science Foundation, U.S. Department of Energy.
Abstract (Originalsprache)
A randomized algorithm for computing a compressed representation of a given rank-structured matrix [Formula: see text] is presented. The algorithm interacts with [Formula: see text] only through its action on vectors. Specifically, it draws two tall thin matrices [Formula: see text] from a suitable distribution, and then reconstructs [Formula: see text] from the information contained in the set [Formula: see text]. For the specific case of a “Hierarchically Block Separable (HBS)” matrix (a.k.a. Hierarchically Semi-Separable matrix) of block rank [Formula: see text], the number of samples [Formula: see text] required satisfies [Formula: see text], with [Formula: see text] being representative. While a number of randomized algorithms for compressing rank-structured matrices have previously been published, the current algorithm appears to be the first that is both of truly linear complexity (no [Formula: see text] factors in the complexity bound) and fully “black box” in the sense that no matrix entry evaluation is required. Further, all samples can be extracted in parallel, enabling the algorithm to work in a “streaming” or “single view” mode.
Förderung
- Office of Naval Research
- National Science Foundation
- U.S. Department of Energy
Zitieren
APA
Levitt, J., & Martinsson, P. (2024). Linear-Complexity Black-Box Randomized Compression of Rank-Structured Matrices. SIAM Journal on Scientific Computing, 46(3), A1747-A1763. https://doi.org/10.1137/22m1528574
Vancouver
Levitt J, Martinsson P. Linear-Complexity Black-Box Randomized Compression of Rank-Structured Matrices. SIAM Journal on Scientific Computing. 2024;46(3):A1747-A1763. doi:10.1137/22m1528574
BibTeX
@article{Levitt2024,
author = {Levitt, James and Martinsson, Per-Gunnar},
title = {Linear-Complexity Black-Box Randomized Compression of Rank-Structured Matrices},
journal = {SIAM Journal on Scientific Computing},
year = {2024},
volume = {46},
number = {3},
pages = {A1747--A1763},
doi = {10.1137/22m1528574}
}
EUVIMED