Solving general sparse linear systems with LU factorization and graph coloring

The fast solution of sparse linear systems is a very critical problem in many applications.

As of November 2015, the cuSPARSE library offers routines for the solution of sparse linear systems based on LU decomposition, in particular




Furthermore, cuSPARSE offers the


which implements graph coloring. The use of graph coloring for incomplete LU-factorization is described in Graph Coloring: More Parallelism for Incomplete-LU Factorization
and M.Naumov, P.Castonguay, J. Cohen, “Parallel Graph Coloring with Applications to the incomplete-LU factorization on the GPU”, NVIDIA Research Technical Report, May, 2015.

The idea is to apply the graph coloring algorithm to the row dependency graph associated to the coefficient matrix of the system and then reorder the system equation accordingly so that the LU factorization routine can extract more parallelism.

On our GitHub website you may find a fully worked example using the above idea.


Leave a Reply

Your email address will not be published. Required fields are marked *