

Exploiting Sparsity in Jacobian Computation via Coloring and Automatic Differentiation: A Case Study in a Simulated Moving Bed Process
incollection
  

Author(s)
Assefaw H. Gebremedhin
, Alex Pothen
, Andrea Walther

Published in Advances in Automatic Differentiation

Editor(s) Christian H. Bischof, H. Martin Bücker, Paul D. Hovland, Uwe Naumann, J. Utke 
Year 2008 
Publisher Springer 
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 fourstep procedure involving matrix compression and decompression. For the detection of sparsity pattern (step 1), we employ a new operator overloadingbased implementation of a technique that relies on propagation of index domains. To obtain the seed matrix to be used for compression (step 2), we use a distance2 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 ADOLC 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 hundred times the time needed for evaluating the function itself. The alternative approach of computing the Jacobian without exploiting sparsity is infeasible. 
CrossReferences Bischof2008AiA 
AD Tools ADOLC 
AD Theory and Techniques Sparsity 
BibTeX
@INCOLLECTION{
Gebremedhin2008ESi,
author = "Assefaw H. Gebremedhin and Alex Pothen and Andrea Walther",
title = "Exploiting Sparsity in {J}acobian Computation via Coloring and Automatic
Differentiation: {A} Case Study in a Simulated Moving Bed Process",
doi = "10.1007/9783540689423_29",
pages = "327338",
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 fourstep procedure
involving matrix compression and decompression. For the detection of sparsity pattern (step 1), we
employ a new operator overloadingbased implementation of a technique that relies on propagation of
index domains. To obtain the seed matrix to be used for compression (step 2), we use a distance2
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
ADOLC 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 hundred times the time needed for
evaluating the function itself. The alternative approach of computing the Jacobian without
exploiting sparsity is infeasible.",
crossref = "Bischof2008AiA",
booktitle = "Advances in Automatic Differentiation",
publisher = "Springer",
editor = "Christian H. Bischof and H. Martin B{\"u}cker and Paul D. Hovland and Uwe
Naumann and J. Utke",
isbn = "9783540689355",
issn = "14397358",
year = "2008",
ad_tools = "ADOLC",
ad_theotech = "Sparsity"
}
 
back

