Coloring and degeneracy for determining very large and sparse derivative matrices
Date
2016
Authors
Suny, Ashraful Huq
University of Lethbridge. Faculty of Arts and Science
Journal Title
Journal ISSN
Volume Title
Publisher
Lethbridge, Alta : University of Lethbridge, Dept. of Mathematics and Computer Science
Abstract
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.
Description
Keywords
degeneracy , graph coloring , greedy coloring , maximum k-core , optimal partitioning , unidirectional partitioning