Adaptive fast multiplication of ℋ²-matrices

Börm, Steffen

doi:10.1090/mcom/3978

Adaptive fast multiplication of $\mathcal {H}^2$-matrices
HTML articles powered by AMS MathViewer

by Steffen Börm;

Math. Comp. 94 (2025), 825-852

DOI: https://doi.org/10.1090/mcom/3978

Published electronically: April 22, 2024

HTML | PDF | Request permission

Abstract:

Hierarchical matrices approximate a given matrix by a decomposition into low-rank submatrices that can be handled efficiently in factorized form. $\mathcal {H}^2$-matrices refine this representation following the ideas of fast multipole methods in order to achieve linear, i.e., optimal complexity for a variety of important algorithms.

The matrix multiplication, a key component of many more advanced numerical algorithms, has been a challenge: the only linear-time algorithms known so far either require the very special structure of HSS-matrices or need to know a suitable basis for all submatrices in advance.

In this article, a new and fairly general algorithm for multiplying $\mathcal {H}^2$-matrices in linear complexity with adaptively constructed bases is presented. The algorithm consists of two phases: first an intermediate representation with a generalized block structure is constructed, then this representation is re-compressed in order to match the structure prescribed by the application.

The complexity and accuracy are analyzed and numerical experiments indicate that the new algorithm can indeed be significantly faster than previous attempts.

References

Christopher R. Anderson, An implementation of the fast multipole method without multipoles, SIAM J. Sci. Statist. Comput. 13 (1992), no. 4, 923–947. MR 1166169, DOI 10.1137/0913055
Mario Bebendorf and Wolfgang Hackbusch, Existence of $\scr H$-matrix approximants to the inverse FE-matrix of elliptic operators with $L^\infty$-coefficients, Numer. Math. 95 (2003), no. 1, 1–28. MR 1993936, DOI 10.1007/s00211-002-0445-6
S. Börm, ${\scr H}^2$-matrix arithmetics in linear complexity, Computing 77 (2006), no. 1, 1–28. MR 2207953, DOI 10.1007/s00607-005-0146-y
Steffen Börm, Efficient numerical methods for non-local operators, EMS Tracts in Mathematics, vol. 14, European Mathematical Society (EMS), Zürich, 2010. $\scr H^2$-matrix compression, algorithms and analysis. MR 2767920, DOI 10.4171/091
Steffen Börm and Lars Grasedyck, Hybrid cross approximation of integral operators, Numer. Math. 101 (2005), no. 2, 221–249. MR 2195343, DOI 10.1007/s00211-005-0618-1
W. Hackbusch and S. Börm, Data-sparse approximation by adaptive $\scr H^2$-matrices, Computing 69 (2002), no. 1, 1–35. MR 1954142, DOI 10.1007/s00607-002-1450-4
Wolfgang Hackbusch and Steffen Börm, ${\scr H}^2$-matrix approximation of integral operators by interpolation, Appl. Numer. Math. 43 (2002), no. 1-2, 129–143. 19th Dundee Biennial Conference on Numerical Analysis (2001). MR 1936106, DOI 10.1016/S0168-9274(02)00121-6
Steffen Börm, Maike Löhndorf, and Jens M. Melenk, Approximation of integral operators by variable-order interpolation, Numer. Math. 99 (2005), no. 4, 605–643. MR 2121071, DOI 10.1007/s00211-004-0564-3
Steffen Börm and Knut Reimer, Efficient arithmetic operations for rank-structured matrices based on hierarchical low-rank updates, Comput. Vis. Sci. 16 (2013), no. 6, 247–258. MR 3319575, DOI 10.1007/s00791-015-0233-3
Steffen Börm and Stefan A. Sauter, BEM with linear complexity for the classical boundary integral operators, Math. Comp. 74 (2005), no. 251, 1139–1177. MR 2136997, DOI 10.1090/S0025-5718-04-01733-8
S. Chandrasekaran, M. Gu, and W. Lyons, A fast adaptive solver for hierarchically semiseparable representations, Calcolo 42 (2005), no. 3-4, 171–185. MR 2191196, DOI 10.1007/s10092-005-0103-3
S. Chandrasekaran, M. Gu, and T. Pals, A fast ULV decomposition solver for hierarchically semiseparable representations, SIAM J. Matrix Anal. Appl. 28 (2006), no. 3, 603–622. MR 2262971, DOI 10.1137/S0895479803436652
Jürgen Dölz, Helmut Harbrecht, and Michael D. Multerer, On the best approximation of the hierarchical matrix product, SIAM J. Matrix Anal. Appl. 40 (2019), no. 1, 147–174. MR 3904427, DOI 10.1137/18M1189373
Ivan P. Gavrilyuk, Wolfgang Hackbusch, and Boris N. Khoromskij, $\scr H$-matrix approximation for the operator exponential with applications, Numer. Math. 92 (2002), no. 1, 83–111. MR 1917366, DOI 10.1007/s002110100360
Ivan P. Gavrilyuk, Wolfgang Hackbusch, and Boris N. Khoromskij, Data-sparse approximation to the operator-valued functions of elliptic operator, Math. Comp. 73 (2004), no. 247, 1297–1324. MR 2047088, DOI 10.1090/S0025-5718-03-01590-4
Zydrunas Gimbutas and Vladimir Rokhlin, A generalized fast multipole method for nonoscillatory kernels, SIAM J. Sci. Comput. 24 (2002), no. 3, 796–817. MR 1950512, DOI 10.1137/S1064827500381148
L. Grasedyck, Existence of a low rank or $\scr H$-matrix approximant to the solution of a Sylvester equation, Numer. Linear Algebra Appl. 11 (2004), no. 4, 371–389. MR 2057708, DOI 10.1002/nla.366
Lars Grasedyck and Wolfgang Hackbusch, Construction and arithmetics of $\scr H$-matrices, Computing 70 (2003), no. 4, 295–334. MR 2011419, DOI 10.1007/s00607-003-0019-1
L. Grasedyck, W. Hackbusch, and B. N. Khoromskij, Solution of large scale algebraic matrix Riccati equations by use of hierarchical matrices, Computing 70 (2003), no. 2, 121–165. MR 1982969, DOI 10.1007/s00607-002-1470-0
Lars Grasedyck, Ronald Kriemann, and Sabine Le Borne, Domain decomposition based $\scr H$-LU preconditioning, Numer. Math. 112 (2009), no. 4, 565–600. MR 2507619, DOI 10.1007/s00211-009-0218-6
L. Greengard and V. Rokhlin, A fast algorithm for particle simulations, J. Comput. Phys. 73 (1987), no. 2, 325–348. MR 918448, DOI 10.1016/0021-9991(87)90140-9
Leslie Greengard and Vladimir Rokhlin, A new version of the fast multipole method for the Laplace equation in three dimensions, Acta numerica, 1997, Acta Numer., vol. 6, Cambridge Univ. Press, Cambridge, 1997, pp. 229–269. MR 1489257, DOI 10.1017/S0962492900002725
W. Hackbusch, A sparse matrix arithmetic based on $\scr H$-matrices. I. Introduction to $\scr H$-matrices, Computing 62 (1999), no. 2, 89–108. MR 1694265, DOI 10.1007/s006070050015
Wolfgang Hackbusch, Hierarchical matrices: algorithms and analysis, Springer Series in Computational Mathematics, vol. 49, Springer, Heidelberg, 2015. MR 3445676, DOI 10.1007/978-3-662-47324-5
W. Hackbusch, B. N. Khoromskij, and R. Kriemann, Hierarchical matrices based on a weak admissibility criterion, Computing 73 (2004), no. 3, 207–243. MR 2106249, DOI 10.1007/s00607-004-0080-4
W. Hackbusch, B. Khoromskij, and S. A. Sauter, On $\scr H^2$-matrices, Lectures on applied mathematics (Munich, 1999) Springer, Berlin, 2000, pp. 9–29. MR 1767761
Diana Halikias and Alex Townsend, Structured matrix recovery from matrix-vector products, Numer. Linear Algebra Appl. 31 (2024), no. 1, Paper No. e2531, 27. MR 4677356, DOI 10.1002/nla.2531
Kristen Ann Lessel, Advancements in Algorithms for Approximations of Rank Structured Matrices, ProQuest LLC, Ann Arbor, MI, 2020. Thesis (Ph.D.)–University of California, Santa Barbara. MR 4106349
J. Levitt and P.-G. Martinsson, Linear-complexity black-box randomized compression of rank-structured matrices, Technical Report, arXiv:2205.02990, 2022.
Lin Lin, Jianfeng Lu, and Lexing Ying, Fast construction of hierarchical matrix representation from matrix-vector multiplication, J. Comput. Phys. 230 (2011), no. 10, 4071–4087. MR 2783833, DOI 10.1016/j.jcp.2011.02.033
M. Ma and D. Jiao, Accuracy directly controlled fast direct solution of general $\mathcal {H}^2$-matrices and its application to solving electrodynamic volume integral equations, IEEE Trans. Microw. Theory Tech. 66 (2018), no. 1, 35–48.
Q. Ma, S. Deshmukh, and R. Yokota, Scalable linear time dense direct solver for 3-D problems without trailing sub-matrix dependencies, Technical Report, Tokyo Institute of Technology, arXiv:2208.10907, 2022.
V. Rokhlin, Rapid solution of integral equations of classical potential theory, J. Comput. Phys. 60 (1985), no. 2, 187–207. MR 805870, DOI 10.1016/0021-9991(85)90002-6
Volker Strassen, Gaussian elimination is not optimal, Numer. Math. 13 (1969), 354–356. MR 248973, DOI 10.1007/BF02165411
Jianlin Xia, Shivkumar Chandrasekaran, Ming Gu, and Xiaoye S. Li, Fast algorithms for hierarchically semiseparable matrices, Numer. Linear Algebra Appl. 17 (2010), no. 6, 953–976. MR 2759603, DOI 10.1002/nla.691