{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,16]],"date-time":"2026-01-16T11:52:32Z","timestamp":1768564352796,"version":"3.49.0"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2018,6,16]],"date-time":"2018-06-16T00:00:00Z","timestamp":1529107200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"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":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2018,12,31]]},"abstract":"<jats:p>\n            Exact solving of systems of linear equations (SLEs) is a fundamental subroutine within number theory, formal verification of mathematical proofs, and exact-precision mathematical programming. Moreover, efficient exact SLE solution methods could be valuable for a growing body of science and engineering applications where current fixed-precision standards have been deemed inadequate. This article contains key derivations relating, and computational tests comparing, two exact direct solution frameworks: roundoff-error-free (REF) LU factorization and rational arithmetic LU factorization. Specifically, both approaches solve the linear system\n            <jats:italic>Ax<\/jats:italic>\n            =\n            <jats:italic>b<\/jats:italic>\n            by factoring the matrix A into the product of a lower triangular (L) and upper triangular (U) matrix,\n            <jats:italic>A<\/jats:italic>\n            =\n            <jats:italic>LU<\/jats:italic>\n            . Most significantly, the featured findings reveal that the integer-preserving REF factorization framework solves dense SLEs one order of magnitude faster than the exact rational arithmetic approach while requiring half the memory. Since rational LU is utilized for basic solution validation in exact linear and mixed-integer programming, these results offer preliminary evidence of the potential of the REF factorization framework to be utilized within this specific context. Additionally, this article develops and analyzes an efficient streamlined version of Edmonds\u2019s Q-matrix approach that can be implemented as another basic solution validation approach. Further experiments demonstrate that the REF factorization framework also outperforms this alternative integer-preserving approach in terms of memory requirements and computational effort. General purpose codes to solve dense SLEs exactly via any of the aforementioned methods have been made available to the research and academic communities.\n          <\/jats:p>","DOI":"10.1145\/3199571","type":"journal-article","created":{"date-parts":[[2018,6,18]],"date-time":"2018-06-18T12:28:11Z","timestamp":1529324891000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Solution of Dense Linear Systems via Roundoff-Error-Free Factorization Algorithms"],"prefix":"10.1145","volume":"44","author":[{"given":"Adolfo R.","family":"Escobedo","sequence":"first","affiliation":[{"name":"Arizona State University, Tempe, AZ"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Erick","family":"Moreno-Centeno","sequence":"additional","affiliation":[{"name":"Texas A8M University, TAMU, College Station, TX"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christopher","family":"Lourenco","sequence":"additional","affiliation":[{"name":"Texas A8M University, TAMU, College Station, TX"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,6,16]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2006.12.010"},{"key":"e_1_2_1_2_1","unstructured":"David L. Applegate Sanjeeb Dash William Cook and Daniel G. Espinoza. 2007. QSopt_ex Rational LP Solver. Retrieved July 1 2016 from http:\/\/www.dii.uchile.cl\/&sim;daespino.  David L. Applegate Sanjeeb Dash William Cook and Daniel G. Espinoza. 2007. QSopt_ex Rational LP Solver. Retrieved July 1 2016 from http:\/\/www.dii.uchile.cl\/&sim;daespino."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/502800.502804"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.3390\/math3020337"},{"key":"e_1_2_1_5_1","first-page":"565","article-title":"Sylvester\u2019s identity and multistep integer-preserving Gaussian elimination","volume":"22","author":"Bareiss Erwin H.","year":"1968","journal-title":"Math. Comp."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1093\/imamat\/10.1.68"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10543-015-0547-z"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073884.1073899"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"William Cook Thorsten Koch Daniel Steffy and Kati Wolter. 2011. An exact rational mixed-integer programming solver. Integer Programming and Combinatoral Optimization. Springer Berlin Heidelberg 104--116.   William Cook Thorsten Koch Daniel Steffy and Kati Wolter. 2011. An exact rational mixed-integer programming solver. Integer Programming and Combinatoral Optimization. Springer Berlin Heidelberg 104--116.","DOI":"10.1007\/978-3-642-20807-2_9"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-013-0055-6"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1916461.1916463"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.epsr.2015.07.001"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 255--256","author":"Dhiflaoui Marcel","year":"2003"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01459082"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.6028\/jres.071B.033"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1051\/ro\/1997310202031"},{"key":"e_1_2_1_17_1","unstructured":"Adolfo R. Escobedo. 2016. Foundational Factorization Algorithms for the Efficient Roundoff-Error-Free Solution of Optimization Problems. Ph.D. Dissertation. Department of Industrial and Systems Engineering Texas A8M University College Station TX.  Adolfo R. Escobedo. 2016. Foundational Factorization Algorithms for the Efficient Roundoff-Error-Free Solution of Optimization Problems. Ph.D. Dissertation. Department of Industrial and Systems Engineering Texas A8M University College Station TX."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2015.0653"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1089630"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPWRS.2013.2286009"},{"key":"e_1_2_1_21_1","unstructured":"Daniel G. Espinoza and Marcos Goycoolea. 2003. EGlib Efficient General Library. Retrieved July 1 2016 from http:\/\/dii.uchile.cl\/&sim;daespino\/EGlib_doc.  Daniel G. Espinoza and Marcos Goycoolea. 2003. EGlib Efficient General Library. Retrieved July 1 2016 from http:\/\/dii.uchile.cl\/&sim;daespino\/EGlib_doc."},{"key":"e_1_2_1_22_1","volume-title":"Computer Solution of Linear Algebraic Systems","volume":"7","author":"George"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236463.1236468"},{"key":"e_1_2_1_24_1","unstructured":"Gerald Gamrath Tobias Fischer Tristan Gally Ambros M. Gleixner Gregor Hendel Thorsten Koch Stephen J. Maher Matthias Miltenberger Benjamin M\u00fcller Marc E. Pfetsch etal 2016. The SCIP optimization suite. ZIB Rep. (2016) 15--60.  Gerald Gamrath Tobias Fischer Tristan Gally Ambros M. Gleixner Gregor Hendel Thorsten Koch Stephen J. Maher Matthias Miltenberger Benjamin M\u00fcller Marc E. Pfetsch et al. 2016. The SCIP optimization suite. ZIB Rep. (2016) 15--60."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(99)00012-7"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479887139455"},{"key":"e_1_2_1_27_1","unstructured":"Ambros Gleixner Matthias Miltenberger and Benjamin M\u00fcller. 2015. SoPlex: the sequential object-oriented simplex class library version 2.2. Retrieved July 1 2016 from http:\/\/soplex.zib.de.  Ambros Gleixner Matthias Miltenberger and Benjamin M\u00fcller. 2015. SoPlex: the sequential object-oriented simplex class library version 2.2. Retrieved July 1 2016 from http:\/\/soplex.zib.de."},{"key":"e_1_2_1_28_1","unstructured":"Ambros M. Gleixner. 2015. Exact and Fast Algorithms for Mixed-Integer Nonlinear Programming. Ph.D. Dissertation. Technische Universit\u00e4t Berlin.  Ambros M. Gleixner. 2015. Exact and Fast Algorithms for Mixed-Integer Nonlinear Programming. Ph.D. Dissertation. Technische Universit\u00e4t Berlin."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2442829.2442858"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/3192708.3192709"},{"key":"e_1_2_1_31_1","unstructured":"Torbj\u00f6rn Granlund et al. 2015. GNU MP 6.0 Multiple Precision Arithmetic Library Samurai Media Limited.   Torbj\u00f6rn Granlund et al. 2015. GNU MP 6.0 Multiple Precision Arithmetic Library Samurai Media Limited."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/258726.258836"},{"key":"e_1_2_1_33_1","volume-title":"Applied Algebra, Algebraic Algorithms and Error-Correcting Codes","author":"Kaltofen Erich"},{"key":"e_1_2_1_34_1","doi-asserted-by":"crossref","unstructured":"Ed Klotz. 2014. Identification assessment and correction of Ill-conditioning and numerical instability in linear and integer programs. TutORials in Operations Research: Bridging Data and Decisions. Informs 54--108.  Ed Klotz. 2014. Identification assessment and correction of Ill-conditioning and numerical instability in linear and integer programs. TutORials in Operations Research: Bridging Data and Decisions. Informs 54--108.","DOI":"10.1287\/educ.2014.0130"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(03)00094-4"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827502405094"},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","unstructured":"Ding Ma and Michael A. Saunders. 2015. Solving multiscale linear programs using the simplex method in quadruple precision. In Numerical Analysis and Optimization. Springer 223--235.  Ding Ma and Michael A. Saunders. 2015. Solving multiscale linear programs using the simplex method in quadruple precision. In Numerical Analysis and Optimization. Springer 223--235.","DOI":"10.1007\/978-3-319-17689-5_9"},{"key":"e_1_2_1_38_1","unstructured":"Hans D. Mittelmann. 2006. LPtestset. Retrieved July 1 2016 from http:\/\/plato.asu.edu\/ftp\/lptestset.  Hans D. Mittelmann. 2006. LPtestset. Retrieved July 1 2016 from http:\/\/plato.asu.edu\/ftp\/lptestset."},{"key":"e_1_2_1_39_1","unstructured":"Bruce A. Murtagh. 1981. Advanced Linear Programming: Computation and Practice. McGraw-Hill International Book Co.  Bruce A. Murtagh. 1981. Advanced Linear Programming: Computation and Practice. McGraw-Hill International Book Co."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/2990016.3114312"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.enganabound.2010.05.011"},{"key":"e_1_2_1_42_1","volume-title":"International Conference on Intelligent Computer Mathematics. Springer, 123--132","author":"Solovyev Alexey"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1940475.1940513"},{"key":"e_1_2_1_44_1","unstructured":"Daniel E. Steffy. 2011b. Topics in Exact Precision Mathematical Programming. Ph.D. Dissertation. Georgia Institute of Technology.   Daniel E. Steffy. 2011b. Topics in Exact Precision Mathematical Programming. Ph.D. Dissertation. Georgia Institute of Technology."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2005.11.001"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1986.1057137"},{"key":"e_1_2_1_47_1","unstructured":"James Hardy Wilkinson. 1963. Rounding Errors in Algebraic Processes. Prentice-Hall Englewood Cliffs NJ.  James Hardy Wilkinson. 1963. Rounding Errors in Algebraic Processes. Prentice-Hall Englewood Cliffs NJ."},{"key":"e_1_2_1_48_1","unstructured":"Roland Wunderling. 1996. Paralleler und Objektorientierter Simplex-Algorithmus. Ph.D. Dissertation. Technische Universit\u00e4t Berlin.  Roland Wunderling. 1996. Paralleler und Objektorientierter Simplex-Algorithmus. Ph.D. Dissertation. Technische Universit\u00e4t Berlin."}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3199571","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3199571","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3199571","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:07:18Z","timestamp":1750273638000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3199571"}},"subtitle":["Theoretical Connections and Computational Comparisons"],"short-title":[],"issued":{"date-parts":[[2018,6,16]]},"references-count":48,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,12,31]]}},"alternative-id":["10.1145\/3199571"],"URL":"https:\/\/doi.org\/10.1145\/3199571","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"value":"0098-3500","type":"print"},{"value":"1557-7295","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,6,16]]},"assertion":[{"value":"2016-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-06-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}