{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,16]],"date-time":"2026-01-16T12:16:28Z","timestamp":1768565788042,"version":"3.49.0"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2022,5,26]],"date-time":"2022-05-26T00:00:00Z","timestamp":1653523200000},"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":"Texas A&M Graduate Merit Fellowship"},{"name":"Texas A&M Graduate Teaching Fellowship"},{"name":"USNA Junior NARC"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2022,6,30]]},"abstract":"<jats:p>\n            SPEX Left LU is a software package for exactly solving unsymmetric sparse linear systems. As a component of the sparse exact (SPEX) software package, SPEX Left LU can be applied to any input matrix,\n            <jats:italic>A<\/jats:italic>\n            , whose entries are integral, rational, or decimal, and provides a solution to the system\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( Ax = b \\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            , which is either exact or accurate to user-specified precision. SPEX Left LU preorders the matrix\n            <jats:italic>A<\/jats:italic>\n            with a user-specified fill-reducing ordering and computes a left-looking LU factorization with the special property that each operation used to compute the\n            <jats:italic>L<\/jats:italic>\n            and\n            <jats:italic>U<\/jats:italic>\n            matrices is integral. Notable additional applications of this package include benchmarking the stability and accuracy of state-of-the-art linear solvers and determining whether singular-to-double-precision matrices are indeed singular. Computationally, this article evaluates the impact of several novel pivoting schemes in exact arithmetic, benchmarks the exact iterative solvers within Linbox, and benchmarks the accuracy of MATLAB sparse backslash. Most importantly, it is shown that SPEX Left LU outperforms the exact iterative solvers in run time on\n            <jats:italic>easy<\/jats:italic>\n            instances and in stability as the iterative solver fails on a sizeable subset of the tested (both easy and hard) instances. The SPEX Left LU package is written in ANSI C, comes with a MATLAB interface, and is distributed via GitHub, as a component of the SPEX software package, and as a component of SuiteSparse.\n          <\/jats:p>","DOI":"10.1145\/3519024","type":"journal-article","created":{"date-parts":[[2022,3,4]],"date-time":"2022-03-04T22:28:24Z","timestamp":1646432904000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Algorithm\u00a01021: SPEX Left LU, Exactly Solving Sparse Linear Systems via a Sparse Left-looking Integer-preserving LU Factorization"],"prefix":"10.1145","volume":"48","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2321-615X","authenticated-orcid":false,"given":"Christopher","family":"Lourenco","sequence":"first","affiliation":[{"name":"United States Naval Academy, Annapolis MD"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jinhao","family":"Chen","sequence":"additional","affiliation":[{"name":"Texas A&amp;M University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Erick","family":"Moreno-Centeno","sequence":"additional","affiliation":[{"name":"Texas A&amp;M University and Instituto Tecnol\u00f3gico Aut\u00f3nomo de M\u00e9xico Department of Industrial and Operations Engineering"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7614-6899","authenticated-orcid":false,"given":"Timothy A.","family":"Davis","sequence":"additional","affiliation":[{"name":"Texas A&amp;M University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,5,26]]},"reference":[{"key":"e_1_3_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1024074.1024081"},{"key":"e_1_3_2_3_1","unstructured":"D. L. Applegate W. Cook S. Dash and D. G. Espinoza. 2007b. QSopt ex. Retrieved from http:\/\/www.dii.uchile.cl\/~daespino\/QSoptExact_doc\/main.html."},{"key":"e_1_3_2_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2006.12.010"},{"key":"e_1_3_2_5_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1968-0226829-0"},{"key":"e_1_3_2_6_1","doi-asserted-by":"publisher","DOI":"10.1006\/jsco.1996.0125"},{"key":"e_1_3_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2382585.2382589"},{"key":"e_1_3_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1916461.1916463"},{"key":"e_1_3_2_9_1","article-title":"SuiteSparse","author":"Davis Tim","year":"2014","unstructured":"Tim Davis, W. W. Hager, and I. S. Duff. 2014. SuiteSparse. Retrieved from http:\/\/faculty. cse. tamu. edu\/davis\/suitesparse.html.","journal-title":"Retrieved from http:\/\/faculty. cse. tamu. edu\/davis\/suitesparse.html"},{"key":"e_1_3_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/992200.992206"},{"key":"e_1_3_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1024074.1024080"},{"key":"e_1_3_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1824801.1824814"},{"key":"e_1_3_2_13_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492916000076"},{"key":"e_1_3_2_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01459082"},{"key":"e_1_3_2_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s101070100263"},{"key":"e_1_3_2_16_1","doi-asserted-by":"publisher","DOI":"10.1142\/9789812777171_0005"},{"key":"e_1_3_2_17_1","unstructured":"Jean-Guillaume Dumas Thierry Gautier Pascal Giorgi Jean-Louis Roch and Gilles Villard. 2008a. Givaro-3.2. 13rc1: C++ library for arithmetic and algebraic computations. https:\/\/github.com\/linbox-team\/givaro."},{"key":"e_1_3_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391989.1391992"},{"key":"e_1_3_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/258726.258776"},{"key":"e_1_3_2_20_1","doi-asserted-by":"publisher","DOI":"10.6028\/jres.071B.033"},{"key":"e_1_3_2_21_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2015.0653"},{"key":"e_1_3_2_22_1","unstructured":"Leslie Foster and N. B. Botev. 2009. San Jose State University singular matrix database (stored in matrix-market format in binary floating-point). Retrieved from http:\/\/www.math.sjsu.edu\/singular\/matrices."},{"key":"e_1_3_2_23_1","unstructured":"Leslie Foster and N. B. Botev. 2022. San Jose State University singular matrix database (stored in text to 16 decimal digits). Retrieved from https:\/\/github.com\/clouren\/SJ_16_Digits."},{"key":"e_1_3_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2513109.2513116"},{"key":"e_1_3_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236463.1236468"},{"key":"e_1_3_2_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(99)00012-7"},{"key":"e_1_3_2_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/0909058"},{"key":"e_1_3_2_28_1","unstructured":"Ambros Gleixner Leon Eifler Tristan Gally Gerald Gamrath Patrick Gemander Robert Lion Gottwald Gregor Hendel Christopher Hojny Thorsten Koch Matthias Miltenberger et\u00a0al. 2017. The SCIP optimization suite 5.0. https:\/\/scipopt.org\/#scipoptsuite."},{"key":"e_1_3_2_29_1","unstructured":"Ambros M. Gleixner. 2015. Exact and fast algorithms for mixed-integer nonlinear programming. PhD Thesis. Zuse Institute Berlin. https:\/\/do.tuberlin.de\/handle\/11303\/5244."},{"key":"e_1_3_2_30_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_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/2911024"},{"key":"e_1_3_2_32_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2005.162.1065"},{"key":"e_1_3_2_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/1888390.1888413"},{"key":"e_1_3_2_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/579525"},{"key":"e_1_3_2_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/2422911"},{"key":"e_1_3_2_36_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."},{"issue":"94720","key":"e_1_3_2_37_1","first-page":"11","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-1776 (1996), 11.","journal-title":"Lecture Notes on the Status of IEEE"},{"key":"e_1_3_2_38_1","first-page":"54","volume-title":"Bridging Data and Decisions","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."},{"key":"e_1_3_2_39_1","doi-asserted-by":"publisher","DOI":"10.1006\/jsco.1995.1022"},{"key":"e_1_3_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/103147.103159"},{"key":"e_1_3_2_41_1","unstructured":"Christopher Lourenco Jinhao Chen Erick Moreno-Centeno and Timothy Davis. 2022. SParse EXact software for solving linear systems. Retrieved from https:\/\/github.com\/clouren\/spex."},{"key":"e_1_3_2_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/18M1202499"},{"key":"e_1_3_2_43_1","first-page":"1","article-title":"Un m\u00e9todo n\u00famerico para c\u00e1lculo matricial","volume":"2","author":"Montante-Pardo Ren\u00e9 M.","year":"1977","unstructured":"Ren\u00e9 M. Montante-Pardo and Marco A. M\u00e9ndez-Cavazos. 1977. Un m\u00e9todo n\u00famerico para c\u00e1lculo matricial. Revista T\u00e9cnico-Cient\u00edfica de Divulgaci\u00f3n 2 (1977), 1\u201324.","journal-title":"Revista T\u00e9cnico-Cient\u00edfica de Divulgaci\u00f3n"},{"key":"e_1_3_2_44_1","unstructured":"Victor Shoup et\u00a0al. 2001. NTL: A library for doing number theory. https:\/\/libntl.org\/."},{"key":"e_1_3_2_45_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1984-0725988-X"},{"key":"e_1_3_2_46_1","unstructured":"Dan Steffy. 2010a. BasisLIB INT. Retrieved from http:\/\/hpac.imag.fr\/Matrices\/BasisLIB\/."},{"key":"e_1_3_2_47_1","unstructured":"Dan Steffy. 2010b. BasisLIB INT. Retrieved from https:\/\/github.com\/clouren\/BasisLIB_INT."},{"key":"e_1_3_2_48_1","volume-title":"Topics in Exact Precision Mathematical Programming","author":"Steffy Daniel E.","year":"2011","unstructured":"Daniel E. Steffy. 2011. Topics in Exact Precision Mathematical Programming. Ph.D. Dissertation. Georgia Institute of Technology."},{"key":"e_1_3_2_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1986.1057137"},{"key":"e_1_3_2_50_1","unstructured":"Roland Wunderling. 1997. SoPlex: The sequential object-oriented simplex class library. https:\/\/soplex.zib.de\/."}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519024","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519024","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:12:20Z","timestamp":1750191140000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519024"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,26]]},"references-count":49,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,6,30]]}},"alternative-id":["10.1145\/3519024"],"URL":"https:\/\/doi.org\/10.1145\/3519024","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"value":"0098-3500","type":"print"},{"value":"1557-7295","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,5,26]]},"assertion":[{"value":"2020-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-05-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}