Probing for Jacobian Sparsity
by
Andreas Griewank
Institute of Scientific Computing, technical Univesity Dresden
Coauthors: Chisto Mitev,

Institute of Scientific Computing Andreas Griewank Christo Mitev

Dresden, January 2000

Abstract
Many numerical methods require the evaluation of Jacobians for vector functions given as evaluation procedures. If known, the sparsity pattern of these first derivative matrices can be used to evaluate, store, and manipulate them more efficiently [, , , , ]. Especially on discretizations of differential equations and other large scale problems, detecting and specifying the pattern of potentially nonzero entries may be a laborious and error prone task.

In this paper we describe an automatic procedure for successively reducing the set of possible nonzeros until eventually the exact sparsity pattern is obtained if this is desired. The dependence information needed in this process consist of 'structural' Jacobian-vector products and possibly also vector-Jacobian products, which can be evaluated exactly by automatic differentiation or approximated by divided differences. The latter approach yields correct sparsity patterns provided there is no exact cancellation at the current argument vector.

Starting from a user specified (or by default initialised) prior probability distribution the procedure suggests a sequence of probing vectors. The resulting information is then used to update the probabilities that certain elements are nonzero according to Bayes' law. For use in the context of automatic differentiation bundles of 32 probing directions are generated that can be propagated as bit patterns forward or backward through the evaluation procedure of the underlying vector function. In this way one obtains 32 structural Jacobian-vector or vector-Jacobian products at an expense that is comparable to a single directional derivative evaluation.

The proposed probing procedure is found to require only O(logn) probing vectors on banded square matrices of dimension n and still a lot less than the trivial bound n on randomly generated matrices with a fixed average number of nonzeros per row and column. In 'validation' mode, i.e. with correct prior distribution of nonzeros, the procedure reduces to a heuristic scheme for finding a scheme to successively compute all nonzero Jacobian entries on the basis of 'numerical' Jacobian-vector and possibly also vector-Jacobian products.

References

[]

A.R. Curtis, M.J.D. Powell, and J.K. Reid, On the estimation of sparse Jacobian matrices, J. Inst. Math. Appl. 13 (1974), 117-119.

[]

G. N. Newsam and J. D. Ramsdell, Estimation of sparse Jacobian matrices, SIAM J. Algebraic Discrete Methods 4 (1983), 404-417.

[]

T.F. Coleman and J.J. Moré, Estimation of sparse Jacobian matrices and graph coloring problems, SIAM J. Numer. Anal. 20 (1984), 187-209.

[]

U. Geitner, Automatische Berechnung von dünnbesetzten Jacobimatrizen nach dem Ansatz von Newsam-Ramsdell, diploma thesis, Technical University Dresden, Germany, 1995.

[]

C.H. Bischof, A. Bouaricha, P.M. Khademi, and J.J. Moré, Computing gradients in large-scale optimization using automatic differentiation, INFORMS J. Comput. 9 (1997), 185-194.

Date received: January 17, 2000

Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cads-45.