Show simple item record

dc.contributor.supervisor Hossain, Shahadat
dc.contributor.author Saha, Anik
dc.contributor.author University of Lethbridge. Faculty of Arts and Science
dc.date.accessioned 2015-10-02T21:09:59Z
dc.date.available 2015-10-02T21:09:59Z
dc.date.issued 2015
dc.identifier.uri https://hdl.handle.net/10133/3760
dc.description.abstract Efficient 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.language.iso en_CA en_US
dc.publisher Lethbridge, Alta. : University of Lethbridge, Dept. of Mathematics and Computer Science en_US
dc.relation.ispartofseries Thesis (University of Lethbridge. Faculty of Arts and Science) en_US
dc.subject sparse matrix en_US
dc.subject Jacobian matrix en_US
dc.subject row and column compressions en_US
dc.subject bi-directional partitioning en_US
dc.title Bi-directional determination of sparse Jacobian matrices : algorithms and lower bounds 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 0405 en_US
dc.proquest.subject 0642 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