Branch Detection and Sparsity Estimation in Matlab
Marina Menshikova and Shaun Forth
Presented at
6th European Workshop on Automatic Differentiation, Nov 15-16 2007, INRIA Sophia-Antipolis, France
Abstract
Some computations performed by automatic differentiation can be
performed more effectively if we can be assured that the control flow of
the program does not change from one call of the program to the next.
This is the case with: uncertainty estimation via Taylor series,
Jacobian sparsity estimation, or reverse mode AD implemented via taping.
We present an overloaded branch detection algorithm for the MAD package
for AD in Matlab that enables one to automatically check whether any
relational operators are evaluated and/or whether their evaluation
changes from one call of the program to the next. In the absence of the
control-flow analysis facilitated by source-transformation, detection of
relational operators is taken to indicate the presence of a branch in
the program and hence potential changes in control flow. We further
present a sparsity detection class for MAD which gives tight
overestimates of Jacobian sparsity patterns even in the presence of
program computations involving sparse matrices. The sparsity patterns
may then be used for Jacobian compression.
Download
PDF: mmsaf_euroadinria07.pdf
