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

1 SAFIR - Algebraic Formal Systems for Industry and Research
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : 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.
Keywords :
Type de document :
Rapport
RR-2794, INRIA. 1996
Domaine :
Liste complète des métadonnées

Littérature citée [1 références]

https://hal.inria.fr/inria-00073896
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 14:01:23
Dernière modification le : samedi 27 janvier 2018 - 01:31:29
Document(s) archivé(s) le : lundi 5 avril 2010 - 00:01:07

### Identifiants

• HAL Id : inria-00073896, version 1

### Citation

José Grimm, Loïc Pottier, Nicole Rostaing-Schmidt. Optimal Time and Minimum Space-Time Product for Reversing a Certain Class of Programs. RR-2794, INRIA. 1996. 〈inria-00073896〉

### Métriques

Consultations de la notice

## 169

Téléchargements de fichiers