inria-00073896, version 1
Optimal Time and Minimum Space-Time Product for Reversing a Certain Class of Programs
José Grimm 1Loïc PottierNicole Rostaing-Schmidt
N° RR-2794 (1996)
Résumé : This report concerns time/space trade-offs for the reverse mode of automatic differentiation on the straight-line programs with nested loops class of programs. In the first part we consider the problem of reversing a finite sequence given by $u_{n+1}=3Df(u_n)$, which can mode lize 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 time-space product equal to $\frac{p (\ln p)^2}{(\ln 4)^2}$. We then present an optimal strategy on nested loops with the objective of taking care of 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 {\sc fortran} program.
- 1 : SAFIR (INRIA Sophia Antipolis)
- INRIA
- Domaine : Informatique/Autre
- Mots-clés : AUTOMATIC DIFFERENTIATION / COMPLEXITY / FORTRAN
- Référence interne : RR-2794
- inria-00073896, version 1
- http://hal.inria.fr/inria-00073896
- oai:hal.inria.fr:inria-00073896
- Contributeur : Rapport De Recherche Inria
- Soumis le : Mercredi 24 Mai 2006, 14:01:23
- Dernière modification le : Mercredi 31 Mai 2006, 14:24:28