Publication: Achieving Logarithmic Growth of Temporal and Spatial Complexity in Reverse Automatic Differentiation
Introduction
Applications
Tools
Research Groups
Workshops
Publications
   List Publications
   Advanced Search
   Info
   Add Publications
My Account
About

Achieving Logarithmic Growth of Temporal and Spatial Complexity in Reverse Automatic Differentiation

- Article in a journal -
 

Author(s)
Andreas Griewank

Published in
Optimization Methods and Software

Year
1992

Abstract
In its basic form the reverse mode of automatic differentiation yields gradient vectors at a small multiple of the computational work needed to evaluate the underlying scalar function. The practical applicability of this temporal complexity result, due originally to Linnainmaa, seemed to be severely limited by the fact that the memory requirement of the basic implementation is proportional to the run time T, of the original evaluation program. It is shown here that, by a recursive scheme related to the multilevel differentiation approach of Volin and Ostrovskii, the growth in both temporal and spatial complexity can be limited to a fixed multiple of log(T). Other compromises between the run time and memory requirement are possible, so that the reverse mode becomes applicable to computational problems of virtually any size.

AD Theory and Techniques
Adjoint, Checkpointing, Data Flow Analysis, General, Introduction, Reverse Mode

BibTeX
@ARTICLE{
         Griewank1992ALG,
       ad_theotech = "Adjoint, Checkpointing, Data Flow Analysis, General, Introduction, Reverse
         Mode",
       author = "Andreas Griewank",
       journal = "Optimization Methods and Software",
       pages = "35--54",
       title = "Achieving Logarithmic Growth of Temporal and Spatial Complexity in Reverse Automatic
         Differentiation",
       volume = "1",
       year = "1992",
       abstract = "In its basic form the reverse mode of automatic differentiation yields gradient
         vectors at a small multiple of the computational work needed to evaluate the underlying scalar
         function. The practical applicability of this temporal complexity result, due originally to
         Linnainmaa, seemed to be severely limited by the fact that the memory requirement of the basic
         implementation is proportional to the run time $T$, of the original evaluation program. It is shown
         here that, by a recursive scheme related to the multilevel differentiation approach of Volin and
         Ostrovskii, the growth in both temporal and spatial complexity can be limited to a fixed multiple of
         $\log(T)$. Other compromises between the run time and memory requirement are possible, so that
         the reverse mode becomes applicable to computational problems of virtually any size."
}


back
  

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