Determining Sparse Jacobian Matrices Using Two-Sided Compression: An Algorithm and Lower Bounds

We study the determination of large and sparse derivative matrices using row and column compression. This sparse matrix determination problem has rich combinatorial structure which must be exploited to effectively solve any reasonably sized problem. We present a new algorithm for computing a two-sided compression of a sparse matrix. We give new lower bounds on the number of matrix-vector products needed to determine the matrix. The effectiveness of our algorithm is demonstrated by numerical testing on a set of practical test instances drawn from the literature.