Publication: Optimal Time and Minimum Space-Time Product for Reversing a Certain Class of Programs
Introduction
Applications
Tools
Research Groups
Workshops
Publications
   List Publications
   Advanced Search
   Info
   Add Publications
My Account
About

Optimal Time and Minimum Space-Time Product for Reversing a Certain Class of Programs

- incollection -
 

Author(s)
JosÚ Grimm , Lo´c Pottier , Nicole Rostaing-Schmidt

Published in
Computational Differentiation: Techniques, Applications, and Tools

Editor(s)
Martin Berz, Christian H. Bischof, George F. Corliss, Andreas Griewank

Year
1996

Publisher
SIAM

Abstract
This paper concerns space-time trade-offs for the reverse mode of automatic differentiation on the straight-line programs with nested loops. In the first part we consider the problem of reversing a finite sequence given by un+1=f(un), which can model a certain class of finite loops. We show an optimal time strategy for this problem, the number of available registers being fixed, and a lower bound on the space-time product equal to (p (ln p)2) ⁄ ((ln 4)2). We then present an optimal strategy on nested loops with the objective of preserving the program structure. Finally, we consider an application of this storage/recomputation strategy to compute in reverse mode the derivatives of a function represented as a Fortran program.

Cross-References
Berz1996CDT

BibTeX
@INCOLLECTION{
         Grimm1996OTa,
       author = "Jos{\'e} Grimm and Lo{\"{\i}}c Pottier and Nicole
         Rostaing-Schmidt",
       editor = "Martin Berz and Christian H. Bischof and George F. Corliss and Andreas Griewank",
       title = "Optimal Time and Minimum Space-Time Product for Reversing a Certain Class of
         Programs",
       booktitle = "Computational Differentiation: Techniques, Applications, and Tools",
       pages = "95--106",
       publisher = "SIAM",
       address = "Philadelphia, PA",
       key = "Grimm1996OTa",
       crossref = "Berz1996CDT",
       abstract = "This paper concerns space-time trade-offs for the reverse mode of automatic
         differentiation on the straight-line programs with nested loops. In the first part we consider the
         problem of reversing a finite sequence given by $u_{n+1}=f(u_{n})$, which can model a certain class
         of finite loops. We show an optimal time strategy for this problem, the number of available
         registers being fixed, and a lower bound on the space-time product equal to $\frac{p (\ln
         p)^{2}}{(\ln 4)^{2}}$. We then present an optimal strategy on nested loops with the objective
         of preserving the program structure. Finally, we consider an application of this
         storage/recomputation strategy to compute in reverse mode the derivatives of a function represented
         as a Fortran program.",
       keywords = "Space-time trade-off, optimal time strategy, nested loops, lower bound on
         space-time product, Odyss\'ee.",
       referred = "[Klein2002DMf], [Mohammadi1996ADi], [Soulie2002EPR].",
       year = "1996"
}


back
  

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