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",
       ad_theotech = "Checkpointing"
}