Coloring algorithms to be implemented about sparsedifftools.jl HOT 7 OPEN

For Hessians, is it just the same coloring but on the adjacency matrix?

from sparsedifftools.jl.

What methods are used in the bidirectional coloring?

from sparsedifftools.jl.

In case of direct recovery, star coloring would work for Hessians. If we plan on extending the stack to include substitution based evaluation, we will have to employ acylic coloring as well.

from sparsedifftools.jl.

We can use either greedy distance-2 coloring (similar to distance-1 coloring) or partial distance-2 coloring in cases where we do not mix both forward and backward AD modes.

from sparsedifftools.jl.

Star coloring must satisfy the two conditions: (1) every pair of adjacent vertices receives distinct colors (a distance-1 coloring), and (2) every path on four vertices uses at least three colors.

Acyclic coloring has the conditions: (1) the coloring corresponds to a distance-1 coloring, and (2) vertices in every cycle of the graph are assigned at least three distinct colors. The name acyclic comes from the fact that subgraph induced by vertices assigned any two colors is a collection of trees—and hence is acyclic.

reference: What Color is your Jacobian?

from sparsedifftools.jl.

Add some acyclic coloring to the list as well then since substitution seems to be the proper way to handle bidirectional and forward-over-reverse.

from sparsedifftools.jl.

The original paper does not talk about acyclic coloring and I can't find any good resources that discuss it either. Will add it to the to-do as soon as I get a reliable paper on it.

from sparsedifftools.jl.