Optimal Time and Minimum Space-Time Product for Reversing a Certain Class of Programs
José Grimm, Loïc Pottier, Nicole Rostaing-Schmidt · 1996
: This paper concerns space-time trade-ooes for the reverse mode of au tomatic dioeerentiation on the straight-line programs with nested loops. In the rst part we consider the problem of reversing a nite sequence given by u n+1 = f(u n ), which can model a certain class of nite loops. We show an optimal time strategy for this problem, the number of available registers being xed, 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. Key-words: Automatic dioeerentiation, complexity, fortran (R#sum# : tsvp) La premi#re partie de ce travail a #t# pr#sent#e au colloque de complexit# alg#brique en m#moire de Jacques Morgenstern, # l'INRIA Sophia Antipolis, en mai 1995 Unite de recherche INRIA Sop...