Skip to Main content Skip to Navigation
Reports

SAVE - Simulated Annealing Applied to the Vertex Elimination Problem 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. In this paper we will describe a new heuristic approach to the solution of the vertex elimination problem in computational graphs which can easily adapted to the more general case of eliminating edges. Simulated annealing is widely regarded as a suitable method for solving combinatorial optimization problems. We will discuss different annealing schedules and present some test results. Finally we will regard this approach in comparison with other methods for computing Jacobians using a minimal number of arithmetic operations.
Document type :
Reports
Complete list of metadatas

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

Identifiers

  • HAL Id : inria-00073012, version 1

Collections

Citation

Uwe Naumann. SAVE - Simulated Annealing Applied to the Vertex Elimination Problem in Computational Graphs. RR-3660, INRIA. 1999. ⟨inria-00073012⟩

Share

Metrics

Record views

126

Files downloads

167