

Combinatorial Optimization of Stencilbased Jacobian Computations
Part of a collection
  

Author(s)
H. M. Bücker
, M. Lülfesmann

Published in Proceedings of the 2010 International Conference on Computational and Mathematical Methods in Science and Engineering, Almería, Andalucía, Spain, June 2630, 2010

Editor(s) J. V. Aguiar 
Year 2010 
Abstract The computation of all nonzero entries of a sparse Jacobian matrix using either divided differencing or the forward mode of automatic differentiation is considered. Throughout this article, we assume that the sparsity of the Jacobian stems from a stencilbased computation of the underlying function which is typical for numerical applications in computational science and engineering involving partial differential equations. The minimization of the time needed to compute all nonzero Jacobian entries is formulated as a combinatorial optimization problem. We present three different, yet equivalent, representations of that problem and discuss each of its advantages and disadvantages. Broadly speaking, the three representations belong to the areas of linear algebra, grid discretization, and graph theory. 
AD Theory and Techniques graph coloring, Sparsity 
BibTeX
@INPROCEEDINGS{
Bucker2010COo,
author = "H. M. B{\"u}cker and M. L{\"u}lfesmann",
title = "Combinatorial Optimization of Stencilbased {J}acobian Computations",
booktitle = "Proceedings of the 2010 International Conference on Computational and Mathematical
Methods in Science and Engineering, Almer\'{i}a, Andaluc\'{i}a, Spain,
June~2630, 2010",
editor = "J. V. Aguiar",
pages = "284295",
isbn = "9788461355105",
abstract = "The computation of all nonzero entries of a sparse Jacobian matrix using either
divided differencing or the forward mode of automatic differentiation is considered. Throughout this
article, we assume that the sparsity of the Jacobian stems from a stencilbased computation of the
underlying function which is typical for numerical applications in computational science and
engineering involving partial differential equations. The minimization of the time needed to compute
all nonzero Jacobian entries is formulated as a combinatorial optimization problem. We present three
different, yet equivalent, representations of that problem and discuss each of its advantages and
disadvantages. Broadly speaking, the three representations belong to the areas of linear algebra,
grid discretization, and graph theory.",
year = "2010",
volume = "1",
ad_theotech = "graph coloring, Sparsity"
}
 
back

