{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:33:40Z","timestamp":1787337220359,"version":"build-2736575974"},"reference-count":41,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2006,1]]},"abstract":"<jats:p>Maximum weight matchings have become an important tool for solving highly indefinite unsymmetric linear systems, especially in direct solvers. In this study we investigate the benefit of reorderings and scalings based on symmetrized maximum weight matchings as a preprocessing step for incomplete $\\mathrm{LDL^T}$ factorizations. The reorderings are constructed such that the matched entries form $1 \\times 1$ or $2 \\times 2$ diagonal blocks in order to increase the diagonal dominance of the system. During the incomplete factorization only tridiagonal pivoting is used. We report results for this approach and comparisons with other solution methods for a diverse set of symmetric indefinite matrices, ranging from nonlinear elasticity to interior point optimization.<\/jats:p>","DOI":"10.1137\/040615614","type":"journal-article","created":{"date-parts":[[2006,4,3]],"date-time":"2006-04-03T21:00:16Z","timestamp":1144098016000},"page":"403-420","source":"Crossref","is-referenced-by-count":37,"title":["Weighted Matchings for Preconditioning Symmetric Indefinite Linear Systems"],"prefix":"10.1137","volume":"28","author":[{"given":"Michael","family":"Hagemann","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Olaf","family":"Schenk","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,25]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479896296921"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1002\/nla.310"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827597319520"},{"key":"R4","unstructured":"R. Barrett, M. W. Berry, T. F. Chan, J. Demmel, J. Donato, J. Dongarra, V. Eijkhout, R. Pozo, C. Romine, and H. van der Vorst,\n                      Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods\n                      , SIAM, Philadelphia, 1993."},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492904000212"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827599361308"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1137\/0711043"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1977-0428694-0"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-0427(97)00171-4"},{"key":"R10","unstructured":"I. S. Duff and J. R. Gilbert,\n                      Maximum\u2010weighted matching and block pivoting for symmetric indefinite systems\n                      , in Abstract Book of Householder Symposium XV, 2002, pp. 73\u201375."},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479897317661"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479899358443"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/04061043X"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1145\/356044.356047"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1137\/0902019"},{"key":"R16","unstructured":"Richard Ewing, Raytcho Lazarov, Peng Lu, Panayot Vassilevski, Preconditioning indefinite systems arising from mixed finite element discretization of second\u2010order elliptic problems, Lecture Notes in Math., Vol. 1457, Springer, Berlin, 1990, 28\u20134392a:65137"},{"key":"R17","unstructured":"R. W. Freund,\n                      Preconditioning of symmetric, but highly indefinite linear systems\n                      , in Proceedings of the 15th IMACS World Congress on Scientific Computation, Modeling and Applied Mathematics, Vol. 2, Numerical Mathematics, Wissenschaft und Technik Verlag, 1997, pp. 551\u2013556."},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1007\/BF02614383"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1137\/0613022"},{"key":"R20","unstructured":"N. I. M. Gould, Y. Hu, and J. A. Scott,\n                      A Numerical Evaluation of Sparse Direct Solvers for the Solution of Large Sparse, Symmetric Linear Systems of Equations\n                      , Technical Report RAL\u2010TR\u20102005\u2010005, Rutherford Appleton Laboratory, Oxfordshire, UK, 2005."},{"key":"R21","unstructured":"A. Gupta and L. Ying,\n                      On Algorithms for Finding Maximum Matchings in Bipartite Graphs\n                      , Technical Report RC, 21576 (97320), IBM T. J. Watson Research Center, Yorktown Heights, NY, 1999."},{"key":"R22","unstructured":"M. Hagemann and O. Schenk, Sagg\u2014Sparse \u00e0 Go\u2010Go, A Solver Package for Sparse Matrices, University of Basel, 2004;"},{"key":"R22","unstructured":"see online resources at http:\/\/ www.computational.unibas.ch\/ cs\/ scicomp\/ software\/ sagg\/."},{"key":"R23","unstructured":"J. C. Haws and C. D. Meyer,\n                      Preconditioning KKT Systems\n                      , Technical Report M&CT\u2010Tech\u201001\u2010021, The Boeing Company, Chicago, IL, 2003."},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1016\/S0024-3795(98)10074-5"},{"key":"R25","unstructured":"HSL Subroutine Library, A collection of Fortran codes for large\u2010scale scientific computation\n                      , Rutherford Appleton Laboratory, Oxfordshire, UK, 2004;"},{"key":"R25","unstructured":"http:\/\/www.cse.clrc.ac.uk\/ nag\/ hsl\/ hsl.shtml."},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1145\/200979.200981"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595287997"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479899351805"},{"key":"R29","first-page":"75","volume":"20","author":"Li Na","year":"2005","journal-title":"Electron. Trans. Numer. Anal."},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1099-1506(199805\/06)5:3<219::AID-NLA134>3.0.CO;2-7"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(94)00192-8"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1002\/nla.1680010405"},{"key":"R33","unstructured":"O. Schenk and K. G\u00e4rtner,\n                      On Fast Factorization Pivoting Methods for Symmetric Indefinite Systems\n                      , Technical report CS\u20102004\u2010004, Computer Science Department, University of Basel, Switzerland, 2004;"},{"key":"R33","unstructured":"Electronic Transactions on Numerical Analysis, submitted."},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022326604210"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2004.823345"},{"key":"R36","unstructured":"SOCS Sparse Optimal Control Software\n                      , Boeing Phantom Works, The Boeing Company, Chicago, IL, 2002."},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-004-0559-y"},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-01-01324-2"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/040615614","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:50:00Z","timestamp":1787334600000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/040615614"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,1]]},"references-count":41,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2006,1]]}},"alternative-id":["10.1137\/040615614"],"URL":"https:\/\/doi.org\/10.1137\/040615614","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,1]]}}}