BibTeX
@INCOLLECTION{
         Griewank2002VJS,
       author = "Andreas Griewank and Christo Mitev",
       title = "Verifying Jacobian Sparsity",
       pages = "271--279",
       chapter = "32",
       crossref = "Corliss2002ADo",
       booktitle = "Automatic Differentiation of Algorithms: From Simulation to Optimization",
       year = "2002",
       editor = "George Corliss and Christ{\`e}le Faure and Andreas Griewank and Laurent
         Hasco{\"e}t and Uwe Naumann",
       series = "Computer and Information Science",
       publisher = "Springer",
       address = "New York, NY",
       abstract = "In a recent paper~\cite{Griewank2002DJS} 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
         consists of ``Boolean products'' Jacobian-vector products and vector-Jacobian products,
         which can be evaluated by propagating Boolean variables forward or backward through the function
         evaluation procedure. Starting from a user specified (or by default initialized) prior probability
         distribution, the procedure suggests a sequence of probing vectors. The resulting information is
         then used according to Bayes' law to update the probabilities that certain elements are
         nonzero. We analyze the special situation where the sparsity pattern is provided as a guess and
         merely needs to be verified with a small number of probes. For banded $n \times n$ matrices
         with $h$ superdiagonals it is shown that the greedy heuristics developed
         in~\cite{Griewank2002DJS} requires in verification mode only $O(h +\log_2 n)$ probes. Our
         numerical results indicate that this is still true if nothing is known a priori about the sparsity
         pattern.",
       ad_theotech = "Sparsity"
}