Back to search

Lethbridge, Alta. : University of Lethbridge, Dept. of Mathematics and Computer Science

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

Abstract

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).

Degree

thesis:*
Level thesis:degree_level
Masters
Grantor dc:publisher
Lethbridge, Alta. : University of Lethbridge, Dept. of Mathematics and Computer Science
Year dc:date.issued
2015

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Saha, Anik
  • University of Lethbridge. Faculty of Arts and Science
Advisor dc:contributor.supervisor
  • Hossain, Shahadat

Subjects

dc:subject × 4

Rights

Language dc:language.iso
en_CA

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/10133/3760

Chain of custody

source
Harvested from
University of Lethbridge
Base URL
opus.uleth.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Saha, Anik; University of Lethbridge. Faculty of Arts and Science. Bi-directional determination of sparse Jacobian matrices : algorithms and lower bounds. Masters thesis, Lethbridge, Alta. : University of Lethbridge, Dept. of Mathematics and Computer Science, 2015. https://hdl.handle.net/10133/3760