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.
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.
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.
provides information on some of the talks and posters given on work in this
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.
- Our serial software
package ColPack is now released. Click on Software
for more info.
- Some of our most recent papers
include works on:
Exploiting Sparsity in Automatic Differentiation on
Multicore Architectures (AD 2012)
Partial Separability in Source-Transformation AD Tool (AD 2012)
Sparse Jacobian computation using ADIC2 and ColPack (ICCS 2011)
Ordering and Coloring Algorithms for Multicore Architectures (EuroPar 2011)
Distributed-memory parallel algorithms for distance-2 and related
coloring problems (SIAM Journal of Scientific Computing,
Vol 32, Issue 4, 2010.)
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.