Publication: Automatic Differentiation: A Structure-Exploiting Forward Mode with Almost Optimal Complexity for Kantorovic Trees
Introduction
Applications
Tools
Research Groups
Workshops
Publications
   List Publications
   Advanced Search
   Info
   Add Publications
My Account
About

Automatic Differentiation: A Structure-Exploiting Forward Mode with Almost Optimal Complexity for Kantorovic Trees

- incollection -
 

Author(s)
Michael Ulbrich , Stefan Ulbrich

Published in
Applied Mathematics and Parallel Computing, Festschrift for Klaus Ritter

Editor(s)
Herbert C. Fischer, B. Riedmüller, S. Schäffler

Year
1996

Publisher
Physica-Verlag

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.

BibTeX
@INCOLLECTION{
         Ulbrich1996ADA,
       author = "Michael Ulbrich and Stefan Ulbrich",
       title = "Automatic Differentiation: A Structure-Exploiting Forward Mode with Almost Optimal
         Complexity for {K}antorovic Trees",
       booktitle = "Applied Mathematics and Parallel Computing, Festschrift for Klaus Ritter",
       year = "1996",
       editor = "Herbert C. Fischer and B. Riedm{\"u}ller and S. Sch{\"a}ffler",
       publisher = "Physica-Verlag",
       address = "Berlin",
       pages = "327--357",
       keywords = "Automatic differentiation, characterizing sequence, code list, forward mode,
         reverse mode, Kantorovic graph, Kantorovic tree, time complexity, parallelization.",
       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."
}


back
  

Contact:
autodiff.org
Username:
Password:
(lost password)