Efficient Calculation of Sparse Jacobians

TitleEfficient Calculation of Sparse Jacobians
Publication TypeJournal Article
Year of Publication1999
AuthorsTolsma JE, Barton PI
JournalSIAM Journal on Scientific Computing
Keywordsautomatic differentiation, common subexpressions, Jacobian evaluation, subgraph reduction

This paper describes a new approach for efficient Jacobian calculation using automatic differentiation. This approach obviates the need for vector accumulation by reducing certain parts of the computational graph representing the system of equations, allowing the Jacobian to be accumulated through a series of scalar operations. The advantages of this new approach include low spatial complexity, the ability to adapt to available memory if resources are limited, the ability to efficiently handle linear equations in a convenient manner, and low computational complexity. In addition, this approach is particularly well suited for evaluations within an interpretive environment. The approach can be applied to both the forward and reverse modes of automatic differentiation.