{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T16:43:04Z","timestamp":1787330584435,"version":"build-2736575974"},"reference-count":48,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"name":"Texas A&M Graduate Merit Fellowship"},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CMMI-1252456"],"award-info":[{"award-number":["CMMI-1252456"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Matrix Anal. Appl."],"published-print":{"date-parts":[[2019,1]]},"abstract":"<jats:p>The roundoff-error-free (REF) LU factorization, along with the REF forward and backward substitution algorithms, allows a rational system of linear equations to be solved exactly and efficiently. The REF LU factorization framework has two key properties: all operations are integral, and the size of each entry is bounded polynomially---a bound that rational arithmetic Gaussian elimination achieves only via the use of computationally expensive greatest common divisor operations. This paper develops a sparse version of REF LU, termed the Sparse Left-looking Integer-Preserving (SLIP) LU factorization, which exploits sparsity while maintaining integrality of all operations. In addition, this paper derives a tighter polynomial bound on the size of entries in L and U and shows that the time complexity of SLIP LU is proportional to the cost of the arithmetic work performed. Last, SLIP LU is shown to significantly outperform a modern full-precision rational arithmetic LU factorization approach on a set of real world instances. In all, SLIP LU is a framework to efficiently and exactly solve sparse linear systems.<\/jats:p>","DOI":"10.1137\/18m1202499","type":"journal-article","created":{"date-parts":[[2019,5,14]],"date-time":"2019-05-14T10:14:45Z","timestamp":1557828885000},"page":"609-638","source":"Crossref","is-referenced-by-count":12,"title":["Exact Solution of Sparse Linear Systems via Left-Looking Roundoff-Error-Free LU Factorization in Time Proportional to Arithmetic Work"],"prefix":"10.1137","volume":"40","author":[{"given":"Christopher","family":"Lourenco","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Adolfo R.","family":"Escobedo","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Erick","family":"Moreno-Centeno","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Timothy A.","family":"Davis","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2019,5,14]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479894278952"},{"key":"atypb2","unstructured":"D. Applegate, W. Cook, S. Dash, and D. Espinoza,\n                      QSOPT ex\n                      ,mailto:http:\/\/www.dii.uchile.cl\/~daespino\/QSoptExact_doc\/main.html, 2007."},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2006.12.010"},{"key":"atypb4","first-page":"565","volume":"22","author":"Bareiss E. H.","year":"1968","journal-title":"Math. Comp."},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1093\/imamat\/10.1.68"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1145\/2382585.2382589"},{"key":"atypb7","first-page":"104","author":"Cook W.","year":"2011","journal-title":"Heidelberg"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1145\/1916461.1916463"},{"key":"atypb9","first-page":"145","author":"Davis T. A.","year":"2006","journal-title":"Philadelphia"},{"key":"atypb10","unstructured":"T. Davis, W. Hager, and I. Duff,\n                      SuiteSparse: A Suite of Sparse Matrix Software\n                      ,http:\/\/faculty.cse.tamu.edu\/davis\/suitesparse.html, 2014."},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"T. A. Davis,\n                      Direct Methods for Sparse Linear Systems\n                      , SIAM, Philadelphia, 2006,https:\/\/doi.org\/10.1137\/1.9780898718881.","DOI":"10.1137\/1.9780898718881"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1145\/1024074.1024080"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1145\/1024074.1024079"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492916000076"},{"key":"atypb15","first-page":"255","author":"Dhiflaoui M.","year":"2003","journal-title":"Philadelphia"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1007\/BF01459082"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.6028\/jres.071B.033"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2015.0653"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1137\/16M1089630"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1145\/3199571"},{"key":"atypb21","unstructured":"D. G. Espinoza,\n                      On Linear Programming, Integer Programming and Cutting Planes\n                      , Ph.D. thesis, Georgia Institute of Technology, Atlanta, GA, 2006."},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(99)00012-7"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479887139455"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1137\/0613024"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1137\/0909058"},{"key":"atypb26","unstructured":"A. M. Gleixner,\n                      Exact and Fast Algorithms for Mixed-Integer Nonlinear Programming\n                      , Ph.D. thesis, Technische Universit\u00e4t, Berlin, Berlin, Germany, 2015."},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2016.0692"},{"key":"atypb28","unstructured":"T. Granlund et al.\n                      GNU MP 6.0 Multiple Precision Arithmetic Library\n                      , Samurai Media Limited, Wickford, England, 2015."},{"key":"atypb29","first-page":"240","volume":"17","author":"Hadamard J.","year":"1893","journal-title":"Bull. Sci. Math"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2005.162.1065"},{"key":"atypb31","unstructured":"R. A. Horn and C. R. Johnson,\n                      Matrix Analysis\n                      , Cambridge University Press, Cambridge, UK, 2012."},{"key":"atypb32","unstructured":"B. Jacob, G. Guennebaud, et al.\n                      Eigen: C++ Template Library for Linear Algebra\n                      ,http:\/\/eigen.tuxfamily.org\/index.php?title=Main_Page, 2013."},{"key":"atypb33","first-page":"29","author":"Kaltofen E.","year":"1991","journal-title":"Berlin"},{"key":"atypb34","first-page":"54","author":"Klotz E.","year":"2014","journal-title":"MD"},{"key":"atypb35","unstructured":"D. E. Knuth,\n                      The Art of Computer Programming: Sorting and Searching\n                      , Vol. 3, Pearson Education, London, UK, 1998."},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(03)00094-4"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1006\/jsco.1995.1022"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1137\/130912438"},{"key":"atypb39","first-page":"1","volume":"2","author":"Montante-Pardo R. M.","year":"1977","journal-title":"Revista T\u00e9cnico-Cient\u00edfica de Divulgaci\u00f3n"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-003-0433-3"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623402401804"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1007\/BF02242355"},{"key":"atypb43","unstructured":"D. E. Steffy,\n                      Topics in Exact Precision Mathematical Programming\n                      , Ph.D. thesis, Georgia Institute of Technology, Atlanta, GA, 2011."},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2005.11.001"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1986.1057137"},{"key":"atypb46","unstructured":"R. Wunderling,\n                      Paralleler und objektorientierter Simplex-Algorithmus\n                      , Ph.D. thesis, Technische Universit\u00e4t Berlin, Berlin, Germany, 1996."},{"key":"atypb47","unstructured":"R. Wunderling,\n                      SoPlex: The Sequential Object-Oriented Simplex Class Library\n                      , 1997, https:\/\/soplex.zib.de\/."},{"key":"atypb48","doi-asserted-by":"publisher","DOI":"10.1137\/0602010"}],"container-title":["SIAM Journal on Matrix Analysis and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/18M1202499","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T16:14:00Z","timestamp":1787328840000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/18M1202499"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1]]},"references-count":48,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,1]]}},"alternative-id":["10.1137\/18M1202499"],"URL":"https:\/\/doi.org\/10.1137\/18m1202499","relation":{},"ISSN":["0895-4798","1095-7162"],"issn-type":[{"value":"0895-4798","type":"print"},{"value":"1095-7162","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1]]}}}