Back to search

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

Efficient heuristics for the consecutive zeros problem in sparse Jacobian matrix determination

Abstract

dc:description.abstract

We study the Consecutive Zeros Problem (CZP), which is an extension of the well-known maximum consecutive ones problem. CZP is interesting both from a combinatorial and a practical standpoint. Leveraging a priori known sparsity pattern of matrix A, we employ a state-of-the-art coloring/column partitioning algorithm to generate a seed matrix S, to obtain the compressed matrix B = A × S, using automatic differentiation (AD) or finite differences (FD) while significantly reducing the problem’s dimensionality. With the AD forward mode, the nonzero entries of A are mapped to the compressed matrix accurately up to the machine precision using Cn “forward passes”. This research aims to reduce the computation cost ( measured by the number of AD passes required to compress the matrix) further by solving the CZP (grouping the zeros in each row of B). The problem is cast as a variant of the Traveling Salesperson Problem (TSP). To solve the problem, we have designed and implemented heuristic algorithms, including Ant Colony Optimization (ACO) meta-heuristic and two variants of ACO (Zp-Hybrid and Zp-Estimator), and several greedy heuristics (Exhaustive Approach, Selective Exhaustive, and Single Attempt). The computational results from a subset of benchmark test matrices clearly demonstrate the effectiveness of the proposed approaches.

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
2025

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Talukdar, Md. Asif
  • University of Lethbridge. Faculty of Arts and Science
Advisors dc:contributor.supervisor
  • Hossain, Shahadat
  • Benkoczi, Robert

Subjects

dc:subject × 10

Rights

Language dc:language.iso
en

Identifiers

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

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

Talukdar, Md. Asif; University of Lethbridge. Faculty of Arts and Science. Efficient heuristics for the consecutive zeros problem in sparse Jacobian matrix determination. Masters thesis, Lethbridge, Alta. : University of Lethbridge, Dept. of Mathematics and Computer Science, 2025. https://hdl.handle.net/10133/7279