Institutional Repository

Graph coloring in sparse derivative matrix computation

DSpace/Manakin Repository

Show simple item record

dc.contributor.advisor Hossain, Shadadat
dc.contributor.author Goyal, Mini
dc.contributor.author University of Lethbridge. Faculty of Arts and Science
dc.date.accessioned 2007-05-17T14:49:10Z
dc.date.available 2007-05-17T14:49:10Z
dc.date.issued 2005
dc.identifier.uri http://hdl.handle.net/10133/260
dc.description viii, 83 leaves ; 29 cm. en
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." en
dc.language.iso en_US en
dc.publisher Lethbridge, Alta. : University of Lethbridge, Faculty of Arts and Science, 2005 en
dc.relation.ispartofseries Thesis (University of Lethbridge. Faculty of Arts and Science) en
dc.subject Graph coloring en
dc.subject Jacobians en
dc.subject Matrices en
dc.subject Dissertations, Academic en
dc.title Graph coloring in sparse derivative matrix computation en
dc.type Thesis en
dc.publisher.faculty Arts and Science
dc.publisher.department Department of Mathematics and Computer Science

Files in this item

This item appears in the following Collection(s)

Show simple item record

Related Items

Search DSpace


Advanced Search

Browse

My Account

Statistics