{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T07:12:50Z","timestamp":1787382770122,"version":"build-2736575974"},"reference-count":39,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>In this paper we discuss a hypergraph-based unsymmetric nested dissection (HUND) ordering for reducing the fill-in incurred during Gaussian elimination. It has several important properties. It takes a global perspective of the entire matrix, as opposed to local heuristics. It takes into account the asymmetry of the input matrix by using a hypergraph to represent its structure. It is suitable for performing Gaussian elimination in parallel, with partial pivoting. This is possible because the row permutations performed due to partial pivoting do not destroy the column separators identified by the nested dissection approach. The hypergraph nested dissection approach is essentially equivalent to graph nested dissection on the matrix $A^{T}A$, but we need only the original matrix A and never form the usually denser matrix $A^{T}A$. The usage of hypergraphs in our approach is fairly standard, and HUND can be implemented by calling an existing hypergraph partitioner that uses recursive bisection. Our implementation uses local reordering constrained column approximate minimum degree (CCOLAMD) to further improve the ordering. We also explain how weighted matching (HSL routine MC64) can be used in this context. Experimental results on 27 medium and large size matrices with highly unsymmetric structures compare our approach to four other well-known reordering algorithms. The results show that it provides a robust reordering algorithm, in the sense that it is the best or close to the best (often within 10%) of all the other methods, in particular on matrices with highly unsymmetric structures.<\/jats:p>","DOI":"10.1137\/080720395","type":"journal-article","created":{"date-parts":[[2010,11,30]],"date-time":"2010-11-30T18:33:55Z","timestamp":1291142035000},"page":"3426-3446","source":"Crossref","is-referenced-by-count":20,"title":["Hypergraph-Based Unsymmetric Nested Dissection Ordering for Sparse LU Factorization"],"prefix":"10.1137","volume":"32","author":[{"given":"Laura","family":"Grigori","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Erik G.","family":"Boman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Simplice","family":"Donfack","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Timothy A.","family":"Davis","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2010,11,30]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479894278952"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1137\/050637315"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1137\/050622547"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1016\/S0045-7825(99)00242-X"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827502401953"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479801385037"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1109\/71.780863"},{"key":"R8","unstructured":"U. V. \u00c7ataly\u00fcrek and C. Aykanat,\n                      PaToH: Partitioning tool for hypergraphs, User's Guide\n                      , 1999."},{"key":"R9","unstructured":"U. V. \u00c7ataly\u00fcrek, C. Aykanat, and E. Kayaaslan,\n                      Hypergraph-partitioning-based Fill-reducing Ordering\n                      , Technical report OSU-BMI-TR-2009-n02, Ohio State University, 2009, submitted for publication."},{"key":"R10","unstructured":"U. V. \u00c7ataly\u00fcrek,\n                      Hypergraph Models for Sparse Matrix Partitioning and Reordering\n                      , Ph.D. thesis, Bilkent University, Computer Engineering and Information Science, Ankara, Turkey, 1999."},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1145\/1391989.1391995"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1145\/1024074.1024080"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1145\/992200.992206"},{"key":"R14","unstructured":"T. Davis and Y. Hu,\n                      The University of Florida Sparse Matrix Collection\n                      , ACM Trans. Math. Software, to appear."},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479895291765"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"K. Devine, E. Boman, R. Heaphy, R. Bisseling, and U. Catalyurek,\n                      Parallel hypergraph partitioning for scientific computing\n                      , in Proceedings of the 20th International Parallel and Distributed Processing Symposium (IPDPS'06), IEEE, 2006.","DOI":"10.1109\/IPDPS.2006.1639359"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479899358443"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1145\/992200.992201"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2004.12.008"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1137\/0710032"},{"key":"R21","unstructured":"L. Grigori, E. G. Boman, S. Donfack, and T. Davis,\n                      Hypergraph-Based Unsymmetric Nested Dissection Ordering for Sparse LU Factorization\n                      , Technical report 6520, INRIA, Paris, 2008."},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1007\/s10543-007-0116-1"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"L. Grigori, J. W. Demmel, and H. Xiang,\n                      Communication avoiding Gaussian elimination\n                      , in Proceedings of the ACM\/IEEE SC08 Conference, 2008.","DOI":"10.1109\/SC.2008.5214287"},{"key":"R24","unstructured":"L. Grigori, J. W. Demmel, and H. Xiang,\n                      CALU: A Communication Optimal LU Factorization Algorithm\n                      , Technical report UCB-EECS-2010-29, University of California, Berkeley, CA, 2010."},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1137\/050638102"},{"key":"R26","doi-asserted-by":"crossref","unstructured":"B. Hendrickson and R. Leland,\n                      A multilevel algorithm for partitioning graphs\n                      , in Proceedings of the Supercomputing '95, ACM, 1995.","DOI":"10.1145\/224170.224228"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827596300656"},{"key":"R28","unstructured":"HSL,\n                      A Collection of Fortran Codes for Large Scale Scientific Computation\n                      , http:\/\/www.cse.clrc.ac.uk\/nag\/hsl\/."},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1016\/S0098-1354(99)00314-2"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1109\/92.748202"},{"key":"R31","unstructured":"G. Karypis and V. Kumar,\n                      : A software package for partitioning unstructured graphs, partitioning meshes and computing fill-reducing orderings of sparse matrices\u2014verstion $4.0$\n                      , http:\/\/www-users.cs.umn.edu\/karypis\/metis."},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595287997"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1137\/0716027"},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1145\/214392.214398"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1145\/779359.779361"},{"key":"R36","unstructured":"F. Manne and R. Bisseling,\n                      A parallel approximation algorithm for the weighted maximum matching problem\n                      , in Proceedings of the Seventh International Conference on Parallel Processing and Applied Mathematics (PPAM 2007), 2007."},{"key":"R37","first-page":"255","volume":"3","author":"Markowitz H. M.","year":"1957","journal-title":"Management"},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144502409019"},{"key":"R39","doi-asserted-by":"publisher","DOI":"10.1137\/0602010"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/080720395","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T16:34:41Z","timestamp":1787330081000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/080720395"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1]]},"references-count":39,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["10.1137\/080720395"],"URL":"https:\/\/doi.org\/10.1137\/080720395","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1]]}}}