Name
Abstract | ||
|---|---|---|
The revised simplex algorithm (RSA) is a typical algorithm for solving linear programming problems. Many theoretical modifications have been done to make the algorithm more efficient, but almost all of them were based on single-instruction single-data architecture processors (CPUs), which could not make full use of the inherent parallel characteristics of RSAs. We propose a novel single-instruction multiple-data architecture processor (GPU) based on the RSA in this paper. The intensive matrix manipulations of a traditional RSA are offloaded to the GPU, which helps to make full use of its powerful parallel processing ability. We implemented the GPU-based RSA on compute unified device architecture (CUDA). Numerical experiments on randomly generated linear programs show that the GPU-based RSA can not only find the correct optimal solutions, but can also reach a speed of up to 100 times as fast as that of a CPU-based RSA: it also runs 3 to 11 times as fast as MATLAB. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1007/s11042-018-5947-z | Multimedia Tools Appl. |
Keywords | Field | DocType |
CUDA, GPU, Revised simplex algorithm, SIMD | Computer vision,MATLAB,Simplex algorithm,Matrix (mathematics),Computer science,CUDA,Parallel computing,Parallel processing,SIMD,Linear programming,Artificial intelligence | Journal |
Volume | Issue | ISSN |
77 | 22 | 1380-7501 |
Citations | PageRank | References |
1 | 0.35 | 18 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Lili He | 1 | 2 | 1.03 |
| Hongtao Bai | 2 | 14 | 4.70 |
| Yu Jiang | 3 | 9 | 5.82 |
| Dan-tong Ou-yang | 4 | 23 | 4.77 |
| Shanshan Jiang | 5 | 129 | 20.15 |