Abstract
Matrices with hierarchical low-rank structure, including HODLR and HSS matrices, constitute a versatile tool to develop fast algorithms for addressing large-scale problems. While existing software packages for such matrices often focus on linear systems, their scope of applications is in fact much wider and includes, for example, matrix functions and eigenvalue problems. In this work, we present a new MATLAB toolbox called hm-toolbox, which encompasses this versatility with a broad set of tools for HODLR and HSS matrices, unmatched by existing software. While mostly based on algorithms that can be found in the literature, our toolbox also contains a few new algorithms as well as novel auxiliary functions. Being entirely based on MATLAB, our implementation does not strive for optimal performance. Nevertheless, it maintains the favorable complexity of hierarchical low-rank matrices and offers, at the same time, a convenient way of prototyping and experimenting with algorithms. A number of applications illustrate the use of the hm-toolbox.
| Original language | English |
|---|---|
| Pages (from-to) | C43-C68 |
| Journal | SIAM Journal on Scientific Computing |
| Volume | 42 |
| Issue number | 2 |
| DOIs | |
| Publication status | Published - 2020 |
| Externally published | Yes |
Bibliographical note
Funding Information:The work of the first author was supported by the SNSF research project Fast Algorithms from Low-Rank Updates under grant 200020 178806. The work of the second author was partially supported by the GNCS/INdAM project "Metodi di proiezione per equazioni di matrici e sistemi lineari con operatori deniti tramite somme di prodotti di Kronecker, e soluzioni con struttura di rango."
Funding Information:
∗Submitted to the journal’s Software and High-Performance Computing section September 18, 2019; accepted for publication (in revised form) January 28, 2020; published electronically April 8, 2020. https://doi.org/10.1137/19M1288048 Funding: The work of the first author was supported by the SNSF research project Fast Algorithms from Low-Rank Updates under grant 200020 178806. The work of the second author was partially supported by the GNCS/INdAM project “Metodi di proiezione per equazioni di matrici e sistemi lineari con operatori deniti tramite somme di prodotti di Kronecker, e soluzioni con struttura di rango.” †Applied Mathematics, EPFL Lausanne, Lausanne, CH-1015, Vaud, Switzerland (massei.stef@ gmail.com). ‡Department of Mathematics, University of Pisa, Pisa, 56127, Italy ([email protected]). §SB-MATHICSE-ANCHP, EPFL Lausanne, Lausanne, CH-1015, Vaud, Switzerland (daniel. [email protected]).
Publisher Copyright:
Copyright © by SIAM.
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.
Funding
The work of the first author was supported by the SNSF research project Fast Algorithms from Low-Rank Updates under grant 200020 178806. The work of the second author was partially supported by the GNCS/INdAM project "Metodi di proiezione per equazioni di matrici e sistemi lineari con operatori deniti tramite somme di prodotti di Kronecker, e soluzioni con struttura di rango." ∗Submitted to the journal’s Software and High-Performance Computing section September 18, 2019; accepted for publication (in revised form) January 28, 2020; published electronically April 8, 2020. https://doi.org/10.1137/19M1288048 Funding: The work of the first author was supported by the SNSF research project Fast Algorithms from Low-Rank Updates under grant 200020 178806. The work of the second author was partially supported by the GNCS/INdAM project “Metodi di proiezione per equazioni di matrici e sistemi lineari con operatori deniti tramite somme di prodotti di Kronecker, e soluzioni con struttura di rango.” †Applied Mathematics, EPFL Lausanne, Lausanne, CH-1015, Vaud, Switzerland (massei.stef@ gmail.com). ‡Department of Mathematics, University of Pisa, Pisa, 56127, Italy ([email protected]). §SB-MATHICSE-ANCHP, EPFL Lausanne, Lausanne, CH-1015, Vaud, Switzerland (daniel. [email protected]).
Keywords
- Hierarchical matrices
- HODLR matrices
- HSS matrices
- Low-rank approximation
- MATLAB