Show simple item record

dc.contributor.supervisor Hossain, Shahadat
dc.contributor.author Khan, Ahamad Imtiaz
dc.contributor.author University of Lethbridge. Faculty of Arts and Science
dc.date.accessioned 2017-11-08T17:22:16Z
dc.date.available 2017-11-08T17:22:16Z
dc.date.issued 2017
dc.identifier.uri https://hdl.handle.net/10133/4978
dc.description.abstract When we solve a system of nonlinear equations or nonlinear least-squares problem by Newton's method or one of its many variants, the most computationally expensive operations per iteration are the evaluation of the Jacobian and solving the associated linear system. Many real-life problems are sparse and if we know the sparsity structure of the Jacobian in advance, great computational saving can be achieved. We revisit heuristic algorithms and sparse data structures used to determine sparse Jacobian matrices. We provide a new implementation of data structures and heuristics and analyze the performance of our implementation. We provide experimental evidence of the superiority of our bucket heap data structure in terms of locality of reference to data access. Additionally, an efficient implementation of a branch-and-bound type exact coloring algorithm with new tie-breaking strategies is provided. The results are supported by extensive numerical experiments with benchmarking instances from the literature. en_US
dc.language.iso en_US en_US
dc.publisher Lethbridge, Alta. : Universtiy of Lethbridge, Department of Mathematics and Computer Science en_US
dc.relation.ispartofseries Thesis (University of Lethbridge. Faculty of Arts and Science) en_US
dc.subject bucket heap data structure en_US
dc.subject heuristic algorithms en_US
dc.subject Jacobian matrices en_US
dc.subject optimal coloring en_US
dc.subject sparse data structures en_US
dc.subject tie-breaking strategies en_US
dc.title Improved implementation of some coloring algorithms for the determination of large and sparse Jacobian matrices en_US
dc.type Thesis en_US
dc.publisher.faculty Arts and Science en_US
dc.publisher.department Department of Mathematics and Computer Science en_US
dc.degree.level Masters en_US
dc.proquest.subject 0984 en_US
dc.proquestyes Yes en_US
dc.embargo No en_US


Files in this item

This item appears in the following Collection(s)

Show simple item record