Skip to Main content Skip to Navigation
Reports

Optimizing the Accumulation of Jacobians by Edge Elimination in the Computational Graph

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 dealt with this interesting subject so far and there is no generally accepted terminology for handling these combinations of the forward and reverse modes of AD. The minimization of the number of arithmetic operations required for the calculation of the complete Jacobian leads to a computationally hard combinatorial optimizati- on problem. In this paper we will give a formal description of this problem, which also is sometimes referred to as the cross-country elimination problem in computational graphs, in terms of a shortest path problem in the so-called metagraph. The well-known strategy of eliminating vertices will be refined by introducing the elimination of edges. We will show that edge elimination is in general superior to vertex elimination with respect to the operations count. As an outlook we will present a selection of methods for solving the general edge elimination problem heuristically
Document type :
Reports
Complete list of metadatas

https://hal.inria.fr/inria-00073013
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 11:35:28 AM
Last modification on : Saturday, January 27, 2018 - 1:31:03 AM
Long-term archiving on: : Sunday, April 4, 2010 - 9:36:14 PM

Identifiers

  • HAL Id : inria-00073013, version 1

Collections

Citation

Uwe Naumann. Optimizing the Accumulation of Jacobians by Edge Elimination in the Computational Graph. RR-3659, INRIA. 1999. ⟨inria-00073013⟩

Share

Metrics

Record views

136

Files downloads

262