LANS Informal Seminar Talks Network
" Hierarchical Coloring"
DATE: January 3, 2007
TIME: - Description:
SPEAKER: Paul Hovland, MCS
LOCATION: MCS, Building 221, Room A-261, Argonne
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 Debojyoti Ghosh: ghosh at mcs dot anl dot gov.