Many algorithms for solving nonlinear optimization
problems and differential equations require the computation of Jacobians (matrices of first derivatives of vector
functions) and Hessians (matrices of second derivatives of scalar
functions). Derivative matrices of functions defined by computer
programs can be computed analytically, and hence accurately, using
Automatic Differentiation (AD). Jacobians and
Hessians could also be computed approximately using the relatively older
method of Finite Differencing (FD).
The overall aim of this project is to exploit the sparsity available in large Jacobian and
Hessian matrices the best possible way in order to make their computation
using AD and FD efficient. The sparsity
exploiting techniques here are essentially the same whether one uses AD
or FD, and 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 can be identified. 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.
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.
Implementations of these 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 and on Parallel Processing,
AD Conferences, and ICIAM meetings. Presentations
provides information on talks and posters given on our works in this
project.
Home