Roundoff-Error-Free Algorithms for Solving Linear Systems via Cholesky and LU Factorizations

摘要

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.