BibTeX
@ARTICLE{
Griewank2003AJa,
abstract = "The chain rule  fundamental to any kind of analytical differentiation  can be
applied in various ways to computational graphs representing vector functions. These variants result
in different operations counts for the calculation of the corresponding Jacobian matrices. The
minimization of the number of arithmetic operations required for the calculation of the complete
Jacobian leads to a hard combinatorial optimization problem. We will describe an approach to the
solution of this problem that builds on the idea of optimizing chained matrix products using dynamic
programming techniques. Reductions by a factor of 3 and more are possible regarding the operations
count for the Jacobian accumulation. After discussing the mathematical basics of Automatic
Differentiation we will show how to compute Jacobians by chained sparse matrix products. These
matrix chains can be reordered, must be pruned, and are finally subject to a dynamic programming
algorithm to reduce the number of scalar multiplications performed.",
ad_theotech = "Code Optimization, General",
author = "Andreas Griewank and Uwe Naumann",
title = "Accumulating {J}acobians as Chained Sparse Matrix Products",
journal = "Math. Prog.",
number = "95",
volume = "3",
pages = "555571",
year = "2003",
doi = "10.1007/s1010700203297",
publisher = "Springer"
}
