Skip to Main content Skip to Navigation

Periodicity is Optimal for Offline and Online Multi-Stage Adjoint Computations

Abstract : We reexamine the work of Aupy et al. on optimal algorithms for multi-stage adjoint computations, where two levels of memories are available. Previous optimal algorithm had a quadratic execution time. Here, with structural arguments, namely periodicity, on the optimal solution, we provide an optimal algorithm in constant time, with appropriate pre-processing. We also provide an asymptotically optimal algorithm for the online problem, when the adjoint graph size is not known before-hand. Again, this algorithms rely on the proof that the optimal solution for multi-stage adjoint computations is weakly periodic. We conjecture a closed-form formula for the period. Finally, we experimentally access the convergence speed of the approximation ratio for the online problem, through simulations.
Complete list of metadatas
Contributor : Julien Herrmann <>
Submitted on : Wednesday, December 16, 2015 - 11:50:36 PM
Last modification on : Thursday, November 21, 2019 - 1:42:09 AM
Long-term archiving on: : Thursday, March 17, 2016 - 11:01:23 AM


Files produced by the author(s)


  • HAL Id : hal-01244584, version 1



Guillaume Aupy, Julien Herrmann. Periodicity is Optimal for Offline and Online Multi-Stage Adjoint Computations. [Research Report] RR-8822, INRIA Grenoble - Rhône-Alpes. 2015. ⟨hal-01244584⟩



Record views


Files downloads