We describe an automatic procedure for successively
reducing the set of possible nonzeros in a Jacobian matrix until
eventually the exact sparsity pattern is obtained. The dependence
information needed in this probing 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.
The proposed probing procedure is found to require only O (\log n)
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.