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

点击翻译按钮获取中文摘要

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.