New Acyclic and
Star Coloring Algorithms
with Applications to Hessian Computation
Abstract.
Acyclic and
star coloring problems are specialized vertex coloring problems that
arise in the efficient computation of Hessians using automatic
differentiation or finite differencing, when both sparsity and
symmetry are exploited. We present an algorithmic paradigm for finding
heuristic solutions for these two NP-hard problems. The
underlying common technique is the exploitation of the structure of
two-colored induced subgraphs. For a graph $G$ on $n$ vertices and $m$
edges, the time complexity of our star coloring algorithm is
$O(n\overline{d}_2)$ where $\overline{d}_k$, a generalization of vertex
degree, denotes the average number of distinct paths of length at most
$k$ edges starting at a vertex in $G$; and the time complexity of our
acyclic coloring algorithm is $O(n\overline{d}_2 \cdot \alpha(m,m'))$
where $\alpha$ is the inverse of Ackermann's function and $m' =
n\overline{d}_2$. (The factor $\alpha(m,m')$ in the latter expression
is nearly a constant.) The space complexity of both algorithms is
$O(m)$. To the best of our knowledge, our acyclic coloring
algorithm is the first practical algorithm for the problem. For
the star coloring problem, our algorithm improves on the time
complexity of and the number of colors used by a previously known
$O(n\overline{d}_3)$-time heuristic algorithm. Computational
results from experiments on
various large-size test graphs demonstrate that the algorithms are fast
and produce highly effective solutions. The use of these algorithms in
Hessian computation is expected to reduce overall runtime significantly.
Key words. acyclic
coloring, star coloring, computation of
Hessians, automatic differentiation, finite differences
|
|