Combinatorial optimization of stencil-based Jacobian computations.

Abstract

The computation of all nonzero entries of a sparse Jacobian matrix using either divided differencing or the forward mode of automatic differentiation is considered. Throughout this article, we assume that the sparsity of the Jacobian stems from a stencil-based computation of the underlying function which is typical for numerical applications in computational science and engineering involving partial differential equations. The minimization of the time needed to compute all nonzero Jacobian entries is formulated as a combinatorial optimization problem. We present three different, yet equivalent, representations of that problem and discuss each of its advantages and disadvantages. Broadly speaking, the three representations belong to the areas of linear algebra, grid discretization, and graph theory.