Publication: Accumulating Jacobians as Chained Sparse Matrix Products
Introduction
Applications
Tools
Research Groups
Workshops
Publications
   List Publications
   Advanced Search
   Info
   Add Publications
My Account
About

Accumulating Jacobians as Chained Sparse Matrix Products

- Article in a journal -
 

Author(s)
Andreas Griewank , Uwe Naumann

Published in
Math. Prog.

Year
2003

Publisher
Springer

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 Theory and Techniques
Code Optimization, General

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 = "555--571",
       year = "2003",
       doi = "10.1007/s10107-002-0329-7",
       publisher = "Springer"
}


back
  

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