TU Darmstadt
| Home      | FB 4      | TU Darmstadt 
Research
Discrete Optimization
Nonlinear Optimization
   About us
   Members
   Events
   Secretary's Office
Global Optimization
Discrete Geometry
Algorithmic Discrete Mathematics
Staff members
Projects
Jobs and Scholarships
Events
Previous Seminars
Publications
Contact
How to find us
Imprint
Technical Report Nr. IAMS1996.1

Institut für Angewandte Mathematik und Statistik

Technische Universität München

Technical Report Nr. IAMS1996.1





Automatic Differentiation:

A Structure-Exploiting Forward Mode with

Almost Optimal Complexity for Kantorovic Trees



Michael Ulbrich and Stefan Ulbrich



January 1996



Abstract:

A structure-exploiting forward mode is discussed that achieves almost optimal complexity for functions given by Kantorovic trees. It is based on approriate representations of the gradient and the Hessian. After a brief exposition of the forward and reverse mode of automatic differentiation for derivatives up to second order and compact proofs of their complexities, the new forward mode is presented and analyzed. It is shown that in the case of functions f: R^n -> R with a tree as Kantorovic graph the algorithm is only O(ln(n)) times as expensive as the reverse mode. Except for the fact that the new method is a very efficient implementation of the forward mode, it can be used to significantly reduce the length of characterizing sequences before applying the memory expensive reverse mode. For the Hessian all discussed algorithms are shown to be efficiently parallelizable. Some numerical examples confirm the advantages of the new forward mode.


Keywords:

automatic differentiation, characterizing sequence, code list, forward mode, reverse mode, Kantorovic graph, Kantorovic tree, time complexity, parallelization.


this Report as compressed Postscript file (100k).
Michael Ulbrich , 1996-05-21