{"id":895,"date":"2023-08-15T11:16:54","date_gmt":"2023-08-15T18:16:54","guid":{"rendered":"https:\/\/labs.wsu.edu\/scads\/?page_id=895"},"modified":"2025-08-20T17:26:58","modified_gmt":"2025-08-21T00:26:58","slug":"automatic-differentiation","status":"publish","type":"page","link":"https:\/\/labs.wsu.edu\/scads\/research\/automatic-differentiation\/","title":{"rendered":"Automatic Differentiation"},"content":{"rendered":"\n

Automatic Differentiation<\/h1>\n\n\n\n
\n\n\n\n

Many algorithms for nonlinear optimization, solution of differential equations, sensitivity analysis, and uncertainty quantification rely on computation of derivatives. Such algorithms can greatly benefit from Algorithmic (or Automatic) Differentiation<\/em> (AD), a technology for transforming a computer program for computing a function into a program for computing the function’s derivatives. AD furnishes derivatives accurately (i.e. without truncation errors) and with relatively little effort from a user’s end, and the time and space complexity of computing derivatives using AD can be bounded by the complexity of evaluating the function itself. For these reasons, AD is a better alternative to other methods of computing derivatives such as finite differencing or symbolic differentiation, or error-prone and tedious hand coding.<\/p>\n\n\n\n

\n\n\n\n

Reverse-mode based Hessian computation<\/strong><\/p>\n\n\n\n

Together with Mu Wang and Alex Pothen at Purdue University, we have recently been working on new algorithms for Hessian computation that aim at taking full advantage of the potential of the Reverse-mode of AD and the symmetry available in the computational graph of the Hessian.<\/p>\n\n\n\n

\n\n\n\n

Sparse computation via compression<\/strong><\/p>\n\n\n\n

Much of our earlier work in Automatic Differentiation aimed at exploiting the sparsity<\/em> (and when applicable, the symmetry<\/em>) that is inherently available in large derivative matrices \u2014 Jacobians and Hessians \u2014 in order to make their computation efficient in terms of runtime and memory requirement.<\/p>\n\n\n\n

A fundamental technique that has proven effective in achieving this objective is computation via compression<\/em>. Loosely speaking, the idea is to reduce computational cost by calculating sums of columns <\/em>of a derivative matrix at a time instead of calculating one <\/em>column at a time. Columns that are to be computed together are determined by exploiting structural properties of the matrix \u2014 in particular, the structural information is used to partition the set of columns into a small number of groups of “independent” columns. Here, a variety of matrix partitiong problems arise depending on whether the matrix to be computed is Jacobian (nonsymmetric) or Hessian (symmetric) and the specifics of the computational approach taken. Graph coloring<\/em> models have proven to be a powerful tool for analyzing the complexity of and designing effective algorithms for these problems since the pioneering works of Coleman and More in the early 1980s.<\/p>\n\n\n\n

\n\n\n\n

Papers<\/h2>\n\n\n\n

Below is a catalogued list of papers (recent ones listed first) we have written together with a number of collaborators on graph-theoretic results and innovative algorithms for (a) efficient Reverse-mode based Hessian computation and (b) matrix partitioning (coloring) and related problems in sparse derivative matrix computation. Also included is information on the associated serial software package ColPack<\/em> we developed in support of sparse derivative computation.<\/p>\n\n\n\n

Reverse Mode-based Hessian computation<\/h3>\n\n\n\n