Business Intelligence

Gaussian Elimination Based Algorithms on the GPU

Free registration required

Executive Summary

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.

  • Format: PDF
  • Size: 212.3 KB