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.abstractWe 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 × 10Rights
- Language dc:language.iso
- en
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- https://hdl.handle.net/10133/7279