Improved implementation of some coloring algorithms for the determination of large and sparse Jacobian matrices

Simple item page
dc.contributor.authorKhan, Ahamad Imtiaz
dc.contributor.authorUniversity of Lethbridge. Faculty of Arts and Science
dc.contributor.supervisorHossain, Shahadat
dc.date.accessioned2017-11-08T17:22:16Z
dc.date.available2017-11-08T17:22:16Z
dc.date.issued2017
dc.degree.levelMastersen_US
dc.description.abstractWhen 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.embargoNoen_US
dc.identifier.urihttps://hdl.handle.net/10133/4978
dc.language.isoen_USen_US
dc.proquest.subject0984en_US
dc.proquestyesYesen_US
dc.publisherLethbridge, Alta. : Universtiy of Lethbridge, Department of Mathematics and Computer Scienceen_US
dc.publisher.departmentDepartment of Mathematics and Computer Scienceen_US
dc.publisher.facultyArts and Scienceen_US
dc.relation.ispartofseriesThesis (University of Lethbridge. Faculty of Arts and Science)en_US
dc.subjectbucket heap data structureen_US
dc.subjectheuristic algorithmsen_US
dc.subjectJacobian matricesen_US
dc.subjectoptimal coloringen_US
dc.subjectsparse data structuresen_US
dc.subjecttie-breaking strategiesen_US
dc.titleImproved implementation of some coloring algorithms for the determination of large and sparse Jacobian matricesen_US
dc.typeThesisen_US
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
KHAN_AHAMAD_MSC_2017.pdf
Size:
355.6 KB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
3.25 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Arts and Science, Faculty of
University of Lethbridge Theses