Coloring and AD for Jacobians

[mauro3]

It would be nice to be able to use coloring and AD for Jacobians as well, in my case it would be for a function f:

f(y, ydot) = ....
J = df/dy + a* df/dydot 

I think this would entail two things: make the graph algorithms work on the non-symmetric case. Document it so I can figure out how to use it. It would be nice if both the coloring and the AD would be usable. The coloring alone I could then use for finite difference Jacobians.

I'm hoping to use this in SciML/ODE.jl#72

See also: https://groups.google.com/d/msg/julia-users/P_56xjp3WVo/wbZj0Tu0TzwJ

[mlubin]

This package implements the acyclic coloring heuristic described here: http://www.eecs.wsu.edu/~assefaw/publications/IJOC21-2-2009.pdf

It's specialized to the symmetric case; I don't know how much code if any is reusable for the asymmetric/Jacobian case. I do know that the standard package in the field is colpack. I won't be able to provide much help in the implementation, but I'm happy to describe any aspects of the code here to the extent that it would be useful. It would be valuable to move these graph coloring algorithms into a separate package once we have multiple variants implemented, also happy to collaborate on that.

You may want to look at some of the older code which took as input a standard Graph object. Unfortunately I hit some performance issues with the Graphs package which were resolved by creating my own data structure for the graph.

[mauro3]

Thanks for looking into this. I agree that it would be great to have the coloring in a separate package. I'll try to make some progress on the Jakobian coloring and report back.

[mauro3]

I put together this package https://github.com/mauro3/MatrixColorings.jl which seems to work fine. This is the first time I coded something like this, so feel free to suggest improvements. Would an interface like this work for Hessians as well? Maybe we can discuss this at JuliaCon.

[mlubin]

Looks pretty reasonable, hessian coloring has mostly the same structure. What does add_delta! do?

[mauro3]

Good to hear. add_delta! is just a convenience function. It adds something to all indices of x which correspond to one color of the Jacobian. It is used to add delta_x for finite differencing, although if I understand correctly it could be used in AD too. See https://github.com/mauro3/MatrixColorings.jl/blob/master/example/jacobian_eval.jl#L182