Efficient computation of gradients and Jacobians by dynamic exploitation of sparsity in automatic differentiation

Automatic differentiation (AD) is a technique that augments computer codes with statements for the computation of derivatives. The computational workhorse of AD-generated codes for first-order derivatives is the linear combination of vectors. For many large-scale problems, the vectors involved in this operation are inherently sparse. If the underlying function is a partially separable one (e.g., if its Hessian is sparse), many of the intermediate gradient vectors computed by AD will also be sparse, even though the final gradient is likely to be dense. For large Jacobians computations, every intermediate derivative vector is usually at least as sparse as the least sparse row of the final Jacobian. In this paper, we show that dynamic exploitation of the sparsity inherent in derivative computation can result in dramatic gains in runtime and memory savings. For a set of gradient problems exhibiting implicit sparsity, we report on the runtime and memory requirements of computing the gradients with the ADIFOR (Automatic Differentiation of FORtran) tool, both with and without employing the SparsLinC (Sparse Linear Combinations) library, and show that SparsLinC can reduce runtime and memory costs by orders of magnitude. We also compute sparse Jacobians using the SparsLinC-based approach - in the process, automatically detecting the sparsity structure of the Jacobian - and show that these Jacobian results compare favorably with those of previous techniques that require a priori knowledge of the sparsity structure of the Jacobian.