Elements: Software: Roundoff-Error-Free Algorithms for Large-Scale, Sparse Systems of Linear Equations and Optimization

求解线性方程组对于解决医疗保健、发电、国防、经济、物理、化学、数学、计算机科学和工程等众多应用中的问题至关重要。如今，大量这些关键应用对更快、更可靠和更准确的解决方案的需求不断增长。例如，对于前列腺癌近距离放射治疗（在肿瘤内放置放射性“种子”）来说，更精确的治疗方案被证明成本更低、侵入性更小、更安全、结果更可靠。同样，通过更准确地解决发电调度优化问题，可以节省数百万美元，并产生更清洁的能源。矛盾的是，当今最先进的软件工具仅限于计算有限精度的解决方案（例如，处理计划和电力调度）。这部分是由于依赖于浮点算术（即使用截断的十进制数的算术）的计算方法的流行。与此同时，许多应用程序中的实际问题变得越来越大，因此更容易由于舍入错误（截断十进制数时引入的错误）而产生不正确的结果。该项目的主要目标是设计，创建和部署计算工具来解决大规模，线性方程和优化问题的稀疏系统，而不会产生任何误差。由于解决线性方程组和优化问题的系统无处不在，这个项目的成果将直接转化为软件，为学术界、工业界和政府的应用提供更可靠的应用。大规模的、稀疏的线性方程组（SLEs）和线性优化问题（lp）经常被求解，求解器的准确性/正确性被认为是理所当然的。然而，最先进的解决方案通常会报告不正确的结果，有些令人震惊的是将可行问题错误地分类为不可行问题，反之亦然，甚至完全失败。此外，精确解决SLEs和lp对于固定精度标准被认为不够的应用至关重要，包括医疗保健、发电、生物学、组合拍卖和数学证明的正式验证等特定应用。因此，本项目的首要目标是设计高效的算法和实现健壮的软件，以可靠、准确地求解大规模、稀疏的SLEs，而不存在任何舍入误差。这个目标将建立在我们最近设计的无舍入误差（REF） LU和密集矩阵的Cholesky分解的基础上。该项目的第二个目标是设计有效的算法和实现健壮的软件，以可靠和准确地（REF）解决大规模，稀疏lp。该项目的具体成果包括：(1)为大规模稀疏矩阵设计一个高效的reffactorization框架，包括设计考虑条目位数增长的良好填充减少顺序；(2)设计REF优化算法，精确求解大规模的稀疏线性规划；(3)我们的软件将经过严格的测试，使用完整的100%测试覆盖率套件和脚手架代码来测试循环不变量和数据完整性。软件产品将作为算法论文提交给ACM数学软件交易，代码本身、测试套件和文档将经过严格的同行审查。最后，我们将把我们的求解器合并到我们现有的SuiteSparse安装中，包括所有的Linux发行版，最终目标是集成到MATLAB中，从而为广泛的用户群所访问。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Solving systems of linear equations is central to solving problems in numerous applications within healthcare, power generation, national defense, economics, physics, chemistry, mathematics, computer science and engineering. Nowadays, a large number of these critical applications have an ever-increasing need for faster, more reliable, and more accurate solutions. For example, more accurate treatment plans are proven to be less costly, less invasive, safer, and more reliable outcomes for prostate-cancer brachytherapy (placement of radioactive "seeds" inside a tumor). Similarly, millions of dollars can be saved, and cleaner energy can be produced, by solving the power generation dispatch optimization problem with more accuracy. Paradoxically, today's state-of-the-art software tools are limited to calculating limited-precision solutions (e.g., treatment plans and power dispatches). This is due in part to the prevalence of computing methods relying on floating-point arithmetic (i.e., arithmetic using truncated decimal numbers). At the same time, real-life problems in a wide range of applications are becoming larger and so more prone to incorrect results due to roundoff errors (errors introduced when truncating the decimal numbers). The primary goal of this project is to design, create, and deploy computational tools to solve large-scale, sparse systems of linear equations and optimization problems without any error at all. Because of the ubiquity of solving systems of linear equations and optimization problems, the outcomes of this project will directly translate in software that is more reliable for applications across academia, industry, and government. Large-scale, sparse systems of linear equations (SLEs) and linear optimization problems (LPs) are routinely solved and the accuracy/correctness of solvers is taken for granted. However, state-of-the-art solvers commonly report incorrect results, some as striking as misclassifying feasible problems as infeasible and vice versa or even failing altogether. Moreover, exactly solving SLEs and LPs is of fundamental importance for applications where fixed-precision standards have been deemed inadequate, including specific applications in healthcare, power generation, biology, combinatorial auctions, and formal verification of mathematical proofs. Therefore, the first objective of this project is to devise efficient algorithms and implement robust software to reliably and exactly solve large-scale, sparse SLEs, free of any roundoff error. This objective will build on our recently devised roundoff-error-free (REF) LU and Cholesky factorizations for dense matrices. The second objective of this project is to devise efficient algorithms and implement robust software to reliably and exactly (REF) solve large-scale, sparse LPs. The specific outcomes of this project include: (1) Devise an efficient REF factorization framework for large-scale sparse matrices, including devising good fill-reducing orderings that consider the bit-size growth of the entries; (2) Devise REF optimization algorithms to exactly solve large-scale, sparse linear programs; (3) Our software will be rigorously tested, with a full 100% test coverage suite and scaffolding code to test loop invariants and data sanity. The software products will be submitted as algorithm papers to the ACM Transactions on Mathematical software, where the code itself, test suite and documentation undergo rigorous peer review. Finally, we will incorporate our solvers into our existing SuiteSparse installations, including all Linux distros with the ultimate goal of being integrated into MATLAB and thus accessible to a wide user base.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.