Estimation of Sparse Jacobian Matrices and Graph Coloring Problems

摘要

Given a mapping with a sparse Jacobian matrix, the problem of minimizing the number of function evaluations needed to estimate the Jacobian matrix by differences is investigated. This problem can be attacked as a graph coloring problem and this approach leads to very efficient algorithms. The behavior of these algorithms is studied and, in particular, it is proved that two of the algorithms are optimal for band graphs. Numerical evidence is presented which indicates that these two algorithms are nearly optimal on practical problems. (ERA citation 06:029581)