On the Estimation of Sparse Hessian Matrices

This paper studies automatic procedures for estimating second derivatives of a real valued function of several variables. The estimates are obtained from differences in first derivative vectors, and it is supposed that the required matrix is sparse and that its sparsity structure is known. Our main purpose is to find ways of taking advantage of the sparsity structure and the symmetry of the second derivative matrix, in order to make small the number of first derivative vectors that have to be calculated. Two new algorithms are proposed, which seem to be very successful in practice and which do not require much computer arithmetic. One is a direct method and the other is a substitution method, these terms being explained in the paper. Some examples show, however, that the given methods may not minimize the number of first derivative vector calculations.