Exploiting Sparsity in Jacobian Computation
via Coloring and Automatic Dierentiation:
a Case Study in a Simulated Moving Bed process
Abstract.
Using a model from a chromatographic separation process in
chemical engineering, we demonstrate that
large, sparse Jacobians of fairly complex structures can be computed
accurately and efficiently by using automatic differentiation (AD) in
combination with a four-step procedure involving matrix {\em
compression} and {\em de-compression}. For the detection of
sparsity pattern (step 1), we employ a new operator overloading-based
implementation of a technique that relies on propagation of {\em index
domains}. To obtain the {\em seed} matrix to be used for compression
(step 2), we use a {\em distance-2 coloring} of the bipartite graph
representation of the Jacobian. The compressed Jacobian is computed
using the vector forward mode of AD (step 3). A simple routine is
used to directly recover the entries of the Jacobian from the
compressed representation (step 4). Experimental results using ADOL-C
show that the runtimes of each of these steps is in complete agreement
with theoretical analysis, and the total runtime is found to be only
about a {\em hundred} times the time needed for evaluating the function
itself. The alternative approach of computing the Jacobian without
exploiting sparsity is infeasible.
|
|