Publication: Sub-exponential graph coloring algorithm for stencil-based Jacobian computations
Introduction
Applications
Tools
Research Groups
Workshops
Publications
   List Publications
   Advanced Search
   Info
   Add Publications
My Account
About

Sub-exponential graph coloring algorithm for stencil-based Jacobian computations

- Article in a journal -
 

Author(s)
M. Lülfesmann , K. Kawarabayashi

Published in
Journal of Computational Science

Year
2014

Abstract
Abstract Partial differential equations can be discretized using a regular Cartesian grid and a stencil-based method to approximate the partial derivatives. The computational effort for determining the associated Jacobian matrix can be reduced. This reduction can be modeled as a (grid) coloring problem. Currently, this problem is solved by using a heuristic approach for general graphs or by developing a formula for every single stencil. We introduce a sub-exponential algorithm using the Lipton–Tarjan separator in a divide-and-conquer approach to compute an optimal coloring. The practical relevance of the algorithm is evaluated when compared with an exponential algorithm and a greedy heuristic.

AD Theory and Techniques
graph coloring, Sparsity

BibTeX
@ARTICLE{
         Lulfesmann2014Seg,
       title = "Sub-exponential graph coloring algorithm for stencil-based {J}acobian computations",
       journal = "Journal of Computational Science",
       volume = "5",
       number = "1",
       pages = "1--11",
       year = "2014",
       issn = "1877-7503",
       doi = "http://dx.doi.org/10.1016/j.jocs.2013.06.002",
       url = "http://www.sciencedirect.com/science/article/pii/S1877750313000781",
       author = "M. L{\"u}lfesmann and K. Kawarabayashi",
       abstract = "Abstract Partial differential equations can be discretized using a regular
         Cartesian grid and a stencil-based method to approximate the partial derivatives. The computational
         effort for determining the associated Jacobian matrix can be reduced. This reduction can be modeled
         as a (grid) coloring problem. Currently, this problem is solved by using a heuristic approach for
         general graphs or by developing a formula for every single stencil. We introduce a sub-exponential
         algorithm using the Lipton–Tarjan separator in a divide-and-conquer approach to compute an
         optimal coloring. The practical relevance of the algorithm is evaluated when compared with an
         exponential algorithm and a greedy heuristic.",
       keywords = "Sparsity exploitation",
       ad_theotech = "graph coloring, Sparsity"
}


back
  

Contact:
autodiff.org
Username:
Password:
(lost password)