Current versions:
 

For C: For Fortran:

revolve_c.tar revolve_f.tar

go to: Synopsis - Functionality - Extentions - Articles - Contact

For adjoint calculations, derivative computations using the reverse mode of automatic differentiation, optimal control by Newton's method, and similar purposes one may need to reverse the execution of a computer program. The simplest option is to record all data required onto a tape during one program evaluation. Subsequently, the tape is read backwards in order to compute the desired information. This basic approach employs usually massive amounts of storage.

Under the assumption that the evaluation procedure can be divided into l time steps the approach implemented in Revolve uses only a fixed and usually small amount of memory pads called checkpoints to store intermediate states. The data required is generated piecewise by restarting the evaluation repeatedly. Applying this checkpointing method the memory requirement can be reduced drastically in comparison to the basic approach.

The following code fragment shows a typcial application of Revolve:
 

Provided by the user:

• forward(y), forwardrec(y), init(bz,by), reverse(bz,by)
  already needed for the basic reversal approach
• store(y,ystor,check), restore(y,ystor,check)
  only required for the checkpointing approach

Short Description:
First some initializations have to be done, namely the specification of the very first state (= capo) and the final state (=fine). The variable check indicate the number of checkpoints currently used. At the beginning, check has to be -1. The number of available checkpoints is given by the variable snaps.

Subsequently the reversal of the time-stepping procedure is done within a do-while-loop. During each execution of the loop-body the call of Revolve causes the appropriate actions for achieving an time-optimal reversal for the given number of checkpoints. For that purpose, the user has to provide functions in order to perform one forward time step, i.e. one integration step (forward(y)), one forward step with recording of the data required for the reversal of that step (forwardrec(y)), and one reverse step (reverse(by,bz)) besides the initialization of the adjoint values
bz and by. These routines are also needed by the basic reversal approach, where all data required is stored into one big tape. Hence , one only has to code the routines store(y,ystor,check) and restore(y,ystor,check) in order to apply Revolve! Here the routine store(y,ystor,check) stores the state y into the checkpoint with the numer check and  the routine restore(y,ystor,check) copies the checkpoint with the number check into the state y.

• Michael Hinze and Andrea Walther:

An optimal memory-reduced procedure for calculating adjoints of the instationary Navier-Stokes equations.
Preprint MATH-NM-06-2002, TU Dresden. 2002.
 
• Andreas Griewank and Andrea Walther.

Revolve: An Implementation of checkpointing for the reverse or adjoint mode of differentiation.
ACM Transactions on Mathematical Software 26(1), pp. 19 - 45 (2000).
 
• Juan M. Restrepo, Gary K. Leaf, and Andreas Griewank :

Circumventing Storage Limitations in Variational Data Assimilation
SIAM J. Sci. Comput. 19, No.5, 1586-1605 (1998).

Andrea Walther
Institute of Scientific Computing
Technical University of Dresden
Mommsenstr. 13
01062 Dresden, Germany
phone: +49 (0)351 463 35018
FAX: +49 (0)351 463 37096

Prof. Andreas Griewank, Ph.D
DFG Research Center MATHEON
Institut für Mathematik Fakultät Mat.-Nat. II
Humboldt-Universität
Rudower Chaussee 25, Adlershof
Post: Unter den Linden 6, 10099 Berlin
phone: 49-30-2093 5820
FAX: 49-30-2093 5859

Institute homepage

  (Okt/06/2006)