Back to search

Lethbridge, Alta. : University of Lethbridge, Faculty of Arts and Science, 2005

Graph coloring in sparse derivative matrix computation

Abstract

dc:description.abstract

There has been extensive research activities in the last couple of years to efficiently determine large sparse Jacobian matrices. It is now well known that the estimation of Jacobian matrices can be posed as a graph coloring problem. Unidirectional coloring by Coleman and More [9] and bidirectional coloring independently proposed by Hossain and Steihaug [23] and Coleman and Verma [12] are techniques that employ graph theoretic ideas. In this thesis we present heuristic and exact bidirectional coloring techniques. For bidirectional heuristic techniques we have implemented variants of largest first ordering, smallest last ordering, and incidence degree ordering schemes followed by the sequential algorithm to determine the Jacobian matrices. A "good" lower bound given by the maximum number of nonzero entries in any row of the Jacobian matrix is readily obtained in an unidirectional determination. However, in a bidirectional determination no such "good" lower bound is known. A significant goal of this thesis is to ascertain the effectiveness of the existing heuristic techniques in terms of the number of matrix-vector products required to determine the Jacobian matrix. For exact bidirectional techniques we have proposed an integer linear program to solve the bidirectional coloring problem. Part of exact bidirectional coloring results were presented at the "Second International Workshop on Cominatorial Scientific Computing (CSC05), Toulouse, France."

Degree

thesis:*
Level thesis:degree_level
Masters
Grantor dc:publisher
Lethbridge, Alta. : University of Lethbridge, Faculty of Arts and Science, 2005
Year dc:date.issued
2005

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Goyal, Mini
  • 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/260

Chain of custody

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

Goyal, Mini; University of Lethbridge. Faculty of Arts and Science. Graph coloring in sparse derivative matrix computation. Masters thesis, Lethbridge, Alta. : University of Lethbridge, Faculty of Arts and Science, 2005, 2005. https://hdl.handle.net/10133/260