Abstracts: Shaun Forth
Automatic Differentiation and Sparse Matrices
We review the matrix interpretation of the automatic differentiation (AD) of functions defined by computer programs in which a sparse linear system governs the relationship between the derivatives of program variables. Griewank and Reese (1991) showed that Gauss elimination of entries corresponding to intermediate variables in forward and reverse order gives sparsity exploiting variants of the classic forward and reverse mode AD algorithms. Other elimination orderings based on Markowitz criteria can further reduce arithmetic operations counts leading to very efficient evaluation of Jacobians (Forth et al 2004). Reid has shown such approaches may lead to numerical instability - an effect not yet found in practical applications. The so-called "edge-elimination" and "face-elimination" techniques of Naumann (2001, 2004) may further reduce operations counts leading to combinatorial optimisation problems that have yet to incorporate the effects of running on real hardware (Tadjouddine et al 2006).