Hm-toolbox: Matlab software for hodlr and HSS matrices
Massei S., Robol L., Kressner D.
approximation Low-rank approximation fast algorithms Computational Mathematics superfast FOS: Mathematics HODLR matrices existence decay bounds MATLAB linear-systems conquer method spectral projectors Hierarchical matrices HSS matrices Mathematics - Numerical Analysis low-rank Numerical Analysis (math.NA) Applied Mathematics solver
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.
Source: SIAM journal on scientific computing (Print) 42 (2020): C43–C68. doi:10.1137/19M1288048
Publisher: Society for Industrial and Applied Mathematics,, Philadelphia, PA , Stati Uniti d'America
[2] S. Ambikasaran, K. Singh, and S. Sankaran. Hodlrlib: A library for hierarchical matrices. Journal of Open Source Software, 4(34):1167, 2 2019.
[3] J. Ballani and D. Kressner. Matrices with hierarchical low-rank structures. In Exploiting hidden structure in matrix computations: algorithms and applications, volume 2173 of Lecture Notes in Math., pages 161-209. Springer, Cham, 2016.
[4] M. Bebendorf and W Hackbusch. Existence of H-matrix approximants to the inverse FE-matrix of elliptic operators with L∞-coefficients. Numer. Math., 95(1):1-28, 2003.
[5] M. Benzi, P. Boito, and N. Razouk. Decay properties of spectral projectors with applications to electronic structure. SIAM Rev., 55(1):3-64, 2013.
[6] M. Benzi and N. Razouk. Decay bounds and O(n) algorithms for approximating functions of sparse matrices. Electron. Trans. Numer. Anal., 28:16-39, 2007.
[7] D. A. Bini, S. Massei, and L. Robol. Efficient cyclic reduction for quasibirth-death problems with rank structured blocks. Appl. Numer. Math., 116:37-46, 2017.
[8] D. A. Bini, S. Massei, and L. Robol. On the decay of the off-diagonal singular values in cyclic reduction. Linear Algebra Appl., 519:27-53, 2017.
[9] S. B¨orm. H2-matrices - an efficient tool for the treatment of dense matrices. Habilitationsschrift, Christian-Albrechts-Universit¨at zu Kiel, 2006.
[10] S. B¨orm. Efficient numerical methods for non-local operators, volume 14 of EMS Tracts in Mathematics. European Mathematical Society (EMS), Zu¨rich, 2010. H2-matrix compression, algorithms and analysis.
[11] S. B¨orm, L. Grasedyck, and W. Hackbusch. cal matrices. Lecture note 21/2003, MPI-MIS Germany, 2003. Revised June 2006. Available http://www.mis.mpg.de/preprints/ln/lecturenote-2103.pdf.
[21] C. J. Geoga, M. Anitescu, and M. L. Stein. Scalable Gaussian process computations using hierarchical matrices. Journal of Computational and Graphical Statistics, 0(ja):1-22, 2019.
[22] P. Ghysels, X. S. Li, F.-H. Rouet, S. Williams, and A. Napov. An efficient multicore implementation of a novel HSS-structured multifrontal solver using randomized sampling. SIAM J. Sci. Comput., 38(5):S358-S384, 2016.
[23] G. H. Golub and C. F. Van Loan. Matrix computations. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore, MD, fourth edition, 2013.
[24] L. Grasedyck. Existence of a low rank or H-matrix approximant to the solution of a Sylvester equation. Numer. Linear Algebra Appl., 11(4):371- 389, 2004.
[25] W. Hackbusch. Hierarchical matrices: algorithms and analysis, volume 49 of Springer Series in Computational Mathematics. Springer, Heidelberg, 2015.
[26] N. Halko, P. G. Martinsson, and J. A. Tropp. Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions. SIAM Rev., 53(2):217-288, 2011.
[27] G. Heinig. Inversion of generalized Cauchy matrices and other classes of structured matrices. In Linear algebra for signal processing (Minneapolis, MN, 1992), volume 69 of IMA Vol. Math. Appl., pages 63-81. Springer, New York, 1995.
[28] N. J. Higham. Functions of matrices. SIAM, Philadelphia, PA, 2008.
[29] N. J. Higham. The scaling and squaring method for the matrix exponential revisited. SIAM Rev., 51(4):747-764, 2009.
[30] D. Kressner, P. Ku¨rschner, and S. Massei. Low-rank updates and divideand-conquer methods for quadratic matrix equations. arXiv:1903.02343, 2019. To appear in Numer. Algorithms.
[31] D. Kressner, S. Massei, and L. Robol. Low-rank updates and a divideand-conquer method for linear matrix equations. SIAM J. Sci. Comput., 41(2):A848-A876, 2019.
[32] D. Kressner and L. Periˇsa. Recompression of Hadamard products of tensors in Tucker format. SIAM J. Sci. Comput., 39(5):A1879-A1902, 2017.
[33] D. Kressner and A. Sˇuˇsnjara. Fast computation of spectral projectors of banded matrices. SIAM J. Matrix Anal. Appl., 38(3):984-1009, 2017.
[34] D. Kressner and A. Sˇuˇsnjara. Fast QR decomposition of HODLR matrices. arXiv preprint arXiv:1809.10585, 2018.
[35] P. G. Martinsson. A fast randomized algorithm for computing a hierarchically semiseparable representation of a matrix. SIAM J. Matrix Anal. Appl., 32(4):1251-1274, 2011.
[36] S. Massei, M. Mazza, and L. Robol. Fast solvers for two-dimensional fractional diffusion equations using rank structured matrices. SIAM J. Sci. Comput., 41(4):A2627-A2656, 2019.
[37] S. Massei and L. Robol. Decay bounds for the numerical quasiseparable preservation in matrix functions. Linear Algebra Appl., 516:212-242, 2017.
[38] M. M. Meerschaert and C. Tadjeran. Finite difference approximations for fractional advection-dispersion flow equations. J. Comput. Appl. Math., 172(1):65-77, 2004.
[39] F. Rouet, X. S. Li, P. Ghysels, and A. Napov. A distributed-memory package for dense hierarchically semi-separable matrix computations using randomization. ACM Trans. Math. Software, 42(4):Art. 27, 35, 2016.
[40] Z. Sheng, P. Dewilde, and S. Chandrasekaran. Algorithms to solve hierarchically semi-separable systems. In System theory, the Schur algorithm and multidimensional analysis, volume 176 of Oper. Theory Adv. Appl., pages 255-294. Birkh¨auser, Basel, 2007.
[41] H. D. Simon and H. Zha. Low-rank matrix approximation using the Lanczos bidiagonalization process with applications. SIAM J. Sci. Comput., 21(6):2257-2274, 2000.
[42] V. Simoncini. Computational methods for linear matrix equations. SIAM Rev., 58(3):377-441, 2016.
[43] R. Vandebril, M. Van Barel, and N. Mastronardi. Matrix computations and semiseparable matrices. Vol. 1. Johns Hopkins University Press, Baltimore, MD, 2008. Linear systems.
[44] R. Vandebril, M. Van Barel, and N. Mastronardi. Matrix computations and semiseparable matrices. Vol. 2. Johns Hopkins University Press, Baltimore, MD, 2008. Eigenvalue and singular value methods.
[45] J. Vogel, J. Xia, S. Cauley, and V. Balakrishnan. Superfast divide-andconquer method and perturbation analysis for structured eigenvalue solutions. SIAM J. Sci. Comput., 38(3):A1358-A1382, 2016.
[46] A. Sˇuˇsnjara and D. Kressner. A fast spectral divide-and-conquer method for banded matrices. arXiv:1801.04175, 2018.
[47] S. Wang, X. S. Li, F.-H. Rouet, J. Xia, and M. V. de Hoop. A parallel geometric multifrontal solver using hierarchically semiseparable structure. ACM Trans. Math. Software, 42(3):Art. 21, 21, 2016.
[48] Y. Xi, J. Xia, S. Cauley, and V. Balakrishnan. Superfast and stable structured solvers for Toeplitz least squares via randomized sampling. SIAM J. Matrix Anal. Appl., 35(1):44-72, 2014.
[49] J. Xia, S. Chandrasekaran, M. Gu, and X. S. Li. Superfast multifrontal method for large structured linear systems of equations. SIAM J. Matrix Anal. Appl., 31(3):1382-1411, 2009.
[50] J. Xia, S. Chandrasekaran, M. Gu, and X. S. Li. Fast algorithms for hierarchically semiseparable matrices. Numer. Linear Algebra Appl., 17(6):953- 976, 2010.
[51] J. Xia, Y. Xi, and M. Gu. A superfast structured solver for Toeplitz linear systems via randomized sampling. SIAM J. Matrix Anal. Appl., 33(3):837- 858, 2012.
Metrics
Back to previous page
@article{oai:it.cnr:prodotti:424805,
title = {Hm-toolbox: Matlab software for hodlr and HSS matrices},
author = {Massei S. and Robol L. and Kressner D.},
publisher = {Society for Industrial and Applied Mathematics,, Philadelphia, PA , Stati Uniti d'America},
doi = {10.1137/19m1288048 and 10.48550/arxiv.1909.07909},
journal = {SIAM journal on scientific computing (Print)},
volume = {42},
year = {2020}
}
0000-0002-6545-1748ISTI Repository
DOI
10.1137/19m1288048
10.48550/arxiv.1909.07909
arXiv.org e-Print Archive
SIAM Journal on Scientific Computing
epubs.siam.org
Infoscience - EPFL scientific publications
