EAGER: Optimization without Round-off Errors

这项探索性研究的早期概念拨款（EAGER）为进一步开发求解线性方程组的算法提供了资金，该算法比高斯消去法具有特殊的优势，因为该算法没有舍入误差。该算法将被定制和适应，以在现有的优化算法中使用。正在进一步开发的算法的关键特性是它在整个执行过程中保持数字的完整性。特别是，尽管该算法确实包含除法（这对算法的多项式时间复杂度至关重要），但所有除法的余数都为零。本文将对算法进行详细的复杂度分析；具体来说，将研究其运行时间和在整个算法执行过程中表示数字所需的位数。还将研究对算法的修改以执行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.