Algorithm 799: revolve

TLDR

Reverse-mode automatic differentiation computes gradients at a cost only slightly higher than evaluating the function, but its memory usage scales with runtime, limiting practical use. The authors aim to develop checkpointing schedules that reduce storage requirements for reverse-mode AD. They present revolve, a routine that generates provably optimal checkpointing schedules and serves as an explicit controller for time‑dependent applications.

Abstract

In its basic form, the reverse mode of computational differentiation yields the gradient of a scalar-valued function at a cost that is a small multiple of the computational work needed to evaluate the function itself. However, the corresponding memory requirement is proportional to the run-time of the evaluation program. Therefore, the practical applicability of the reverse mode in its original formulation is limited despite the availability of ever larger memory systems. This observation leads to the development of checkpointing schedules to reduce the storage requirements. This article presents the function revolve, which generates checkpointing schedules that are provably optimal with regard to a primary and a secondary criterion. This routine is intended to be used as an explicit “controller” for running a time-dependent applications program.