Graph Coloring for Computing Derivatives
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. 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.
  • Our most recent papers include works on:

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

o        Parallel algorithms for distance-2 and related coloring problems (SIAM J. Sci. Comput. 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 part of the CSCAPES Institute, thanks to funding from DOE's Office of Science under SciDAC-2.