|
|
|
Graph Coloring in Scientific Computing
Graph coloring models of various kinds have proved to be powerful abstractions for
minimizing the execution time, memory, and storage space needed in computing sparse
derivative matrices using automatic differentiation. Depending on the structure of the
derivative matrix of interest---whether it is Jacobian (nonsymmentric) or Hessian
(symmetric)---and the specifics of the computational techniques employed, as many as five
variants of coloring problems exist. Graph coloring models are also useful in discovering
concurrency in parallel scientific computation; examples include iterative methods for
sparse linear systems, adaptive mesh refinement, preconditioning, and sparse tiling.
Various kinds of matchings in graphs are needed in several scientific or high-performance
computing contexts. Examples include sparse linear systems (numerical preprocessing and block
triangular decomposition) and graph partitioning (coarsening phase of multilevel methods).
Traditional matching algorithms compute optimal solutions in superlinear time, but current
trends are toward algorithms that find approximate solutions faster. CSCAPES is developing
parallel matching algorithms based on approximation techniques. |
|---|