Graph Coloring in the Estimation of Sparse Derivative Matrices: Instances and Applications

We describe a graph coloring problem associated with the determination of mathematical derivatives. The coloring instances are obtained as intersection graphs of row partitioned sparse derivative matrices. The size of the graph is dependent on the partition and can be varied between the number of columns and the number of nonzero entries. If solved exactly … Read more

Optimal Direct Determination of Sparse Jacobian Matrices

It is well known that a sparse Jacobian matrix can be determined with fewer function evaluations or automatic differentiation \emph{passes} than the number of independent variables of the underlying function. In this paper we show that by grouping together rows into blocks one can reduce this number further. We propose a graph coloring technique for … Read more

Sparsity issues in the computation of Jacobian Matrices

The knowledge of sparsity information plays an important role in efficient determination of sparse Jacobian matrices. In a recent work, we have proposed sparsity-exploiting substitution techniques to determine Jacobian matrices. In this paper, we take a closer look at the underlying combinatorial problem. We propose a column ordering heuristic to augment the “usable sparsity” in … Read more

Reducing the number of AD passes for computing a sparse Jacobian matrix

A reduction in the computational work is possible if we do not require that the nonzeros of a Jacobian matrix be determined directly. If a column or row partition is available, the proposed substitution technique can be used to reduce the number of groups in the partition further. In this chapter, we present a substitution … Read more