Detecting Jacobian Sparsity Patterns by Bayesian Probing
Prof. Dr. Andreas Griewank
March 19, 2001, 9 a.m. BA 9911We 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.
