Skip to Main content Skip to Navigation
Reports

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

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.
Document type :
Reports
Complete list of metadatas

Cited literature [1 references]  Display  Hide  Download

https://hal.inria.fr/inria-00073896
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 2:01:23 PM
Last modification on : Monday, April 27, 2020 - 10:10:05 PM
Long-term archiving on: : Monday, April 5, 2010 - 12:01:07 AM

Identifiers

  • HAL Id : inria-00073896, version 1

Collections

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⟩

Share

Metrics

Record views

228

Files downloads

768