Estimation of Sparse Jacobian Matrices

Abstract

When finding a numerical solution to a system of nonlinear equations, one often estimates the Jacobian by finite differences. Curtis, Powell and Reid [J. Inst. Math. Applics.,13 (1974), pp. 117–119] presented an algorithm that reduces the number of function evaluations required to estimate the Jacobian by taking advantage of sparsity. We show that the problem of finding the best of the Curtis, Powell and Reid type algorithms is NP-complete, and then propose two procedures for estimating the Jacobian that may use fewer function evaluations.