{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,24]],"date-time":"2026-08-24T03:35:42Z","timestamp":1787542542226,"version":"build-2736575974"},"reference-count":51,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","funder":[{"name":"Women Leading IITM, India, in Mathematics","award":["SB22230053MAIITM008880"],"award-info":[{"award-number":["SB22230053MAIITM008880"]}]},{"name":"MATRICS","award":["Sanction MTR\/2019\/001241"],"award-info":[{"award-number":["Sanction MTR\/2019\/001241"]}]},{"name":"YSRA","award":["BRNS, DAE (34\/20\/03\/2017-BRNS\/34278)"],"award-info":[{"award-number":["BRNS, DAE (34\/20\/03\/2017-BRNS\/34278)"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2023,10,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>This article introduces HODLR2D, a new hierarchical low-rank representation for a class of dense matrices arising out of [Formula: see text]-body problems in two dimensions. Using this new hierarchical framework, we propose a new fast matrix-vector product that scales almost linearly. We apply this fast matrix-vector product to accelerate the iterative solution of large dense linear systems arising out of radial basis function interpolation and discretized integral equation. The space and computational complexity of HODLR2D matrix-vector products scale as [Formula: see text], where [Formula: see text] is the maximum rank of the compressed matrix subblocks. For the logarithmic kernel function, we prove that [Formula: see text]. We also numerically observe a similar scaling for other kernel functions in 2D. We thereby demonstrate that the storage and computational complexity of HODLR2D matrix-vector products remain tractable for large [Formula: see text]. Additionally, we also study the parallel scalability of HODLR2D as part of this article.<\/jats:p>","DOI":"10.1137\/22m1491253","type":"journal-article","created":{"date-parts":[[2023,9,21]],"date-time":"2023-09-21T04:56:18Z","timestamp":1695272178000},"page":"A2382-A2408","source":"Crossref","is-referenced-by-count":3,"title":["HODLR2D: A New Class of Hierarchical Matrices"],"prefix":"10.1137","volume":"45","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4512-7497","authenticated-orcid":true,"given":"V. A","family":"Kandappan","sequence":"first","affiliation":[{"name":"Department of Mathematics, IIT Madras, India."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2742-1561","authenticated-orcid":true,"given":"Vaishnavi","family":"Gujjula","sequence":"additional","affiliation":[{"name":"Department of Mathematics, IIT Madras, India."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sivaram","family":"Ambikasaran","sequence":"additional","affiliation":[{"name":"Department of Mathematics, IIT Madras and Robert Bosch Centre for Data Science and AI (RBCDSAI), IIT Madras, India."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2023,9,21]]},"reference":[{"key":"ref1","doi-asserted-by":"crossref","unstructured":"K. Akbudak , \nH. Ltaief , \nA. Mikhalev , and \nD. Keyes  , Tile low rank Cholesky factorization for climate\/weather modeling applications on manycore architectures, in International Supercomputing Conference, Springer, 2017, pp. 22\u201340.","DOI":"10.1007\/978-3-319-58667-0_2"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1137\/15M102455X"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1007\/s10915-013-9714-z"},{"key":"ref4","unstructured":"S. Ambikasaran  and \nE. Darve  , The Inverse Fast Multipole Method, preprint, arXiv:1407.1572, 2014."},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1007\/s10596-013-9364-0"},{"key":"ref6","unstructured":"S. Ambikasaran , \nM. O\u2019Neil , and \nK. R. Singh  , Fast Symmetric Factorization of Hierarchical Matrices with Applications, preprint, arXiv:1405.0223, 2014."},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.21105\/joss.01167"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1137\/120903476"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1137\/16M1077192"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1137\/18M1182760"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1038\/324446a0"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611971538"},{"key":"ref13","series-title":"Numer. Math. Sci. Comput.","first-page":"1","volume-title":"Wavelets, Multilevel Methods and Elliptic PDEs","author":"Beatson R.","year":"1997"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1007\/PL00005410"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1007\/s00607-002-1469-6"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1007\/s00211-012-0449-9"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1137\/080720693"},{"key":"ref18","series-title":"Lecture Note 21","volume-title":"Hierarchical Matrices","author":"B\u00f6rm S.","year":"2003"},{"key":"ref19","doi-asserted-by":"crossref","unstructured":"S. Chandrasekaran , \nP. Dewilde , \nM. Gu , \nT. Pals , and \nA.J. van der Veen  , Fast stable solver for sequentially semi-separable linear systems of equations, in International Conference on High-Performance Computing, Springer, 2002, pp. 545\u2013554.","DOI":"10.1007\/3-540-36265-7_51"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejco.2022.100046"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1016\/j.cma.2016.05.029"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1006\/jcph.2000.6451"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1109\/8.933487"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2009.08.031"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1007\/s11464-012-0188-3"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1007\/s00607-003-0019-1"},{"key":"ref27","series-title":"Adv. Neural Inf. Process. Syst. 13","volume-title":"\u2018N-Body\u2019 Problems in Statistical Learning","author":"Gray A.","year":"2000"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1016\/0021-9991(87)90140-9"},{"key":"ref29","doi-asserted-by":"crossref","unstructured":"V. Gujjula  and \nS. Ambikasaran  , A New Directional Algebraic Fast Multipole Method Based Iterative Solver for the Lippmann-Schwinger Equation Accelerated with Hodlr Preconditioner, preprint, arXiv:2204.00326, 2022.","DOI":"10.4208\/cicp.OA-2022-0103"},{"key":"ref30","unstructured":"V. Gujjula  and \nS. Ambikasaran  , A New Nested Cross Approximation, preprint, arXiv:2203.14832, 2022."},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1137\/060662083"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1007\/PL00021408"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1007\/s00607-004-0080-4"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1007\/BF01396324"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.119.043901"},{"key":"ref36","first-page":"642","volume":"22","author":"Ida A.","year":"2014","journal-title":"J. Inf. Process."},{"key":"ref37","unstructured":"M. Izadi  , Hierarchical Matrix Techniques on Massively Parallel Computers, Ph.D. thesis, Leipzig University, 2012."},{"key":"ref38","unstructured":"R. Khan , \nV. Kandappan , and \nS. Ambikasaran  , Numerical Rank of Singular Kernel Functions, preprint, arXiv:2209.05819, 2022."},{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1137\/140964904"},{"key":"ref40","doi-asserted-by":"crossref","unstructured":"Y. Li , \nJ. Poulson , and \nL. Ying  , Distributed-Memory   \\(\\mathcal{H}\\)  -Matrix Algebra I: Data Distribution and Matrix-Vector Multiplication, preprint, arXiv:2008.12441, 2020.","DOI":"10.4208\/csiam-am.2020-0206"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1016\/j.csda.2019.02.002"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1137\/060662253"},{"key":"ref43","doi-asserted-by":"crossref","unstructured":"E. Rebrova , \nG. Ch\u00e1vez , \nY. Liu , \nP. Ghysels , and \nX. S. Li  , A study of clustering techniques and hierarchical matrix formats for kernel ridge regression, in 2018 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), IEEE, 2018, pp. 883\u2013892.","DOI":"10.1109\/IPDPSW.2018.00140"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.1016\/0021-9991(90)90107-C"},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1109\/TAP.2019.2896711"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1137\/0907058"},{"key":"ref47","doi-asserted-by":"publisher","DOI":"10.1007\/s006070070031"},{"key":"ref48","doi-asserted-by":"publisher","DOI":"10.1007\/s006070050015"},{"key":"ref49","doi-asserted-by":"crossref","unstructured":"R. Yokota , \nH. Ibeid , and \nD. Keyes  , Fast multipole method as a matrix-free hierarchical low-rank approximation, in International Workshop on Eigenvalue Problems: Algorithms, Software and Applications in Petascale Computing, Springer, 2015, pp. 267\u2013286.","DOI":"10.1007\/978-3-319-62426-6_17"},{"key":"ref50","doi-asserted-by":"publisher","DOI":"10.1109\/TEMC.2005.857898"},{"key":"ref51","doi-asserted-by":"publisher","DOI":"10.1109\/TMTT.2019.2920894"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/22M1491253","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T15:46:15Z","timestamp":1787327175000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/22M1491253"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,21]]},"references-count":51,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2023,10,31]]}},"alternative-id":["10.1137\/22M1491253"],"URL":"https:\/\/doi.org\/10.1137\/22m1491253","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,9,21]]}}}