SBIR Phase I:GPU Software for Sparse Linear Programming

Award Information
Agency:
National Science Foundation
Branch
n/a
Amount:
$150,000.00
Award Year:
2010
Program:
SBIR
Phase:
Phase I
Contract:
1014271
Award Id:
99149
Agency Tracking Number:
1014271
Solicitation Year:
n/a
Solicitation Topic Code:
1B
Solicitation Number:
n/a
Small Business Information
932 Waterview Way, Apartment D, Champaign, IL, 61822
Hubzone Owned:
N
Minority Owned:
N
Woman Owned:
N
Duns:
832759141
Principal Investigator:
JosephElble
PhD
(217) 418-9239
joseph.elble@gmail.com
Business Contact:
JosephElble
PhD
(217) 418-9239
joseph.elble@gmail.com
Research Institute:
n/a
Abstract
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.

* information listed above is at the time of submission.

Agency Micro-sites


SBA logo

Department of Agriculture logo

Department of Commerce logo

Department of Defense logo

Department of Education logo

Department of Energy logo

Department of Health and Human Services logo

Department of Homeland Security logo

Department of Transportation logo

Enviromental Protection Agency logo

National Aeronautics and Space Administration logo

National Science Foundation logo
US Flag An Official Website of the United States Government