|
|||||
|
|
Sub-exponential graph coloring algorithm for stencil-based Jacobian computations |
|
| Institution: | 1. Institute for Scientific Computing, Center for Computational Engineering Science, RWTH Aachen University, D-52056 Aachen, Germany;2. National Institute of Informatics and JST ERATO Kawarabayashi Large Graph Project, 2-1-2, Hitotsubashi, Chiyoda-ku, Tokyo, Japan;1. Department of Systems & Computer Engineering, Carleton University, Center for Visualization and Simulation (VSIM), Ottawa, ON, Canada;2. Autodesk Research Toronto, ON, Canada |
| 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: | Grid coloring algorithm Divide-and-conquer approach Lipton–Tarjan separator Stencil discretization Derivative computation Sparsity exploitation |
| 本文献已被 ScienceDirect 等数据库收录！ | |