Sparse Derivative Computation
NSF and DOE Funded Project

Home | People | Papers | Presentations | Software | Automatic Differentiation

Overview

The overall aim of this project is to exploit the sparsity available in large-scale Jacobian and Hessian matrices the best possible way in order to make their computation using automatic differentiation (AD) (or finite differences) efficient. The sparsity exploiting techniques involve partitioning the columns, or rows, (or both) of a derivative matrix into a small number of groups. Depending on whether the matrix of interest is Jacobian (nonsymmentric) or Hessian (symmetric), and on the specifics of the computational techniques employed, several partitioning problems exist. We formulate these as graph coloring problems, enabling us to analyze the complexity of the problems, and to design and implement effective algorithms for solving them.

Implementations of sequential algorithms we have developed for these coloring problems and other related tasks in derivative computation have been assembled in our software package ColPack. The package ColPack has been interfaced with the operator overloading-based AD tool ADOL-C and the source-transformation-based AD tool ADIC2. Software provides a description of the functionalities available in and the organization of ColPack. For detailed discussions of the algorithms used in ColPack and their performance, see Papers.

A large part of the effort in this project is geared towards developing parallel algorithms. Papers also includes a number of articles discussing our work on parallel coloring algorithms on distributed memory computers and emerging multicore architectures. Implementations of the distributed-memory algorithms are made publicly available via the Zoltan toolkit of Sandia National Labs.

Results from this project have been presented at several international conferences, including SciDAC Conferences; SIAM Conferences on Optimization, Computational Science and Engineering, and Parallel Processing; AD Conferences; and ICIAM meetings. Presentations provides information on some of the talks and posters given on work in this project.

Funding
This project is funded by the Department of Energy through the SciDAC Applied Math Institute for Combinatorial Scientific Computing and Petascale Simulations (CSCAPES) and by the National Science Foundation.

 

News & Updates

 

  • Our serial software package ColPack is now released. Click on Software for more info.
  • Some of our most recent papers include works on:

o        Exploiting Sparsity in Automatic Differentiation on Multicore Architectures (AD 2012)

o        Partial Separability in Source-Transformation AD Tool (AD 2012)

o        Sparse Jacobian computation using ADIC2 and ColPack (ICCS 2011)

o        Ordering and Coloring Algorithms for Multicore Architectures (EuroPar 2011)

o        Distributed-memory parallel algorithms for distance-2 and related coloring problems (SIAM Journal of Scientific Computing, Vol 32, Issue 4, 2010.)

o        Hessian computation in an electric power flow problem (INFORMS Journal on Computing, Vol 21, No 2, 2009.)

  • This project is funded by the DOE via the SciDAC-2 Institute CSCAPES, and by the National Science Foundation.