Skip to Main content Skip to Navigation

Heuristics for Efficiently Calculating Jacobians by Edge Elimination in Computational Graphs

Uwe Naumann 1
1 TROPICS - Program transformations for scientific computing
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : The chain rule - fundamental for Automatic Differentiation (AD) - can be applied to computational graphs representing vector functions in arbitrary orders resulting in different operations counts for the calculation of their Jacobian matrices. Very few authors have looked at this interesting subject so far and there is no generally accepted terminology for dealing with these combinations of the forward and reverse modes of AD. The minimizati- on of the number of arithmetic operations required for the calculation of the complete Jacobian leads to a computationally hard combinatorial optimization problem. After an extensive introduction into the problem of computing Jacobians using a minimal number of arithmetic operations we will describe several heuristics for reducing the size the computational graph as well as for solving the edge elimination problem in computational graphs. We will discuss the ideas behind the heuristics and present some test results. Finally we will give an outlook on the role that edge eliminatio- n could play in the development of new AD tools.
Document type :
Complete list of metadata
Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 11:30:18 AM
Last modification on : Friday, February 4, 2022 - 3:16:13 AM
Long-term archiving on: : Sunday, April 4, 2010 - 11:30:07 PM


  • HAL Id : inria-00072979, version 1



Uwe Naumann. Heuristics for Efficiently Calculating Jacobians by Edge Elimination in Computational Graphs. RR-3690, INRIA. 1999. ⟨inria-00072979⟩



Record views


Files downloads