An inexact combinatorial model for maximizing the number of discovered nonzero entries.

Abstract

Given a large sparse Jacobian matrix with a known sparsity pattern and a positive integer p, we formulate the new combinatorial problem of maximizing the number of nonzero elements that can be discovered by forming p groups of linear combinations of columns of the matrix. This combinatorial problem is addressed by introducing a novel graph model that does not represent the underlying aspects exactly, but aims at capturing the main aspects of the situation. In an attempt to encode information on the number of discovered nonzeros, an edge-weighted column intersection graph is transformed into an edge-weighted and vertex-weighted column gain graph. This combinatorial model gives rise to heuristic algorithms which are compared by computational experiments using a set of matrices arising from different scientific disciplines.