New interface

# 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 :
Document type :
Reports
Domain :

Cited literature [1 references]

https://hal.inria.fr/inria-00073896
Contributor : Rapport De Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 2:01:23 PM
Last modification on : Friday, February 4, 2022 - 3:16:09 AM
Long-term archiving on: : Monday, April 5, 2010 - 12:01:07 AM

### Identifiers

• 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⟩

Record views