Differential Inversion of the Implicit Euler Method

Abstract. The implicit Euler method integrates systems of ordinary differential equations [Formula: see text] with differentiable right-hand side [Formula: see text] from an initial state [Formula: see text] to a target time [Formula: see text] as [Formula: see text]. Discretization of the time interval [Formula: see text] yields [Formula: see text] time steps. We present a method for efficiently computing the product of its inverse Jacobian [Formula: see text] with a given vector [Formula: see text]. We show that the differential inverse [Formula: see text] can be evaluated for given [Formula: see text] with a computational cost of [Formula: see text] as opposed to the widely used [Formula: see text] or, if applying Algorithmic Differentiation to [Formula: see text] naively, even [Formula: see text]. The theoretical results are supported by actual run times. A reference implementation is provided together with instructions on how to reproduce the main results of this paper. Reproducibility of computational results. This paper has been awarded the “SIAM Reproducibility Badge: Code and data available” as recognition that the authors have followed reproducibility principles valued by SISC and the scientific computing community. Code and data that allow readers to reproduce the results in this paper are available at https://github.com/un110076/DifferentialInversion and in the supplementary materials ( DifferentialInversion-main.zip [12.5KB]). [Formula: see text]