Parallel Algorithms for Graph Coloring in Optimization
Collaborators:
Fredrik Manne, Assefaw Gebremedhin (University of Bergen, Norway);
Bruce Hendrickson, John Shadid, Bill Spotz (Sandia National Lab).
Objective:
Optimization algorithms that employ derivative information
require the computation of a Jacobian or Hessian matrix.
Automatic differentiation (AD) and finite differences (FD)
are two techniques used to compute these matrices.
It is well-known that graph coloring algorithms could be used
to reduce the number of function evaluations needed in estimating
the Jacobian and the Hessian.
We have begun to develop parallel algorithms for graph coloring applicable
to optimization.
Approach:
We have been able to provide a unified perspective of the various
graph coloring problems, corresponding to
Jacobian and Hessian estimation, and corresponding to
FD or AD techniques, when either columns or rows only,
or both rows and columns are used to estimate the elements.
We show that all these problems
could be formulated as a single, albeit non-traditional,
distance-two graph coloring problem.
We then extend a recent parallel coloring algorithm
for the shared memory programming model, proposed by
Gebremedhin and Manne, to solve the new coloring problem.
The parallel algorithm has been developed and implemented
on an Origin 2000, and we have reported results on problems
from finite element solutions of PDEs as well as eigencomputations.
The algorithm performs well on up to 16 processors of
a shared memory machine.
This algorithm will be adapted for distributed memory machines
with hundreds of processors.
Once we complete developing the shared memory algorithm,
we will apply it to solve
the Jacobian and Hessian estimation problems in parallel on
shared-memory computers.
Once this is complete, we will extend
these ideas to solve the estimation problem on
parallel computers with message-passing programming models.
John Shadid and colleagues will collaborate with us in
developing the distributed memory code,
and in including the parallel coloring codes within
PDE constrained optimization codes at Sandia.
back to
highlights page