Star bi-coloring of bipartite graphs
Date
2019
Authors
Hasan, Ahmed Shoeb Al
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
Evaluation of the Jacobian is the most computationally expensive operation while solving a non-linear system. Knowledge of the sparsity pattern in advance reduces the computational cost. Bi-directional partitioning to determine non-zeroes in the sparse matrix works better than unidirectional partitioning for dense rows and dense columns. We have developed a bidirectional coloring algorithm that determines all the non-zeroes of a sparse Jacobian matrix. Our algorithm is inspired by complete direct cover. Several numerical experiments have been carried out on standard data sets. Test results ensure that our proposed algorithm works better than existing algorithms. We have implemented our algorithm using the data structures and partitioning algorithms defined in software tool kit DSJM (Determine Sparse Jacobian Matrices). We have added new procedures in DSJM, which facilitates bi-directional partitioning.
Description
Keywords
Bipartite graphs , Computer algorithms , Jacobians , Machine learning