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.