A Computational Comparison of Basis Updating Schemes for the Simplex Algorithm on a CPU-GPU System
A Computational Comparison of Basis Updating Schemes for the Simplex Algorithm on a CPU-GPU System作者机构：Department of Applied Informatics School of Information Sciences University of Macedonia Thessaloniki Greece
出 版 物：《American Journal of Operations Research》 (美国运筹学期刊（英文）)
年 卷 期：2013年第3卷第6期
页 面：497-505页
学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学]
主 题：Simplex Algorithm Basis Inverse Graphics Processing Unit MATLAB Compute Unified Device Architecture
摘 要：The computation of the basis inverse is the most time-consuming step in simplex type algorithms. This inverse does not have to be computed from scratch at any iteration, but updating schemes can be applied to accelerate this calculation. In this paper, we perform a computational comparison in which the basis inverse is computed with five different updating schemes. Then, we propose a parallel implementation of two updating schemes on a CPU-GPU System using MATLAB and CUDA environment. Finally, a computational study on randomly generated full dense linear programs is preented to establish the practical value of GPU-based implementation.
维普期刊数据库