Accumulating Jacobians as chained sparse matrix products

Accumulating Jacobians as chained sparse matrix products

0.00 Avg rating0 Votes
Article ID: iaor20041177
Country: Germany
Volume: 95
Issue: 3
Start Page Number: 555
End Page Number: 571
Publication Date: Jan 2003
Journal: Mathematical Programming
Authors: ,
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.

Reviews

Required fields are marked *. Your email address will not be published.