Seminar Details:

LANS Informal Seminar Talks Network
" Hierarchical Coloring"

DATE: January 3, 2007

SPEAKER: Paul Hovland, MCS
LOCATION: MCS, Building 221, Room A-261, Argonne

[related website]

Discretizing PDEs on a regular grid induces a hierarchy of two types of sparsity patterns on a Jacobian matrix, one due to the stencil being used and one due to the dependence among individual degrees of freedom within that stencil. Goldfarb and Toint demonstrated how to exploit the sparsity
structure induced by the stencil, but exploiting the unstructured sparsity within the stencil must rely upon more general techniques. We present a two stage coloring strategy: Goldfarb-Toint coloring followed by optimal intra-stencil coloring. We demonstrate that optimal coloring at both stages is suboptimal in general. Nonetheless, savings of 50% or more over Goldfarb-Toint alone are possible.


Please send questions or suggestions to Jeffrey Larson: jmlarson at anl dot gov.