Back to search

Lethbridge, Alta. : University of Lethbridge, Dept. of Mathematics and Computer Science

Star bi-coloring of bipartite graphs

Abstract

dc:description.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.

Degree

thesis:*
Level thesis:degree_level
Masters
Grantor dc:publisher
Lethbridge, Alta. : University of Lethbridge, Dept. of Mathematics and Computer Science
Year dc:date.issued
2019

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Hasan, Ahmed Shoeb Al
  • University of Lethbridge. Faculty of Arts and Science
Advisor dc:contributor.supervisor
  • Hossain, Shahadat

Subjects

dc:subject × 4

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/10133/5656

Chain of custody

source
Harvested from
University of Lethbridge
Base URL
opus.uleth.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Hasan, Ahmed Shoeb Al; University of Lethbridge. Faculty of Arts and Science. Star bi-coloring of bipartite graphs. Masters thesis, Lethbridge, Alta. : University of Lethbridge, Dept. of Mathematics and Computer Science, 2019. https://hdl.handle.net/10133/5656