EAGER: Optimization without Round-off Errors

这一早期概念探索性研究拨款(AGER)为进一步开发一种算法来解线性方程组提供了资金，该算法比高斯消去法具有独特的优势，因为该算法没有舍入误差。该算法将被定制和调整，以用于现有的优化算法。正在进一步开发的算法的关键特性是它在整个执行过程中保持了数字的完整性。具体地说，尽管算法确实包含除法(这对于算法的多项式时间复杂性至关重要)，但所有除法的余数都为零。将对算法进行详细的复杂性分析；具体地说，将调查其运行时间和在整个算法执行过程中表示数字所需的位数。还将研究执行LU因式分解的算法的修改。如果成功，这项研究的结果将有助于更深入地理解无舍入误差的计算线性代数及其在优化算法中的相关应用。在线性规划(LP)的背景下，这项研究将使我们能够准确地求解大规模LP；这反过来将显著提高整数规划求解器的精度和速度。此外，由于求解线性方程组是许多数值算法的关键子程序，因此这项研究将影响许多线性系统频繁出现的应用领域，包括经济、物理、化学和工程。

This Early-concept Grant for Exploratory Research (EAGER) provides funding to further develop an algorithm to solve systems of linear equations with a specific advantage over Gaussian Elimination in that the algorithm does not have round-off errors. The algorithm will be tailored and adapted to be used within existing optimization algorithms. The key property of the algorithm being further developed is that it maintains the integrality of the numbers throughout its execution. In particular, although the algorithm does contain divisions (which is crucial for the polynomial-time complexity of thealgorithm) all the divisions have a remainder of zero. A detailed complexity analysis of the algorithm will be performed; specifically, both its running time and the number of bits required to represent the numbers throughout the algorithm's execution will be investigated. A modification of the algorithm to perform LU factorizations will also be studied. Finally, the algorithm will be adapted to enable its use for the basis updates performed in state-of-the-art implementations of the revised simplex method.If successful, the outcomes of this research will lead to a deeper understanding of computational linear algebra free of round-off errors and the associated applications within optimization algorithms. In the linear programming (LP) context, this research will enable us to solve large-scale LPs exactly; this, in turn, will significantly improve the accuracy and speed of integer programming solvers. In addition, since solving systems of linear equations is a critical subroutine of many numerical algorithms, this research will impact many application areas where linear systems frequently arise, including economics, physics, chemistry, and engineering.