Publication: Exploiting Sparsity in Jacobian Computation via Coloring and Automatic Differentiation: A Case Study in a Simulated Moving Bed Process
Introduction
Applications
Tools
Research Groups
Workshops
Publications
   List Publications
   Advanced Search
   Info
   Add Publications
My Account
About

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 four-step procedure involving matrix compression and 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 index domains. To obtain the seed matrix to be used for compression (step 2), we use a 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 hundred times the time needed for evaluating the function itself. The alternative approach of computing the Jacobian without exploiting sparsity is infeasible.

Cross-References
Bischof2008AiA

AD Tools
ADOL-C

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/978-3-540-68942-3_29",
       pages = "327--338",
       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 compression and 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
         index domains. To obtain the seed matrix to be used for compression (step 2), we use a 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 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 = "978-3-540-68935-5",
       issn = "1439-7358",
       year = "2008",
       ad_tools = "ADOL-C",
       ad_theotech = "Sparsity"
}


back
  

Contact:
autodiff.org
Username:
Password:
(lost password)