{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T21:14:30Z","timestamp":1782940470521,"version":"3.54.5"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2019,2,24]],"date-time":"2019-02-24T00:00:00Z","timestamp":1550966400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100008982","name":"QNRF","doi-asserted-by":"crossref","award":["NPRP-5-995-2-415"],"award-info":[{"award-number":["NPRP-5-995-2-415"]}],"id":[{"id":"10.13039\/100008982","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2019,3,31]]},"abstract":"<jats:p>Hierarchical matrices are space- and time-efficient representations of dense matrices that exploit the low-rank structure of matrix blocks at different levels of granularity. The hierarchically low-rank block partitioning produces representations that can be stored and operated on in near-linear complexity instead of the usual polynomial complexity of dense matrices.<\/jats:p>\n          <jats:p>\n            In this article, we present high-performance implementations of matrix vector multiplication and compression operations for the\n            <jats:italic>H<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            variant of hierarchical matrices on GPUs. The\n            <jats:italic>H<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            variant exploits, in addition to the hierarchical block partitioning, hierarchical bases for the block representations and results in a scheme that requires only\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) storage and\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) complexity for the mat-vec and compression kernels. These two operations are at the core of algebraic operations for hierarchical matrices, the mat-vec being a ubiquitous operation in numerical algorithms while compression\/recompression represents a key building block for other algebraic operations, which require periodic recompression during execution.\n          <\/jats:p>\n          <jats:p>The difficulties in developing efficient GPU algorithms come primarily from the irregular tree data structures that underlie the hierarchical representations, and the key to performance is to recast the computations on flattened trees in ways that allow batched linear algebra operations to be performed. This requires marshaling the irregularly laid out data in a way that allows them to be used by the batched routines. Marshaling operations only involve pointer arithmetic with no data movement and as a result have minimal overhead.<\/jats:p>\n          <jats:p>Our numerical results on covariance matrices from 2D and 3D problems from spatial statistics show the high efficiency our routines achieve over 550GB\/s for the bandwidth-limited matrix-vector operation and over 850GFLOPS\/s in sustained performance for the compression operation on the P100 Pascal GPU.<\/jats:p>","DOI":"10.1145\/3232850","type":"journal-article","created":{"date-parts":[[2019,2,25]],"date-time":"2019-02-25T13:23:28Z","timestamp":1551101008000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":22,"title":["Hierarchical Matrix Operations on GPUs"],"prefix":"10.1145","volume":"45","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2958-9344","authenticated-orcid":false,"given":"Wajih","family":"Boukaram","sequence":"first","affiliation":[{"name":"Extreme Computing Research Center, KAUST"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"George","family":"Turkiyyah","sequence":"additional","affiliation":[{"name":"American University of Beirut, Lebanon"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Keyes","sequence":"additional","affiliation":[{"name":"Extreme Computing Research Center, KAUST"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,2,24]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2818311"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.3874"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10915-013-9714-z"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2015.2448083"},{"key":"e_1_2_1_5_1","volume-title":"Matrices with Hierarchical Low-Rank Structures","author":"Ballani Jonas","unstructured":"Jonas Ballani and Daniel Kressner . 2016. Matrices with Hierarchical Low-Rank Structures . Springer International Publishing , Cham , 161--209. Jonas Ballani and Daniel Kressner. 2016. Matrices with Hierarchical Low-Rank Structures. Springer International Publishing, Cham, 161--209."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/110838844"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1654059.1654078"},{"key":"e_1_2_1_8_1","volume-title":"Thrust: A productivity-oriented library for CUDA. In GPU Computing Gems Jade Edition","author":"Bell Nathan","year":"2011","unstructured":"Nathan Bell and Jared Hoberock . 2011 . Thrust: A productivity-oriented library for CUDA. In GPU Computing Gems Jade Edition . Elsevier , 359--371. Nathan Bell and Jared Hoberock. 2011. Thrust: A productivity-oriented library for CUDA. In GPU Computing Gems Jade Edition. Elsevier, 359--371."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00607-004-0106-y"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00211-009-0278-7"},{"key":"e_1_2_1_11_1","volume-title":"Efficient Numerical Methods for Non-local Operators: H<sup>2<\/sup>-matrix Compression, Algorithms, and Analysis. EMS tracts in mathematics","author":"B\u00f6rm Steffen","unstructured":"Steffen B\u00f6rm . 2010b. Efficient Numerical Methods for Non-local Operators: H<sup>2<\/sup>-matrix Compression, Algorithms, and Analysis. EMS tracts in mathematics , Vol. 14 . European Mathematical Society . Steffen B\u00f6rm. 2010b. Efficient Numerical Methods for Non-local Operators: H<sup>2<\/sup>-matrix Compression, Algorithms, and Analysis. EMS tracts in mathematics, Vol. 14. European Mathematical Society."},{"key":"e_1_2_1_12_1","volume-title":"Approximation of BEM matrices using GPGPUs. arXiv abs\/1510.07244","author":"B\u00f6rm Steffen","year":"2015","unstructured":"Steffen B\u00f6rm and Sven Christophersen . 2015. Approximation of BEM matrices using GPGPUs. arXiv abs\/1510.07244 ( 2015 ). Steffen B\u00f6rm and Sven Christophersen. 2015. Approximation of BEM matrices using GPGPUs. arXiv abs\/1510.07244 (2015)."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00211-004-0564-3"},{"key":"e_1_2_1_14_1","volume-title":"Keyes","author":"Boukaram Wajih Halim","year":"2017","unstructured":"Wajih Halim Boukaram , George Turkiyyah , Hatem Ltaief , and David E . Keyes . 2017 . Batched QR and SVD algorithms on GPUs with applications in hierarchical matrix compression. Parallel Comput . (2017). Wajih Halim Boukaram, George Turkiyyah, Hatem Ltaief, and David E. Keyes. 2017. Batched QR and SVD algorithms on GPUs with applications in hierarchical matrix compression. Parallel Comput. (2017)."},{"key":"e_1_2_1_15_1","volume-title":"GPU-STREAM v2.0: Benchmarking the Achievable Memory Bandwidth of Many-Core Processors Across Diverse Parallel Programming Models. ISC High Performance","author":"Deakin Tom","year":"2016","unstructured":"Tom Deakin , James Price , Matt Martineau , and Simon McIntosh-Smith . 2016. GPU-STREAM v2.0: Benchmarking the Achievable Memory Bandwidth of Many-Core Processors Across Diverse Parallel Programming Models. ISC High Performance 2016 . Lecture Notes in Computer Science, Vol. 9945 . Springer , 489--507. Tom Deakin, James Price, Matt Martineau, and Simon McIntosh-Smith. 2016. GPU-STREAM v2.0: Benchmarking the Achievable Memory Bandwidth of Many-Core Processors Across Diverse Parallel Programming Models. ISC High Performance 2016. Lecture Notes in Computer Science, Vol. 9945. Springer, 489--507."},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Dongarra et al. 2014. Numerical Computations with GPUs. In Accelerating Numerical Dense Linear Algebra Calculations with GPUs. Springer 1--26.  Dongarra et al. 2014. Numerical Computations with GPUs. In Accelerating Numerical Dense Linear Algebra Calculations with GPUs. Springer 1--26.","DOI":"10.1007\/978-3-319-06548-9_1"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3017994"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11464-012-0188-3"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00607-003-0019-1"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00607-002-1470-0"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00211-009-0218-6"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s006070050015"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47324-5"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00607-002-1450-4"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/333825.333827"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00607-004-0080-4"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2716282.2716288"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00791-014-0226-7"},{"key":"e_1_2_1_29_1","unstructured":"Ronald Kriemann. 2016. H-lib Pro. Retrieved from www.hlibpro.com.  Ronald Kriemann. 2016. H -lib Pro. Retrieved from www.hlibpro.com."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2013.02.019"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/3014904.3014982"},{"key":"e_1_2_1_32_1","unstructured":"NVIDIA. 2016a. cuBLAS Library Documentation (v8.0). https:\/\/docs.nvidia.com\/cuda\/cublas\/.  NVIDIA. 2016a. cuBLAS Library Documentation (v8.0). https:\/\/docs.nvidia.com\/cuda\/cublas\/."},{"key":"e_1_2_1_33_1","unstructured":"NVIDIA. 2016b. cuSPARSE Library Documentation (v8.0). https:\/\/docs.nvidia.com\/cuda\/cusparse.  NVIDIA. 2016b. cuSPARSE Library Documentation (v8.0). https:\/\/docs.nvidia.com\/cuda\/cusparse."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1002\/nla.691"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.14529\/jsfi140104"},{"key":"e_1_2_1_36_1","unstructured":"Peter Zaspel. 2017. Algorithmic patterns for H-matrices on many-core processors. CoRR abs\/1708.09707. Retrieved from http:\/\/arxiv.org\/abs\/1708.09707.  Peter Zaspel. 2017. Algorithmic patterns for H-matrices on many-core processors. CoRR abs\/1708.09707. Retrieved from http:\/\/arxiv.org\/abs\/1708.09707."}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3232850","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3232850","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:41:10Z","timestamp":1750282870000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3232850"}},"subtitle":["Matrix-Vector Multiplication and Compression"],"short-title":[],"issued":{"date-parts":[[2019,2,24]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,3,31]]}},"alternative-id":["10.1145\/3232850"],"URL":"https:\/\/doi.org\/10.1145\/3232850","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"value":"0098-3500","type":"print"},{"value":"1557-7295","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,2,24]]},"assertion":[{"value":"2017-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-02-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}