Publication: Verifying Jacobian Sparsity
Introduction
Applications
Tools
Research Groups
Workshops
Publications
   List Publications
   Advanced Search
   Info
   Add Publications
My Account
About

Verifying Jacobian Sparsity

- incollection -
 

Author(s)
Andreas Griewank , Christo Mitev

Published in
Automatic Differentiation of Algorithms: From Simulation to Optimization

Editor(s)
George Corliss, Christèle Faure, Andreas Griewank, Laurent Hascoët, Uwe Naumann

Year
2002

Publisher
Springer

Abstract
In a recent paper [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×n matrices with h superdiagonals it is shown that the greedy heuristics developed in [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.

Cross-References
Corliss2002ADo

AD Theory and Techniques
Sparsity

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"
}


back
  

Contact:
autodiff.org
Username:
Password:
(lost password)