Coloring and degeneracy for determining very large and sparse derivative matrices
Suny, Ashraful Huq
University of Lethbridge. Faculty of Arts and Science
Lethbridge, Alta : University of Lethbridge, Dept. of Mathematics and Computer Science
Estimation of large sparse Jacobian matrix is a prerequisite for many scientific and engineering problems. It is known that determining the nonzero entries of a sparse matrix can be modeled as a graph coloring problem. To find out the optimal partitioning, we have proposed a new algorithm that combines existing exact and heuristic algorithms. We have introduced degeneracy and maximum k-core for sparse matrices to solve the problem in stages. Our combined approach produce better results in terms of partitioning than DSJM and for some test instances, we report optimal partitioning for the first time.
degeneracy , graph coloring , greedy coloring , maximum k-core , optimal partitioning , unidirectional partitioning