Exploiting Intermediate Sparsity in Computing Derivatives for a Leapfrog Scheme.




The leapfrog scheme is a commonly used second-order method for solving differential equations. If Z(t) denotes the state of a system at a particular time step t, this integration scheme computes the state at the next time step as Z(t+1) = H(Z(t), Z(t-1), W), where H is the nonlinear timestepping operator and W are parameters that are not time-dependent. In this note, we show how the associativity of the chain rule of differential calculus can be used to expose and exploit intermediate derivative sparsity arising from the typical localized nature of the operator H. We construct a computational harness that capitalizes on this structure while employing automatic differentiation tools to automatically generate the derivative code corresponding to the evaluation of one time step. Experimental results with a 2-D shallow water equations model on IBM RS6000 and Sun SPARCstations illustrate these issues.