{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:04:38Z","timestamp":1750309478973,"version":"3.41.0"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2024,12,11]],"date-time":"2024-12-11T00:00:00Z","timestamp":1733875200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Science Foundation","award":["OAC-1835499"],"award-info":[{"award-number":["OAC-1835499"]}]},{"name":"Fulbright-Garcia Robles Scholarship"},{"name":"US Naval Academy Junior NARC"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2024,12,31]]},"abstract":"<jats:p>\n            SPEX Cholesky, SPEX LDL, and SPEX Backslash are software packages for exactly solving sparse linear systems,\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(A\\mathbf{x}=\\mathbf{b}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            . SPEX Cholesky, used for symmetric positive definite (SPD) systems, computes an integral Cholesky factorization to solve the system\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(A\\mathbf{x}=\\mathbf{b}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            in time proportional to arithmetic work\u2014to date the only algorithm for SPD linear systems with this property. SPEX LDL extends SPEX Cholesky for symmetric negative definite and symmetric indefinite matrices with exclusively non-zero leading principal minors. SPEX Backslash is a general-purpose exact solver that automatically determines the best ordering and factorization to exactly solve the system\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(A\\mathbf{x}=\\mathbf{b}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            . Computationally, we test the accuracy of MATLAB sparse backslash, the state-of-the-art collection of sparse matrix solvers, revealing it is near perfect for 87% of the tested instances. In addition, we show that SPEX Cholesky outperforms alternate exact solvers in runtime; specifically, SPEX Cholesky outperforms the exact solver Linbox and exact LU factorization on 70% and 92% of tested instances, respectively. Each of SPEX Cholesky, SPEX LDL, and SPEX Backslash is implemented in C and is accompanied by easy-to-use Python and MATLAB interfaces. They are distributed via GitHub, as a component of the SPEX software package, and as component of SuiteSparse.\n          <\/jats:p>","DOI":"10.1145\/3700592","type":"journal-article","created":{"date-parts":[[2024,10,19]],"date-time":"2024-10-19T08:41:56Z","timestamp":1729327316000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Algorithm 1050: SPEX Cholesky, LDL, and Backslash for Exactly Solving Sparse Linear Systems"],"prefix":"10.1145","volume":"50","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0970-3840","authenticated-orcid":false,"given":"Lorena","family":"Mejia-Domenzain","sequence":"first","affiliation":[{"name":"Department of Industrial and Systems Engineering, Texas A&amp;M University, College Station, TX, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3113-3469","authenticated-orcid":false,"given":"Jinhao","family":"Chen","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, Texas A&amp;M University, College Station, TX, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2321-615X","authenticated-orcid":false,"given":"Christopher","family":"Lourenco","sequence":"additional","affiliation":[{"name":"Department of Mathematics, United States Naval Academy, Annapolis, MD, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6258-5428","authenticated-orcid":false,"given":"Erick","family":"Moreno-Centeno","sequence":"additional","affiliation":[{"name":"Department of Industrial and Systems Engineering, Texas A&amp;M University, College Station, TX, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7614-6899","authenticated-orcid":false,"given":"Timothy A.","family":"Davis","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, Texas A&amp;M University, College Station, TX, USA"}]}],"member":"320","published-online":{"date-parts":[[2024,12,11]]},"reference":[{"key":"e_1_3_2_2_1","doi-asserted-by":"publisher","DOI":"10.1088\/1742-6596\/180\/1\/012037"},{"key":"e_1_3_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1024074.1024081"},{"key":"e_1_3_2_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/0610013"},{"key":"e_1_3_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2382585.2382589"},{"key":"e_1_3_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391989.1391995"},{"key":"e_1_3_2_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-013-0055-6"},{"key":"e_1_3_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1024074.1024080"},{"key":"e_1_3_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2049662.2049663"},{"key":"e_1_3_2_10_1","first-page":"1","article-title":"LAPACK: A portable linear algebra library for supercomputers","author":"Demmel James","year":"1989","unstructured":"James Demmel. 1989a. LAPACK: A portable linear algebra library for supercomputers. In Proceedings of the IEEE Control Systems Society Workshop on Computer-Aided Control System Design. IEEE, 1\u20137.","journal-title":"Proceedings of the IEEE Control Systems Society Workshop on Computer-Aided Control System Design"},{"key":"e_1_3_2_11_1","volume-title":"On Floating Point Errors in Cholesky","author":"Demmel James","year":"1989","unstructured":"James Demmel. 1989b. On Floating Point Errors in Cholesky. University of Tennessee. Computer Science Department."},{"key":"e_1_3_2_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.coastaleng.2021.104011"},{"key":"e_1_3_2_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01459082"},{"key":"e_1_3_2_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s101070100263"},{"key":"e_1_3_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/992200.992202"},{"key":"e_1_3_2_16_1","doi-asserted-by":"publisher","DOI":"10.1142\/9789812777171_0005"},{"key":"e_1_3_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/258726.258776"},{"key":"e_1_3_2_18_1","first-page":"1","article-title":"A computational status update for exact rational mixed integer programming","volume":"197","author":"Eifler Leon","year":"2022","unstructured":"Leon Eifler and Ambros Gleixner. 2022. A computational status update for exact rational mixed integer programming. Mathematical Programming 197 (2022), 1\u201320.","journal-title":"Mathematical Programming"},{"key":"e_1_3_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236463.1236468"},{"key":"e_1_3_2_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(99)00012-7"},{"key":"e_1_3_2_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/0909058"},{"key":"e_1_3_2_22_1","author":"Gleixner Ambros M.","year":"2015","unstructured":"Ambros M. Gleixner. 2015. Exact and Fast Algorithms for Mixed-Integer Nonlinear Programming. Ph.D. Dissertation. Technischen Universitat Berlin, Berlin, Germany.","journal-title":"Exact and Fast Algorithms for Mixed-Integer Nonlinear Programming"},{"key":"e_1_3_2_23_1","volume-title":"Matrix Computations","author":"Golub Gene H.","year":"2012","unstructured":"Gene H. Golub and Charles F. Van Loan. 2012. Matrix Computations. Vol. 3, JHU Press."},{"key":"e_1_3_2_24_1","volume-title":"GNU MP 6.0 Multiple Precision Arithmetic Library","author":"Torbjrn Granlund and Gmp Development Team","year":"2015","unstructured":"Torbjrn Granlund and Gmp Development Team. 2015. GNU MP 6.0 Multiple Precision Arithmetic Library. Samurai Media Limited."},{"key":"e_1_3_2_25_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2005.162.1065"},{"key":"e_1_3_2_26_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41586-020-2649-2"},{"key":"e_1_3_2_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15582-6_18"},{"key":"e_1_3_2_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718027"},{"key":"e_1_3_2_29_1","volume-title":"The Matrix Computation Toolbox for MATLAB (Version 1.0)","author":"Higham Nicholas J.","year":"2002","unstructured":"Nicholas J. Higham. 2002b. The Matrix Computation Toolbox for MATLAB (Version 1.0). Manchester Centre for Computational Mathematics."},{"issue":"1","key":"e_1_3_2_30_1","first-page":"40","article-title":"The CMake build manager","volume":"28","author":"Hoffman William","year":"2003","unstructured":"William Hoffman and Ken Martin. 2003. The CMake build manager. Dr. Dobb\u2019s Journal: Software Tools for the Professional Programmer 28, 1 (2003), 40\u201343.","journal-title":"Dr. Dobb\u2019s Journal: Software Tools for the Professional Programmer"},{"key":"e_1_3_2_31_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139020411"},{"key":"e_1_3_2_32_1","volume-title":"Blocked Lanczos-Style Algorithms over Small Finite Fields","author":"Hovinen Bradford","year":"2004","unstructured":"Bradford Hovinen. 2004. Blocked Lanczos-Style Algorithms over Small Finite Fields. Ph.D. Dissertation. Citeseer."},{"key":"e_1_3_2_33_1","first-page":"94720","article-title":"IEEE standard 754 for binary floating-point arithmetic","volume":"754","author":"Kahan William","year":"1996","unstructured":"William Kahan. 1996. IEEE standard 754 for binary floating-point arithmetic. Lecture Notes on the Status of IEEE 754, 94720\u20131776 (1996), 11.","journal-title":"Lecture Notes on the Status of IEEE"},{"key":"e_1_3_2_34_1","first-page":"54","article-title":"Identification, assessment, and correction of ill-conditioning and numerical instability in linear and integer programs","author":"Klotz Ed","year":"2014","unstructured":"Ed Klotz. 2014. Identification, assessment, and correction of ill-conditioning and numerical instability in linear and integer programs. In Bridging Data and Decisions. INFORMS, 54\u2013108.","journal-title":"Bridging Data and Decisions"},{"key":"e_1_3_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/103147.103159"},{"key":"e_1_3_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519024"},{"key":"e_1_3_2_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/18M1202499"},{"key":"e_1_3_2_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/20M1371592"},{"key":"e_1_3_2_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/130912438"},{"key":"e_1_3_2_40_1","unstructured":"Victor Shoup. 2001. NTL: A library for doing number theory. Retrieved from https:\/\/libntl.org\/"},{"key":"e_1_3_2_41_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1984-0725988-X"},{"key":"e_1_3_2_42_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41592-019-0686-2"},{"key":"e_1_3_2_43_1","doi-asserted-by":"publisher","DOI":"10.4324\/9780203489307-28"},{"key":"e_1_3_2_44_1","first-page":"629","article-title":"A priori error analysis of algebraic processes","volume":"19","author":"Wilkinson James H.","year":"1968","unstructured":"James H. Wilkinson. 1968. A priori error analysis of algebraic processes. In Proceedings of the International Congress of Mathematicians, Vol. 19, 629\u2013639.","journal-title":"Proceedings of the International Congress of Mathematicians"},{"key":"e_1_3_2_45_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\/10.1145\/3700592","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3700592","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:17:28Z","timestamp":1750295848000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3700592"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,11]]},"references-count":44,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,12,31]]}},"alternative-id":["10.1145\/3700592"],"URL":"https:\/\/doi.org\/10.1145\/3700592","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"type":"print","value":"0098-3500"},{"type":"electronic","value":"1557-7295"}],"subject":[],"published":{"date-parts":[[2024,12,11]]},"assertion":[{"value":"2023-07-26","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-08-22","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-12-11","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}