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

cusparse<t>csrilu02

and

cusparse<t>csrsv2_solve

Furthermore, cuSPARSE offers the

cusparse<t>csrcolor

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.

** **