{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,15]],"date-time":"2026-09-15T02:56:28Z","timestamp":1789440988035,"version":"build-2803163510"},"reference-count":37,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1255416"],"award-info":[{"award-number":["DMS-1255416"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2017,1]]},"abstract":"<jats:p>We design a distributed-memory randomized structured multifrontal solver for large sparse matrices. Two layers of hierarchical tree parallelism are used. A sequence of innovative parallel methods are developed for randomized structured frontal matrix operations, structured update matrix computation, skinny extend-add operation, selected entry extraction from structured matrices, etc. Several strategies are proposed to reuse computations and reduce communications. Unlike an earlier parallel structured multifrontal method that still involves large dense intermediate matrices, our parallel solver performs the major operations in terms of skinny matrices and fully structured forms. It thus significantly enhances the efficiency and scalability. Systematic communication cost analysis shows that the numbers of words are reduced by factors of about $O(\\sqrt{n}\/r)$ in two dimensions and about $O(n^{2\/3}\/r)$ in three dimensions, where $n$ is the matrix size and $r$ is an off-diagonal numerical rank bound of the intermediate frontal matrices. The efficiency and parallel performance are demonstrated with the solution of some large discretized PDEs in two and three dimensions. Nice scalability and significant savings in the cost and memory can be observed from the weak and strong scaling tests, especially for some 3D problems discretized on unstructured meshes.<\/jats:p>","DOI":"10.1137\/16m1079221","type":"journal-article","created":{"date-parts":[[2017,8,17]],"date-time":"2017-08-17T15:26:15Z","timestamp":1502983575000},"page":"C292-C318","source":"Crossref","is-referenced-by-count":5,"title":["A Distributed-Memory Randomized Structured Multifrontal Method for Sparse Direct Solutions"],"prefix":"10.1137","volume":"39","author":[{"given":"Zixing","family":"Xin","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jianlin","family":"Xia","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Maarten V.","family":"de Hoop","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stephen","family":"Cauley","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Venkataramanan","family":"Balakrishnan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2017,8,17]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1007\/s10915-013-9714-z"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/120903476"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/S0045-7825(99)00242-X"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719642"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1007\/s00607-002-1450-4"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479803436652"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1137\/090775932"},{"key":"atypb8","volume-title":"LAPACK Working Note 73","author":"Clint Whaley R.","year":"1994"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1145\/356044.356047"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1137\/0710032"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(89)90101-4"},{"key":"atypb12","first-page":"236","volume":"13","author":"Gibbs N.","year":"1976","journal-title":"SIAM J. Sci. Comput."},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1137\/130918988"},{"key":"atypb15","first-page":"661","volume-title":"Domain Decomposition Methods in Science and Engineering XVI","author":"Grasedyck L.","year":"2006"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1137\/0917055"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1007\/s00607-004-0080-4"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1137\/090771806"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595287997"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1145\/779359.779361"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0709640104"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1137\/1034004"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1137\/15M1023774"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1137\/100786617"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0031609"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1137\/0914074"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2011.10.013"},{"key":"atypb28","first-page":"42","author":"Wang S.","year":"2016","journal-title":"ACM Trans. Math. Software"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1137\/110848062"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1137\/120867032"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1137\/12087116X"},{"key":"atypb32","unstructured":"J. Xia,\n                      Multilayer Hierarchically Semiseparable Structures\n                      , GMIG Report 15-16, Purdue University, 2015."},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1137\/09074543X"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1002\/nla.691"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1137\/110831982"},{"key":"atypb36","unstructured":"Z. Xin, J. Xia, M. V. de Hoop, S. Cauley, and V. Balakrishnan,\n                      Parallel Randomized Structured Multifrontal Method for General Sparse Matrices\n                      , GMIG Report 14-17, Purdue University, 2014."},{"key":"atypb37","unstructured":"Z. Xin, J. Xia, M. V. de Hoop, S. Cauley, and V. Balakrishnan,\n                      Scalable Randomized Structured Multifrontal Method for Large-Scale Sparse Direct Solutions\n                      , GMIG Report 15-14, Purdue University, 2015."},{"key":"atypb38","unstructured":"Z. Xin, J. Xia, M. V. de Hoop, S. Cauley, and V. Balakrishnan,\n                      A Distributed-Memory Randomized Structured Multifrontal Method for Sparse Direct Solutions\n                      , GMIG Report 9, Rice University, 2016, pp. 169-189."}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/16M1079221","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:58:53Z","timestamp":1787335133000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/16M1079221"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1]]},"references-count":37,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,1]]}},"alternative-id":["10.1137\/16M1079221"],"URL":"https:\/\/doi.org\/10.1137\/16m1079221","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,1]]}}}