Gaussian Elimination Based Algorithms on the GPU
Source: UC Regents
The authors implemented and evaluated several Gaussian elimination based algorithms on Graphic Processing Units (GPUs). These algorithms, LU decomposition without pivoting, all-pairs shortest-paths, and transitive closure, all have similar data access patterns. The impressive computational power and memory bandwidth of the GPU make it an attractive platform to run such computationally intensive algorithms. Although improvements over CPU implementations have previously been achieved for those algorithms in terms of raw speed, the utilization of the underlying computational resources was quite low. They implemented a recursively partioned all-pairs shortest-paths algorithm that harnesses the power of GPUs better than existing implementations.