Estimation of Sparse Jacobian Matrices and Graph Coloring Blems

Given a mapping with a sparse Jacobian matrix, we investigate the problem of minimizing the number of function evaluations needed to estimate the Jacobian matrix by differences. We show that this problem can be attacked as a graph coloring problem and that this approach leads to very efficient algorithms. The behavior of these algorithms is studied and, in particular, we prove that two of the algorithms are optimal for band graphs. We also present numerical evidence which indicates that these two algorithms are nearly optimal on practical problems.