Roundoff-error-free algorithms for solving linear systems via cholesky and LU factorizations

Adolfo R. Escobedo, Erick Moreno-Centeno

Research output: Contribution to journalArticlepeer-review

8 Scopus citations


LU and Cholesky factorizations are computational tools for efficiently solving linear systems that play a central role in solving linear programs and several other classes of mathematical programs. In many documented cases, however, the roundoff errors accrued during the construction and implementation of these factorizations lead to the misclassification of feasible problems as infeasible and vice versa. Hence, reducing these roundoff errors or eliminating them altogether is imperative to guarantee the correctness of the solutions provided by optimization solvers. To achieve this goal without having to use rational arithmetic, we introduce two roundoff-error-free factorizations that require storing the same number of individual elements and performing a similar number of operations as the traditional LU and Cholesky factorizations. Additionally, we present supplementary roundoff-error-free forward and backward substitution algorithms, thereby providing a complete tool set for solving systems of linear equations exactly and efficiently. An important property shared by the featured factorizations and substitution algorithms is that their individual coefficients' maximum word length-i.e., the maximum number of digits required for expression-is bounded polynomially. Unlike the rational arithmetic methods used in practice to solve linear systems exactly, however, the algorithms herein presented do not require any gcd calculations to bound the entries' word length. We also derive various other related theoretical results, including the total computational complexity of all the roundoff-error-free processes herein presented.

Original languageEnglish (US)
Pages (from-to)677-689
Number of pages13
JournalINFORMS Journal on Computing
Issue number4
StatePublished - Sep 1 2015
Externally publishedYes


  • Exact algorithms
  • Exact mathematical programming
  • Matrix factorizations
  • Roundoff errors
  • Solving linear systems

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Computer Science Applications
  • Management Science and Operations Research


Dive into the research topics of 'Roundoff-error-free algorithms for solving linear systems via cholesky and LU factorizations'. Together they form a unique fingerprint.

Cite this