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.
Home