{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T16:23:25Z","timestamp":1787329405616,"version":"build-2736575974"},"reference-count":54,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2011,1]]},"abstract":"<jats:p>A typical first step of a direct solver for the linear system $Mx=b$ is reordering of the symmetric matrix M to improve execution time and space requirements of the solution process. In this work, we propose a novel nested-dissection-based ordering approach that utilizes hypergraph partitioning. Our approach is based on the formulation of graph partitioning by vertex separator (GPVS) problem as a hypergraph partitioning problem. This new formulation is immune to deficiency of GPVS in a multilevel framework and hence enables better orderings. In matrix terms, our method relies on the existence of a structural factorization of the input M matrix in the form of $M=AA^T$ (or $M=AD^2A^T$). We show that the partitioning of the row-net hypergraph representation of the rectangular matrix A induces a GPVS of the standard graph representation of matrix M. In the absence of such factorization, we also propose simple, yet effective structural factorization techniques that are based on finding an edge clique cover of the standard graph representation of matrix M, and hence applicable to any arbitrary symmetric matrix M. Our experimental evaluation has shown that the proposed method achieves better ordering in comparison to state-of-the-art graph-based ordering tools even for symmetric matrices where structural $M=AA^T$ factorization is not provided as an input. For matrices coming from linear programming problems, our method enables even faster and better orderings.<\/jats:p>","DOI":"10.1137\/090757575","type":"journal-article","created":{"date-parts":[[2011,8,19]],"date-time":"2011-08-19T03:15:44Z","timestamp":1313723744000},"page":"1996-2023","source":"Crossref","is-referenced-by-count":12,"title":["Hypergraph Partitioning-Based Fill-Reducing Ordering for Symmetric Matrices"],"prefix":"10.1137","volume":"33","author":[{"given":"\u00dcmit V.","family":"\u00c7ataly\u00fcrek","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Cevdet","family":"Aykanat","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Enver","family":"Kayaaslan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2011,8,18]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-9260(95)00008-4"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479894278952"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1145\/1024074.1024081"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"E. D. Andersen, J. Gondzio, C. Meszaros, and X. Xu,\n                      Implementation of interior point methods for large scale linear programming\n                      , in Interior Point Methods in Mathematical Programming, Kluwer Academic Publishers, Norwell, MA, 1996, pp. 189\u2013252.","DOI":"10.1007\/978-1-4613-3449-1_6"},{"key":"R5","unstructured":"C. Ashcraft and R. Grimes,\n                      Spooles: An object-oriented sparse matrix library\n                      , in Proceedings of the 9th SIAM Conference on Parallel Processing for Scientific Computing, 1999."},{"key":"R6","unstructured":"C. Ashcraft and J. W. H. Liu,\n                      SMOOTH: A software package for ordering sparse matrices\n                      , 1996."},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479896308433"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827502401953"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"A. Brandstadt, V. B. Le, and J. P. Spinrad,\n                      Graph classes: A survey\n                      , SIAM Monogr. Discrete Math. Appl., SIAM, Philadelphia, 1999.","DOI":"10.1137\/1.9780898719796"},{"key":"R10","unstructured":"T. N. Bui and C. Jones,\n                      A heuristic for reducing fill-in in sparse matrix factorization\n                      , in Proceedings of the 6th SIAM Conference on Parallel Processing for Scientific Computing, 1993, pp. 445\u2013452."},{"key":"R11","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, Bilkent, Turkey, 1999; available online from http:\/\/www.cs.bilkent.edu.tr\/tech-reports\/1999\/ABSTRACTS.1999.html."},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1109\/71.780863"},{"key":"R13","unstructured":"U. V. \u00c7ataly\u00fcrek and C. Aykanat,\n                      PaToH: A Multilevel Hypergraph Partitioning Tool, Version $3.0$\n                      , Department of Computer Engineering, Bilkent University, Ankara, 06533 Turkey. PaToH is available from http:\/\/bmi.osu.edu\/ umit\/software.htm, 1999."},{"key":"R14","unstructured":"U. V. \u00c7ataly\u00fcrek and C. Aykanat,\n                      A fine-grain hypergraph model for 2D decomposition of sparse matrices\n                      , in Proceedings of 15th International Parallel and Distributed Processing Symposium (IPDPS), San Francisco, CA, 2001."},{"key":"R15","unstructured":"U. V. \u00c7ataly\u00fcrek and C. Aykanat,\n                      Hypergraph-partitioning-based sparse matrix ordering\n                      , in Proceedings of the Second International Workshop on Combinatorial Scientific Computing (CSC05), CERFACS, Toulouse, France, 2005."},{"key":"R16","unstructured":"U. V. \u00c7ataly\u00fcrek, C. Aykanat, and E. Kayaaslan,\n                      Hypergraph partitioning-based fill-reducing ordering\n                      , Technical reports OSUBMI-TR-2009-n02 and BU-CE-0904, Department of Biomedical Informatics and Bilkent University, Computer Engineering Department, The Ohio State University, Columbus, OH, 2009."},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1137\/080737770"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2007.12.001"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"J. Cong, W. Labio, and N. Shivakumar,\n                      Multi-way VLSI circuit partitioning based on dual net representation\n                      , in Proceedings of the IEEE International Conference on Computer-Aided Design, 1994, pp. 56\u201362.","DOI":"10.1109\/ICCAD.1994.629744"},{"key":"R20","unstructured":"T. H. Cormen, C. E. Leiserson, and R. L. Rivest,\n                      Introduction to Algorithms\n                      , MIT Press, McGraw-Hill, New York, 1990."},{"key":"R21","unstructured":"G. B. Dantzig and M. N. Thapa,\n                      Linear Programming: Theory and Extensions\n                      , Springer, New York, 2003."},{"key":"R22","unstructured":"T. Davis,\n                      University of Florida sparse matrix collection: http:\/\/www.cise.ufl.edu\/research\/sparse\/\n                      , NA Digest, 92\/96\/97 (1994\/1996\/1997)."},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1145\/1024074.1024079"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479895291765"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1007\/s101070100263"},{"key":"R26","unstructured":"I. S. Duff and B. U\u00e7ar,\n                      Combinatorial problems in solving linear systems\n                      , Technical report TR\/PA\/09\/60, CERFACS, Toulouse, France, 2009; available online from http:\/\/www.cerfacs.fr\/algor\/reports\/."},{"key":"R27","doi-asserted-by":"crossref","unstructured":"C. M. Fiduccia and R. M. Mattheyses,\n                      A linear-time heuristic for improving network partitions\n                      , in Proceedings of the 19th ACM\/IEEE Design Automation Conference, 1982, pp. 175\u2013181.","DOI":"10.1109\/DAC.1982.1585498"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1137\/0904013"},{"key":"R29","unstructured":"A. George and J. W. H. Liu,\n                      Computer Solution of Large Sparse Positive Definite Systems\n                      , Prentice-Hall, Englewood Cliffs, NJ, 1981."},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1137\/0710032"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-8369-7_6"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1007\/BF01396660"},{"key":"R33","doi-asserted-by":"crossref","unstructured":"J. Gramm, J. Guo, F. H\u00fcffner, and R. Niedermeier,\n                      Data reduction, exact, and heuristic algorithms for clique cover\n                      , in Proceedings of the Eighth Workshop on Algorithm Engineering, 2006.","DOI":"10.1137\/1.9781611972863.9"},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1137\/080720395"},{"key":"R35","unstructured":"A. Gupta,\n                      Fast and effective algorithms for graph partitioning and sparse matrix ordering\n                      , Technical report RC 20453, IBM T. J. Watson Research Center, Yorktown Heights, New York, 1996."},{"key":"R36","unstructured":"A. Gupta,\n                      Watson graph partitioning package\n                      , Technical report RC 20453, IBM T. J. Watson Research Center, Yorktown Heights, New York, 1996."},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(00)00048-X"},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827598341475"},{"key":"R39","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, New York, 1995.","DOI":"10.1145\/224170.224228"},{"key":"R40","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827596300656"},{"key":"R41","doi-asserted-by":"crossref","unstructured":"A. B. Kahng,\n                      Fast hypergraph partition\n                      , in Proceedings of the 26th ACM\/IEEE Design Automation Conference, 1989, pp. 762\u2013766.","DOI":"10.1145\/74382.74524"},{"key":"R42","doi-asserted-by":"crossref","unstructured":"R. M. Karp,\n                      Reducibility among combinatorial problems\n                      , in Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, eds., Plenum Press, New York, 1972, pp. 85\u2013103.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"R43","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595287997"},{"key":"R44","unstructured":"G. Karypis and V. Kumar,\n                      MeTiS A Software Package for Partitioning Unstructured Graphs, Partitioning Meshes, and Computing Fill-Reducing Orderings of Sparse Matrices Version $4.0$\n                      , Department of Computer Science and Engineering, Army HPC Research Center, University of Minnesota, Minneapolis, MN, 1998."},{"key":"R45","unstructured":"E. Kayaaslan, A. Pinar, U. V. \u00c7ataly\u00fcrek, and C. Aykanat,\n                      Hypergraph partitioning through vertex separators on graphs\n                      , Technical reports OSUBMI-TR-2010-n01 and BU-CE-1016, Department of Biomedical Informatics and Bilkent University, Computer Engineering Department, The Ohio State University, Columbus, OH, 2010; also available from http:\/\/bmi.osu.edu\/hpc\/publications.html."},{"key":"R46","unstructured":"E. Kellerman,\n                      Determination of keyword conflict\n                      , IBM Technical Disclosure Bulletin, 1973."},{"key":"R47","doi-asserted-by":"publisher","DOI":"10.1145\/359340.359346"},{"key":"R48","doi-asserted-by":"publisher","DOI":"10.1145\/214392.214398"},{"key":"R49","doi-asserted-by":"publisher","DOI":"10.1137\/0910069"},{"key":"R50","doi-asserted-by":"crossref","unstructured":"D. J. Rose,\n                      A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations\n                      , Graph Theory and Computing, Academic Press, New York, 1972, pp. 183\u2013217.","DOI":"10.1016\/B978-1-4832-3187-7.50018-0"},{"key":"R51","unstructured":"E. Rothberg,\n                      Ordering sparse matrices using approximate minimum local fill\n                      , in Second SIAM Conference on Sparse Matrices, 1996."},{"key":"R52","doi-asserted-by":"crossref","unstructured":"W. F. Tinney and J. W. Walker,\n                      Direct solution of sparse network equations by optimally ordered triangular factorization\n                      , in Proc. IEEE, 55, 1967, pp. 1801\u20131809.","DOI":"10.1109\/PROC.1967.6011"},{"key":"R53","doi-asserted-by":"publisher","DOI":"10.1137\/060662459"},{"key":"R54","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\/090757575","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T15:16:39Z","timestamp":1787325399000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/090757575"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1]]},"references-count":54,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,1]]}},"alternative-id":["10.1137\/090757575"],"URL":"https:\/\/doi.org\/10.1137\/090757575","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,1]]}}}