Back to search

Lethbridge, Alta. : Universtiy of Lethbridge, Department of Mathematics and Computer Science

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

Abstract

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.

Degree

thesis:*
Level thesis:degree_level
Masters
Grantor dc:publisher
Lethbridge, Alta. : Universtiy of Lethbridge, Department of Mathematics and Computer Science
Year dc:date.issued
2017

Author and committee

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

Subjects

dc:subject × 6

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Identifier
hdl:10133/4978

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

Khan, Ahamad Imtiaz; University of Lethbridge. Faculty of Arts and Science. Improved implementation of some coloring algorithms for the determination of large and sparse Jacobian matrices. Masters thesis, Lethbridge, Alta. : Universtiy of Lethbridge, Department of Mathematics and Computer Science, 2017. https://hdl.handle.net/10133/4978