General Elimination Techniques for Cheap Jacobians
by
Uwe Naumann
University of Hertfordshire

Jacobian accumulation is widely considered as the process of eliminating all intermediate vertices from the linearised version of the computational graph CG. The combinatorial optimisation problem of determining an elimination sequence that minimises the number of scalar multiplications performed is conjectured to be NP-hard.

We will take the approach several steps further by looking at edge elimination sequences in CG and, more generally, at edge elimination sequences in the line graph of CG. With the help of a non-trivial example we will show that an optimal vertex elimination sequence does, in fact, not minimise the number of scalar multiplications required to accumulate the whole Jacobian.

As an outlook we will propose several methods for approximately solving the combinatorial optimisation problem, including heuristics as well as dynamic programming and simulated annealing techniques. Numerical results will be presented to support our approach. Run-time savings of factors of 3 and more become possible compared to standard AD techniques.

http://homepages.feis.herts.ac.uk/~comqun/AD2000/xcad2_abstr.ps

Date received: February 11, 2000