Coloring algorithms to be implemented

[pkj-m]

• Greedy Star Coloring, "What Color is your Jacobian?" pg 662
• Greedy Star Coloring 2, "What Color is your Jacobian?" pg 663
• Backtracking Sequential Coloring (NP-hard), "Graph Coloring Algorithms"
• Star Bicoloring, "What Color is your Jacobian?" pg 668
• Acyclic Coloring "New Acyclic and Star Coloring Algorithms with Application to Computing Hessians"

[ChrisRackauckas]

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

[ChrisRackauckas]

What methods are used in the bidirectional coloring?

[pkj-m]

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.

[pkj-m]

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.

[pkj-m]

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?

[ChrisRackauckas]

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.

[pkj-m]

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.