SBIR Phase I: GPU Software for Sparse Linear Programming

这个小企业创新研究（SBIR）第一阶段项目将调查开发一个实际的线性规划的单纯形算法的并行实现的可行性。 随着对解决经济各部门中更大和更复杂的决策问题的需求的增加，对用于在线和时间关键操作的并行单纯形算法的需求也在增加。然而，该算法的并行版本目前无法优于适当的串行代码的工业相关的问题，涉及稀疏的大规模矩阵。拟议的研究将探索一个细粒度的并行化比以前尝试的单纯形算法。因此，所提出的单纯形算法的实现将利用图形处理单元（GPU）的最新进展，同时能够受益于该算法的上下文中的任何未来串行算法进展。除了可调用的库和独立的可执行文件外，还将通过支持云的商业服务提供实施。 单纯形算法的并行化一直是科学计算中的一个主要挑战。拟议的研究将涉及对因子分解和定价算法的不同组合在现代GPU上的性能进行系统调查。如果成功，拟议的工作将为科学、工程和商业等不同领域的决策提供一种支持技术。 线性规划广泛应用于从数据挖掘到航空公司调度，癌症治疗，工程设计，财务决策和物流等应用。因此，拟议的工作提供了一个独特的机会，以提高国家的商业基础设施的竞争力。

This Small Business Innovation Research (SBIR) Phase I project will investigate the feasibility of developing a practical parallel implementation of the simplex algorithm for linear programming. As the demand to solve larger and more complex decision-making problems in all sectors of the economy increases, so does the demand for a parallel simplex algorithm for on-line and time-critical operations. Yet, parallel versions of this algorithm are currently unable to outperform appropriate serial codes for industrially-relevant problems that involve sparse large-scale matrices. The proposed research will explore a finer-grain parallelization than previously attempted for the simplex algorithm. As a result, the proposed implementation of the simplex algorithm will harness recent advances in graphics processing units (GPUs), while being capable of benefiting from any future serial algorithmic advances in the context of this algorithm. In addition to callable libraries and stand-alone executables, the implementation will be offered through cloud-enabled commercial services. The parallelization of the simplex algorithm has remained a major challenge in scientific computing. The proposed research will involve a systematic investigation of different combinations of factorization and pricing algorithms with regard to their performance on modern GPUs. If successful, the proposed work will result in an enabling technology for decision making in diverse areas across science and engineering and commerce. Linear programming is used extensively in applications ranging from data mining to airline scheduling, cancer therapy, engineering design, financial decision making, and logistics. As a result, the proposed work presents an unique opportunity to improve the competitiveness of the nation's commercial infrastructure.