LU-GPU: Efficient Algorithms for Solving Dense Linear Systems on Graphics Hardware

Nico Galoppo, Naga K. Govindaraju, Michael Henson, Dinesh Manocha
University of North Carolina at Chapel Hill
In SC ’05: Proceedings of the 2005 ACM/IEEE conference on Supercomputing (2005)


   title={LU-GPU: Efficient algorithms for solving dense linear systems on graphics hardware},

   author={Galoppo, N. and Govindaraju, N.K. and Henson, M. and Manocha, D.},

   booktitle={Proceedings of the 2005 ACM/IEEE conference on Supercomputing},




   organization={IEEE Computer Society}


Download Download (PDF)   View View   Source Source   



We present a novel algorithm to solve dense linear systems using graphics processors (GPUs). We reduce matrix decomposition and row operations to a series of rasterization problems on the GPU. These include new techniques for streaming index pairs, swapping rows and columns and parallelizing the computation to utilize multiple vertex and fragment processors. We also use appropriate data representations to match the rasterization order and cache technology of graphics processors. We have implemented our algorithm on different GPUs and compared the performance with optimized CPU implementations. In particular, our implementation on a NVIDIA GeForce 7800 GPU outperforms a CPU-based ATLAS implementation. Moreover, our results show that our algorithm is cache and bandwidth efficient and scales well with the number of fragment processors within the GPU and the core GPU clock rate. We use our algorithm for fluid flow simulation and demonstrate that the commodity GPU is a useful co-processor for many scientific applications.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: