EUVIMEDEUVIMED entdecken
Crossref

Linear-Complexity Black-Box Randomized Compression of Rank-Structured Matrices

James Levitt, Per-Gunnar Martinsson

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →