Coloring algorithms to be implemented

JuliaDiff / SparseDiffTools.jl

Fast jacobian computation through sparsity exploitation and matrix coloring

MIT License

237 stars 41 forks source link

Coloring algorithms to be implemented #29

Open pkj-m opened 5 years ago

pkj-m commented 5 years ago

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

ChrisRackauckas commented 5 years ago

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

ChrisRackauckas commented 5 years ago

What methods are used in the bidirectional coloring?

pkj-m commented 5 years ago

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 commented 5 years ago

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 commented 5 years ago

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 commented 5 years ago

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 commented 5 years ago

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.