Data-driven construction of hierarchical matrices with nested bases. (English) Zbl 07837042
Summary: Hierarchical matrices provide a powerful representation for significantly reducing the computational complexity associated with dense kernel matrices. For example, the fast multipole method (FMM) and its variants are highly efficient when the kernel function is related to fundamental solutions of classical elliptic PDEs. For general kernel functions, interpolation-based methods are widely used for the efficient construction of hierarchical matrices. In this paper, we present a fast hierarchical data reduction (HiDR) procedure with \(O(n)\) complexity for the memory-efficient construction of hierarchical matrices with nested bases where \(n\) is the number of data points. HiDR aims to reduce the given data in a hierarchical way so as to obtain \(O(1)\) representations for all nearfield and farfield interactions. Based on HiDR, a linear complexity \(\mathcal{H}^2\) matrix construction algorithm is proposed. The use of data-driven methods enables better efficiency than other general-purpose methods and flexible computation without accessing the kernel function. Experiments demonstrate significantly improved memory efficiency of the proposed data-driven method compared to interpolation-based methods over a wide range of kernels. For the Coulomb kernel, the proposed general-purpose algorithm offers competitive performance compared to FMM and its variants, such as PVFMM. The data-driven approach not only works for general kernels but also leads to much smaller precomputation costs compared to PVFMM.
MSC:
| 68W25 | Approximation algorithms |
| 65D40 | Numerical approximation of high-dimensional functions; sparse grids |
Keywords:
hierarchical matrix; kernel matrix; data-driven construction; complexity analysis; data reduction; GaussianReferences:
| [1] | Anderson, C. R., An implementation of the fast multipole method without multipoles, SIAM J. Sci. Statist. Comput., 13 (1992), pp. 923-947. · Zbl 0754.65101 |
| [2] | Atkinson, K., Convergence rates for approximate eigenvalues of compact integral operators, SIAM J. Numer. Anal., 12 (1975), pp. 213-222. · Zbl 0295.65073 |
| [3] | Atkinson, K. E., The numerical solution of the eigenvalue problem for compact integral operators, Trans. Amer. Math. Soc., 129 (1967), pp. 458-465. · Zbl 0177.18803 |
| [4] | Barnes, J. and Hut, P., A hierarchical O(N log N) force-calculation algorithm, Nature, 324 (1986), pp. 446-449. |
| [5] | Bebendorf, M., Approximation of boundary element matrices, Numer. Math., 86 (2000), pp. 565-589. · Zbl 0966.65094 |
| [6] | Bebendorf, M. and Venn, R., Constructing nested bases approximations from the entries of non-local operators, Numer. Math., 121 (2012), pp. 609-635. · Zbl 1252.65206 |
| [7] | Bishop, C. M., Pattern Recognition and Machine Learning, Springer, New York, 2006. · Zbl 1107.68072 |
| [8] | Börm, S. and Grasedyck, L., Hybrid cross approximation of integral operators, Numer. Math., 101 (2005), pp. 221-249. · Zbl 1104.65120 |
| [9] | Börm, S., Grasedyck, L., and Hackbusch, W., Introduction to hierarchical matrices with applications, Eng. Anal. Bound. Elem., 27 (2003), pp. 405-422. · Zbl 1035.65042 |
| [10] | Cai, D., Physics-Informed Distribution Transformers via Molecular Dynamics and Deep Neural Networks, preprint, https://ssrn.com/abstract=4028725, 2022. |
| [11] | Cai, D. and Cai, Z., Hybrid A Posteriori Error Estimators for Conforming Finite Element Approximations to Stationary Convection-Diffusion-Reaction Equations, preprint, arXiv:2107.06341, 2021. |
| [12] | Cai, D. and Cai, Z., A hybrid a posteriori error estimator for conforming finite element approximations, Comput. Methods Appl. Math. Engrg., 339 (2018), pp. 320-340. · Zbl 1440.65187 |
| [13] | Cai, D., Cai, Z., and Zhang, S., Robust equilibrated a posteriori error estimator for higher order finite element approximations to diffusion problems, Numer. Math., 144 (2020), pp. 1-21. · Zbl 1447.65130 |
| [14] | Cai, D., Cai, Z., and Zhang, S., Robust equilibrated error estimator for diffusion problems: Mixed finite elements in two dimensions, J. Sci. Comput., 83 (2020), pp. 1-22. · Zbl 1437.65177 |
| [15] | Cai, D., Chow, E., Erlandson, L., Saad, Y., and Xi, Y., SMASH: Structured matrix approximation by separation and hierarchy, Numer. Linear Algebra Appl., 25 (2018), e2204. · Zbl 1513.65128 |
| [16] | Cai, D., Chow, E., and Xi, Y., Data-Driven Linear Complexity Low-Rank Approximation of General Kernel Matrices: A Geometric Approach, preprint, 2022, https://arxiv.org/pdf/2212.12674.pdf. |
| [17] | Cai, D., Nagy, J., and Xi, Y., Fast deterministic approximation of symmetric indefinite kernel matrices with high dimensional datasets, SIAM J. Matrix Anal. Appl., 43 (2022), pp. 1003-1028, doi:10.1137/21M1424627. · Zbl 1508.65040 |
| [18] | Cai, D. and Vassilevski, P. S., Eigenvalue problems for exponential-type kernels, Comput. Methods Appl. Math., 20 (2020), pp. 61-78. · Zbl 1437.65230 |
| [19] | Cai, D. and Xia, J., A stable matrix version of the fast multipole method: Stabilization strategies and examples, Electron. Trans. Numer. Anal., 54 (2021), pp. 581-609. · Zbl 1475.65026 |
| [20] | Cao, Y., Wen, L., and Rong, J., A SVD accelerated kernel-independent fast multipole method and its application to BEM, WIT Trans. Model. Simul., 56 (2013), pp. 431-443. · Zbl 1292.65130 |
| [21] | Cheng, H., Gimbutas, Z., Martinsson, P.-G., and Rokhlin, V., On the compression of low rank matrices, SIAM J. Sci. Comput., 26 (2005), pp. 1389-1404. · Zbl 1083.65042 |
| [22] | Cheng, H., Greengard, L., and Rokhlin, V., A fast adaptive multipole algorithm in three dimensions, J. Comput. Phys., 155 (1999), pp. 468-498. · Zbl 0937.65126 |
| [23] | Colton, D. and Kress, R., Integral Equation Methods in Scattering Theory, , Wiley, New York, 1983. · Zbl 0522.35001 |
| [24] | Decoste, D. and Schölkopf, B., Training invariant support vector machines, Mach. Learn., 46 (2002), pp. 161-190. · Zbl 0998.68102 |
| [25] | Eldar, Y., Lindenbaum, M., Porat, M., and Zeevi, Y. Y., The farthest point strategy for progressive image sampling, IEEE Trans. Image Process., 6 (1997), pp. 1305-1315. |
| [26] | Erlandson, L., Cai, D., Xi, Y., and Chow, E.. Accelerating parallel hierarchical matrix-vector products via data-driven sampling, in 2020 IEEE International Parallel and Distributed Processing Symposium (IPDPS), , 2020, pp. 749-758. |
| [27] | Fornberg, B. and Wright, G., Stable computation of multiquadric interpolants for all values of the shape parameter, Comput. Math. Appl., 48 (2004), pp. 853-867. · Zbl 1072.41001 |
| [28] | Gillman, A., Young, P. M., and Martinsson, P.-G., A direct solver with o(n) complexity for integral equations on one-dimensional domains, Front. Math. China, 7 (2012), pp. 217-247. · Zbl 1262.65198 |
| [29] | Greengard, L. and Rokhlin, V., A fast algorithm for particle simulations, J. Comput. Phys., 73 (1987), pp. 325-348. · Zbl 0629.65005 |
| [30] | Gu, M. and Eisenstat, S. C., Efficient algorithms for computing a strong rank-revealing QR factorization, SIAM J. Sci. Comput., 17 (1996), pp. 848-869. · Zbl 0858.65044 |
| [31] | Hackbusch, W., Hierarchical Matrices: Algorithms and Analysis, , Springer-Verlag, Berlin, 2015. · Zbl 1336.65041 |
| [32] | Hackbusch, W. and Börm, S., \( \mathcal{H}^2\) -matrix approximation of integral operators by interpolation, Appl. Numer. Math., 43 (2002), pp. 129-143. · Zbl 1019.65103 |
| [33] | Hackbusch, W., Khoromskij, B., and Sauter, S.. On \(\mathcal{H}^2\) -matrices, in Lectures on Applied Mathematics, Bungartz, H.-J., Hoppe, R. H. W., and Zenger, C., eds., Springer-Verlag, Berlin, 2000, pp. 9-29. · Zbl 0963.65043 |
| [34] | Hackbusch, W., Khoromskij, B. N., and Kriemann, R., Hierarchical matrices based on a weak admissibility criterion, Computing, 73 (2004), pp. 207-243. · Zbl 1063.65035 |
| [35] | Huang, H., Xing, X., and Chow, E., H2Pack: High-performance H-2 matrix package for kernel matrices using the proxy point method, ACM Trans. Math. Softw., 47 (2020), pp. 1-29. · Zbl 07467963 |
| [36] | Keller, H. B., On the accuracy of finite difference approximations to the eigenvalues of differential and integral operators, Numer. Math., 7 (1965), pp. 412-419. · Zbl 0135.37702 |
| [37] | Liu, Y., Sid-Lakhdar, W., Rebrova, E., Ghysels, P., and Li, X. S., A parallel hierarchical blocked adaptive cross approximation algorithm, Int. J. High Perform. Comput. Appl., 34 (2020), pp. 394-408. |
| [38] | Malhotra, D. and Biros, G., Pvfmm: A parallel kernel independent fmm for particle and volume potentials, Commun. Comput. Phys., 18 (2015), pp. 808-830. · Zbl 1388.65169 |
| [39] | Martinsson, P. and Rokhlin, V., A fast direct solver for boundary integral equations in two dimensions, J. Comput. Phys., 205 (2005), pp. 1-23. · Zbl 1078.65112 |
| [40] | Osborn, J., Spectral approximation for compact operators, Math. Comput., 29 (1975), pp. 712-725. · Zbl 0315.35068 |
| [41] | Peyré, G. and Cohen, L. D., Geodesic remeshing using front propagation, Int. J. Comput. Vis., 69 (2006), pp. 145-156. |
| [42] | Rokhlin, V., Rapid solution of integral equations of classical potential theory, J. Comput. Phys., 60 (1985), pp. 187-207. · Zbl 0629.65122 |
| [43] | Rokhlin, V., Rapid solution of integral equations of scattering theory in two dimensions, J. Comput. Phys., 86 (1990), pp. 414-439. · Zbl 0686.65079 |
| [44] | Schlömer, T., Heck, D., and Deussen, O.. Farthest-point optimized point sets with maximized minimum distance, in Proceedings of the ACM SIGGRAPH Symposium on High Performance Graphics, , 2011, pp. 135-142. |
| [45] | Spence, A., Error bounds and estimates for eigenvalues of integral equations, Numer. Math., 29 (1978), pp. 133-147. · Zbl 0358.65109 |
| [46] | Sun, X. and Pitsianis, N., A matrix version of the fast multipole method, SIAM Rev., 43 (2001), pp. 289-300. · Zbl 0974.65109 |
| [47] | Ying, L., Biros, G., and Zorin, D., A kernel-independent adaptive fast multipole algorithm in two and three dimensions, J. Comput. Phys., 196 (2004), pp. 591-626. · Zbl 1053.65095 |
| [48] | Zhao, Y., Jiao, D., and Mao, J., Fast nested cross approximation algorithm for solving large-scale electromagnetic problems, IEEE Trans. Microw. Theory, 67 (2019), pp. 3271-3283. |
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.
