×

Hm-toolbox: MATLAB software for HODLR and HSS matrices. (English) Zbl 1437.15002

Summary: 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.

MSC:

15-04 Software, source code, etc. for problems pertaining to linear algebra
65F55 Numerical methods for low-rank matrix approximation; matrix compression
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] S. Ambikasaran, D. Foreman-Mackey, L. Greengard, D. W. Hogg, and M. O’Neil, Fast direct methods for Gaussian processes, IEEE Trans. Pattern Anal. Mach. Intell., 38 (2016), pp. 252-265, https://doi.org/10.1109/TPAMI.2015.2448083.
[2] S. Ambikasaran, K. Singh, and S. Sankaran, HODLRlib: A Library for Hierarchical Matrices, J. Open Source Software, 4 (2019), 1167, https://doi.org/10.21105/joss.01167.
[3] J. Ballani and D. Kressner, Matrices with hierarchical low-rank structures, in Exploiting Hidden Structure in Matrix Computations: Algorithms and Applications, Lecture Notes in Math. 2173, Springer, Cham, 2016, pp. 161-209. · Zbl 1361.65023
[4] M. Bebendorf, AHMED, https://github.com/xantares/ahmed, (2019).
[5] M. Bebendorf and W. Hackbusch, Existence of \(\mathcal H\)-matrix approximants to the inverse FE-matrix of elliptic operators with \(L^\infty \)-coefficients, Numer. Math., 95 (2003), pp. 1-28, https://doi.org/10.1007/s00211-002-0445-6. · Zbl 1033.65100
[6] M. Benzi, P. Boito, and N. Razouk, Decay properties of spectral projectors with applications to electronic structure, SIAM Rev., 55 (2013), pp. 3-64, https://doi.org/10.1137/100814019. · Zbl 1377.65155
[7] M. Benzi and N. Razouk, Decay bounds and \(O(n)\) algorithms for approximating functions of sparse matrices, Electron. Trans. Numer. Anal., 28 (2007), pp. 16-39. · Zbl 1171.65034
[8] D. A. Bini, S. Massei, and L. Robol, Efficient cyclic reduction for quasi-birth-death problems with rank structured blocks, Appl. Numer. Math., 116 (2017), pp. 37-46, https://doi.org/10.1016/j.apnum.2016.06.014. · Zbl 1372.65122
[9] D. A. Bini, S. Massei, and L. Robol, On the decay of the off-diagonal singular values in cyclic reduction, Linear Algebra Appl., 519 (2017), pp. 27-53, https://doi.org/10.1016/j.laa.2016.12.027. · Zbl 1360.65118
[10] S. Börm, HLIBPro, https://www.hlibpro.com/.
[11] S. Börm, \( \mathcal{H}_2\)-Matrices-An Efficient Tool for the Treatment of Dense Matrices, Habilitationsschrift, Christian-Albrechts-Universität zu Kiel, 2006.
[12] S. Börm, Efficient Numerical Methods for Non-Local Operators: \({\mathcal{H}}{^2} \)-Matrix Compression, Algorithms and Analysis, EMS Tracts Math. 14, European Mathematical Society, Zürich, 2010, https://doi.org/10.4171/091. · Zbl 1208.65037
[13] S. Börm, H2Lib, https://github.com/H2Lib/H2Lib, (2019).
[14] S. Börm, L. Grasedyck, and W. Hackbusch, Hierarchical Matrices, Lecture Note 21/2003, MPI-MIS Leipzig, 2006, http://www.mis.mpg.de/preprints/ln/lecturenote-2103.pdf.
[15] P. Businger and G. H. Golub, Linear least squares solutions by Householder transformations, Numer. Math., 7 (1965), pp. 269-276, https://doi.org/10.1007/BF01436084. · Zbl 0142.11503
[16] S. Chandrasekaran, P. Dewilde, M. Gu, T. Pals, X. Sun, A.-J. van der Veen, and D. White, Some fast algorithms for sequentially semiseparable representations, SIAM J. Matrix Anal. Appl., 27 (2005), pp. 341-364, https://doi.org/10.1137/S0895479802405884. · Zbl 1091.65063
[17] S. Chandrasekaran, M. Gu, and T. Pals, A fast ULV decomposition solver for hierarchically semiseparable representations, SIAM J. Matrix Anal. Appl., 28 (2006), pp. 603-622, https://doi.org/10.1137/S0895479803436652. · Zbl 1120.65031
[18] J. Dölz, H. Harbrecht, and M. D. Multerer, On the best approximation of the hierarchical matrix product, SIAM J. Matrix Anal. Appl., 40 (2019), pp. 147-174, https://doi.org/10.1137/18M1189373. · Zbl 07011413
[19] Y. Eidelman, I. Gohberg, and I. Haimovici, Separable Type Representations of Matrices and Fast Algorithms, Volume 1: Basics. Completion Problems. Multiplication and Inversion Algorithms, Oper. Theory Adv. Appl. 234, Birkhäuser/Springer, Basel, 2014. · Zbl 1280.65027
[20] Y. Eidelman, I. Gohberg, and I. Haimovici, Separable Type Representations of Matrices and Fast Algorithms, Volume 2: Eigenvalue Method, Oper. Theory Adv. Appl. 235, Birkhäuser/Springer, Basel, 2014. · Zbl 1280.65034
[21] M. Faustmann, J. M. Melenk, and D. Praetorius, Existence of \(\mathcal{H} \)-matrix approximants to the inverse of BEM matrices: The hyper-singular integral operator, IMA J. Numer. Anal., 37 (2017), pp. 1211-1244, https://doi.org/10.1093/imanum/drw024. · Zbl 1433.65324
[22] I. P. Gavrilyuk, W. Hackbusch, and B. N. Khoromskij, \( \mathcal{H} \)-matrix approximation for the operator exponential with applications, Numer. Math., 92 (2002), pp. 83-111, https://doi.org/10.1007/s002110100360. · Zbl 1005.65113
[23] I. P. Gavrilyuk, W. Hackbusch, and B. N. Khoromskij, Data-sparse approximation to the operator-valued functions of elliptic operator, Math. Comp., 73 (2004), pp. 1297-1324, https://doi.org/10.1090/S0025-5718-03-01590-4. · Zbl 1065.47009
[24] C. J. Geoga, M. Anitescu, and M. L. Stein, Scalable Gaussian process computations using hierarchical matrices, J. Comput. Graph. Statist., https://doi.org/10.1080/10618600.2019.1652616. · Zbl 07499251
[25] 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 (2016), pp. S358-S384, https://doi.org/10.1137/15M1010117. · Zbl 1352.65092
[26] G. H. Golub and C. F. Van Loan, Matrix Computations, 4th ed., Johns Hopkins Stud. Math. Sci., Johns Hopkins University Press, Baltimore, MD, 2013. · Zbl 1268.65037
[27] L. Grasedyck, Existence of a low rank or \(\mathcal H\)-matrix approximant to the solution of a Sylvester equation, Numer. Linear Algebra Appl., 11 (2004), pp. 371-389, https://doi.org/10.1002/nla.366. · Zbl 1164.65381
[28] W. Hackbusch, Hierarchical Matrices: Algorithms and Analysis, Springer Ser. Comput. Math. 49, Springer, Heidelberg, 2015, https://doi.org/10.1007/978-3-662-47324-5. · Zbl 1336.65041
[29] W. Hackbusch, B. N. Khoromskij, and R. Kriemann, Hierarchical matrices based on a weak admissibility criterion, Computing, 73 (2004), pp. 207-243, https://doi.org/10.1007/s00607-004-0080-4. · Zbl 1063.65035
[30] N. Halko, P. G. Martinsson, and J. A. Tropp, Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions, SIAM Rev., 53 (2011), pp. 217-288, https://doi.org/10.1137/090771806. · Zbl 1269.65043
[31] G. Heinig, Inversion of generalized Cauchy matrices and other classes of structured matrices, in Linear Algebra for Signal Processing (Minneapolis, MN, 1992), IMA Vol. Math. Appl. 69, Springer, New York, 1995, pp. 63-81, https://doi.org/10.1007/978-1-4612-4228-4_5. · Zbl 0823.65020
[32] N. J. Higham, Functions of Matrices, SIAM, Philadelphia, 2008. · Zbl 1167.15001
[33] N. J. Higham, The scaling and squaring method for the matrix exponential revisited, SIAM Rev., 51 (2009), pp. 747-764, https://doi.org/10.1137/090768539. · Zbl 1178.65040
[34] D. Kressner, P. Kürschner, and S. Massei, Low-rank updates and divide-and-conquer methods for quadratic matrix equations, Numer. Algorithms, (2019), https://doi.org/10.1007/s11075-019-00776-w. · Zbl 1448.65034
[35] D. Kressner, S. Massei, and L. Robol, Low-rank updates and a divide-and-conquer method for linear matrix equations, SIAM J. Sci. Comput., 41 (2019), pp. A848-A876, https://doi.org/10.1137/17M1161038. · Zbl 1448.65034
[36] D. Kressner and L. Periša, Recompression of Hadamard products of tensors in Tucker format, SIAM J. Sci. Comput., 39 (2017), pp. A1879-A1902, https://doi.org/10.1137/16M1093896. · Zbl 1373.65031
[37] D. Kressner and A. Šušnjara, Fast computation of spectral projectors of banded matrices, SIAM J. Matrix Anal. Appl., 38 (2017), pp. 984-1009, https://doi.org/10.1137/16M1087278. · Zbl 1373.65023
[38] D. Kressner and A. Šušnjara, Fast QR Decomposition of HODLR Matrices, preprint, arXiv:1809.10585, 2018.
[39] P. G. Martinsson, A fast randomized algorithm for computing a hierarchically semiseparable representation of a matrix, SIAM J. Matrix Anal. Appl., 32 (2011), pp. 1251-1274, https://doi.org/10.1137/100786617. · Zbl 1237.65028
[40] S. Massei, M. Mazza, and L. Robol, Fast solvers for two-dimensional fractional diffusion equations using rank structured matrices, SIAM J. Sci. Comput., 41 (2019), pp. A2627-A2656, https://doi.org/10.1137/18M1180803. · Zbl 1420.65096
[41] S. Massei and L. Robol, Decay bounds for the numerical quasiseparable preservation in matrix functions, Linear Algebra Appl., 516 (2017), pp. 212-242, https://doi.org/10.1016/j.laa.2016.11.041. · Zbl 1352.15011
[42] M. M. Meerschaert and C. Tadjeran, Finite difference approximations for fractional advection-dispersion flow equations, J. Comput. Appl. Math., 172 (2004), pp. 65-77, https://doi.org/10.1016/j.cam.2004.01.033. · Zbl 1126.76346
[43] 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 (2016), 27, https://doi.org/10.1145/2930660. · Zbl 1369.65043
[44] Z. Sheng, P. Dewilde, and S. Chandrasekaran, Algorithms to solve hierarchically semi-separable systems, in System Theory, the Schur Algorithm and Multidimensional Analysis, Oper. Theory Adv. Appl. 176, Birkhäuser, Basel, 2007, pp. 255-294, https://doi.org/10.1007/978-3-7643-8137-0_5. · Zbl 1123.65020
[45] H. D. Simon and H. Zha, Low-rank matrix approximation using the Lanczos bidiagonalization process with applications, SIAM J. Sci. Comput., 21 (2000), pp. 2257-2274, https://doi.org/10.1137/S1064827597327309. · Zbl 0962.65038
[46] V. Simoncini, Computational methods for linear matrix equations, SIAM Rev., 58 (2016), pp. 377-441, https://doi.org/10.1137/130912839. · Zbl 1386.65124
[47] R. Vandebril, M. Van Barel, and N. Mastronardi, Matrix Computations and Semiseparable Matrices, Volume 1: Linear Systems, Johns Hopkins University Press, Baltimore, MD, 2008. · Zbl 1141.65019
[48] R. Vandebril, M. Van Barel, and N. Mastronardi, Matrix Computations and Semiseparable Matrices, Volume 2: Eigenvalue and Singular Value Methods, Johns Hopkins University Press, Baltimore, MD, 2008. · Zbl 1175.65045
[49] J. Vogel, J. Xia, S. Cauley, and V. Balakrishnan, Superfast divide-and-conquer method and perturbation analysis for structured eigenvalue solutions, SIAM J. Sci. Comput., 38 (2016), pp. A1358-A1382, https://doi.org/10.1137/15M1018812. · Zbl 1338.65104
[50] A. Šušnjara and D. Kressner, A Fast Spectral Divide-and-Conquer Method for Banded Matrices, arXiv:1801.04175, 2018. · Zbl 1373.65023
[51] 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 (2016), 21, https://doi.org/10.1145/2830569. · Zbl 1369.65050
[52] 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 (2014), pp. 44-72, https://doi.org/10.1137/120895755. · Zbl 1300.65018
[53] 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 (2009), pp. 1382-1411, https://doi.org/10.1137/09074543X. · Zbl 1195.65031
[54] J. Xia, S. Chandrasekaran, M. Gu, and X. S. Li, Fast algorithms for hierarchically semiseparable matrices, Numer. Linear Algebra Appl., 17 (2010), pp. 953-976, https://doi.org/10.1002/nla.691. · Zbl 1240.65087
[55] J. Xia, Y. Xi, and M. Gu, A superfast structured solver for Toeplitz linear systems via randomized sampling, SIAM J. Matrix Anal. Appl., 33 (2012), pp. 837-858, https://doi.org/10.1137/110831982. · Zbl 1258.65030
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.