{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,11,22]],"date-time":"2024-11-22T05:25:13Z","timestamp":1732253113843,"version":"3.28.0"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2017,8,16]],"date-time":"2017-08-16T00:00:00Z","timestamp":1502841600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000266","name":"EPSRC","doi-asserted-by":"crossref","award":["EP\/M025179\/1"],"id":[{"id":"10.13039\/501100000266","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":[[2018,6,30]]},"abstract":"\n Sparse symmetric indefinite problems arise in a large number of important application areas; they are often solved through the use of an\n \n LDL\n T<\/jats:sup>\n <\/jats:italic>\n factorization via a sparse direct solver. While for many problems prescaling the system matrix\n A<\/jats:italic>\n is sufficient to maintain stability of the factorization, for a small but important fraction of problems numerical pivoting is required. Pivoting often incurs a significant overhead, and consequently, a number of techniques have been proposed to try and limit the need for pivoting. In particular, numerically aware ordering algorithms may be used, that is, orderings that depend not only on the sparsity pattern of\n A<\/jats:italic>\n but also on the values of its (scaled) entries.\n <\/jats:p>\n \n Current approaches identify large entries of\n A<\/jats:italic>\n and symmetrically permute them onto the subdiagonal, where they can be used as part of a 2 \u00d7 2 pivot. This is numerically effective, but the fill in the factor\n L<\/jats:italic>\n and hence the runtime of the factorization and subsequent triangular solves may be significantly increased over a standard ordering if no pivoting is required.\n <\/jats:p>\n We present a new algorithm that combines a matching-based approach with a numerically aware nested dissection ordering. Numerical comparisons with current approaches for some tough symmetric indefinite problems are given.<\/jats:p>","DOI":"10.1145\/3104991","type":"journal-article","created":{"date-parts":[[2017,8,24]],"date-time":"2017-08-24T11:49:04Z","timestamp":1503575344000},"page":"1-22","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Numerically Aware Orderings for Sparse Symmetric Indefinite Linear Systems"],"prefix":"10.1145","volume":"44","author":[{"given":"Jonathan","family":"Hogg","sequence":"first","affiliation":[{"name":"Rutherford Appleton Laboratory, Oxfordshire, UK"}]},{"ORCID":"http:\/\/orcid.org\/0000-0003-2130-1091","authenticated-orcid":false,"given":"Jennifer","family":"Scott","sequence":"additional","affiliation":[{"name":"Rutherford Appleton Laboratory, Oxfordshire, UK"}]},{"given":"Sue","family":"Thorne","sequence":"additional","affiliation":[{"name":"Rutherford Appleton Laboratory"}]}],"member":"320","published-online":{"date-parts":[[2017,8,16]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1024074.1024081"},{"volume-title":"Technical Report RAL-TR-2016-4. STFC Rutherford Appleton Laboratory","year":"2016","author":"Ashcraft C.","key":"e_1_2_1_2_1","unstructured":"C. Ashcraft, I. S. Duff, J. D. Hogg, J. A. Scott, and H. S. Thorne. 2016. Nested Dissection Revisited. Technical Report RAL-TR-2016-4. STFC Rutherford Appleton Laboratory. http:\/\/purl.org\/net\/epubs\/work\/24733312."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479896296921"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1977-0428694-0"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/992200.992202"},{"volume-title":"Abstract Book of Householder Symposium XV. 73--75","author":"Duff I. S.","key":"e_1_2_1_6_1","unstructured":"I. S. Duff and J. R. Gilbert. 2002. Maximum-weighted matching and block pivoting for symmetric indefinite systems. In Abstract Book of Householder Symposium XV. 73--75."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1093\/imanum\/11.2.181"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479897317661"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/04061043X"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/0710032"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/578296"},{"key":"e_1_2_1_12_1","unstructured":"A. Gupta. 2015. Private communication. (2015)."},{"key":"e_1_2_1_13_1","first-page":"06","article-title":"WSMP: Watson Sparse Matrix Package","volume":"13","author":"Gupta A.","year":"2013","unstructured":"A. Gupta and H. Avron. 2013. WSMP: Watson Sparse Matrix Package. Part I - Direct Solution of Symmetric Systems. Version 13.06. Technical Report RC 21886. IBM T. J. Watson Research Center, Yorktown Heights, NY. http:\/\/www.research.ibm.com\/projects\/wsmp.","journal-title":"Part I - Direct Solution of Symmetric Systems. Version"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/040615614"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/0916028"},{"volume-title":"Technical Report SAND942692. Sandia National Laboratories","year":"1995","author":"Hendrickson B.","key":"e_1_2_1_16_1","unstructured":"B. Hendrickson and R. Leland. 1995. The Chaco Users Guide, Version 2.0. Technical Report SAND942692. Sandia National Laboratories, Albuquerque, NM."},{"volume-title":"Technical Report RAL-TR-2011-024. STFC Rutherford Appleton Laboratory.","year":"2011","author":"Hogg J. D.","key":"e_1_2_1_19_1","unstructured":"J. D. Hogg and J. A. Scott. 2011. HSL_MA97: A Bit-Compatible Multifrontal Code for Sparse Symmetric Systems. Technical Report RAL-TR-2011-024. STFC Rutherford Appleton Laboratory."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","unstructured":"J. D. Hogg and J. A. Scott. 2013. Pivoting strategies for tough sparse indefinite systems. ACM Trans. Math. Software 40 (2013). Article 4 19 pages. 10.1145\/2513109.2513113","DOI":"10.1145\/2513109.2513113"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/130920629"},{"volume-title":"METIS: Unstructured Graph Partitioning and Sparse Matrix Ordering System. Technical Report TR 95-035","year":"1995","author":"Karypis G.","key":"e_1_2_1_22_1","unstructured":"G. Karypis and V. Kumar. 1995. METIS: Unstructured Graph Partitioning and Sparse Matrix Ordering System. Technical Report TR 95-035. University of Minnesota."},{"volume-title":"METIS: A software package for partitioning unstructured graphs, partitioning meshes and computing fill-reducing orderings of sparse matrices - Version 4.0.","year":"1998","author":"Karypis G.","key":"e_1_2_1_23_1","unstructured":"G. Karypis and V. Kumar. 1998. METIS: A software package for partitioning unstructured graphs, partitioning meshes and computing fill-reducing orderings of sparse matrices - Version 4.0. Retrieved from http:\/\/www-users.cs.umn.edu\/∼karypis\/metis\/."},{"key":"e_1_2_1_24_1","unstructured":"F. Pellegrini. 2012. SCOTCH 6.0. Retrieved from http:\/\/www.labri.fr\/perso\/pelegrin\/scotch\/."},{"key":"e_1_2_1_25_1","first-page":"158","article-title":"On fast factorization pivoting methods for symmetric indefinite systems","volume":"23","author":"Schenk O.","year":"2006","unstructured":"O. Schenk and K. G\u00e4rtner. 2006. On fast factorization pivoting methods for symmetric indefinite systems. Electron. Trans. Numer. Analysis 23 (2006), 158--179.","journal-title":"Electron. Trans. Numer. Analysis"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-006-9003-y"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/0602010"}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3104991","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,21]],"date-time":"2024-11-21T17:20:10Z","timestamp":1732209610000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3104991"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,8,16]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,6,30]]}},"alternative-id":["10.1145\/3104991"],"URL":"https:\/\/doi.org\/10.1145\/3104991","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"type":"print","value":"0098-3500"},{"type":"electronic","value":"1557-7295"}],"subject":[],"published":{"date-parts":[[2017,8,16]]},"assertion":[{"value":"2016-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-05-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-08-16","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}