BibTeX
@INCOLLECTION{
Grimm1996OTa,
author = "Jos{\'e} Grimm and Lo{\"{\i}}c Pottier and Nicole
RostaingSchmidt",
editor = "Martin Berz and Christian H. Bischof and George F. Corliss and Andreas Griewank",
title = "Optimal Time and Minimum SpaceTime Product for Reversing a Certain Class of
Programs",
booktitle = "Computational Differentiation: Techniques, Applications, and Tools",
pages = "95106",
publisher = "SIAM",
address = "Philadelphia, PA",
key = "Grimm1996OTa",
crossref = "Berz1996CDT",
abstract = "This paper concerns spacetime tradeoffs for the reverse mode of automatic
differentiation on the straightline 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 spacetime 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 = "Spacetime tradeoff, optimal time strategy, nested loops, lower bound on
spacetime product, Odyss\'ee.",
referred = "[Klein2002DMf], [Mohammadi1996ADi], [Soulie2002EPR].",
year = "1996"
}
