Efficient heuristics for the consecutive zeros problem in sparse Jacobian matrix determination
No Thumbnail Available
Date
2025
Authors
Talukdar, Md. Asif
University of Lethbridge. Faculty of Arts and Science
Journal Title
Journal ISSN
Volume Title
Publisher
Lethbridge, Alta. : University of Lethbridge, Dept. of Mathematics and Computer Science
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.
Description
Keywords
Consecutive zeros problem , Traveling salesperson problem , Ant colony optimization , Jacobian matrix determination , Greedy heuristics , Substitution method