Bi-directional determination of sparse Jacobian matrices : algorithms and lower bounds

Simple item page
dc.contributor.authorSaha, Anik
dc.contributor.authorUniversity of Lethbridge. Faculty of Arts and Science
dc.contributor.supervisorHossain, Shahadat
dc.date.accessioned2015-10-02T21:09:59Z
dc.date.available2015-10-02T21:09:59Z
dc.date.issued2015
dc.degree.levelMastersen_US
dc.description.abstractEfficient estimation of large sparse Jacobian matrices is a requisite in many large-scale scientific and engineering problems. It is known that estimation of non-zeroes of a matrix can be viewed as a graph coloring problem. Due to the presence of dense rows or dense columns, unidirectional partitioning does not always give good results. Bi-Directional partitioning handles the problem of dense rows and dense columns quite well[16]. Lower bound to determine the non-zeroes of a sparse Jacobian matrix can be defined as the least number of groups necessary to determine the matrix. For unidirectional partitioning, a good lower bound is given by the maximum number of non-zeroes in any row[4]. For bi-directional determination, both columns and rows must be considered to obtain a lower bound. In this thesis, we provide an easily computed better lower bound. We have developed a heuristic algorithm and an iterative algorithm to determine non-zeroes of sparse Jacobian matrices using Bi-Directional partitioning. Our heuristic algorithm is inspired from graph coloring problems and recursive largest first partitioning of graphs. Our algorithm provides a better result than the existing algorithms. For the iterative method, we have introduced randomization technique to color the vertices of the graph. A part of our work was presented at "Applied Mathematics, Modelling and Computational Science" (AMMCS-2015).en_US
dc.embargoNoen_US
dc.identifier.urihttps://hdl.handle.net/10133/3760
dc.language.isoen_CAen_US
dc.proquest.subject0405en_US
dc.proquest.subject0642en_US
dc.proquestyesYesen_US
dc.publisherLethbridge, Alta. : University of Lethbridge, Dept. 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.subjectsparse matrixen_US
dc.subjectJacobian matrixen_US
dc.subjectrow and column compressionsen_US
dc.subjectbi-directional partitioningen_US
dc.titleBi-directional determination of sparse Jacobian matrices : algorithms and lower boundsen_US
dc.typeThesisen_US
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Saha_Anik_MSc_2015.pdf
Size:
449.96 KB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
1.71 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Arts and Science, Faculty of
University of Lethbridge Theses