SciML / ADTypes.jl

Repository for automatic differentiation backend types
https://sciml.github.io/ADTypes.jl/
MIT License
38 stars 11 forks source link

Add symmetric coloring function #43

Closed gdalle closed 5 months ago

gdalle commented 5 months ago

Motivation

Hessian coloring is slightly different from Jacobian coloring, so it needs a dedicated function symmetric_coloring, which this PR introduces.

Now we have all we need to implement problems P1 and P2 of the reference paper What color is your Jacobian? (see tables below). The actual coloring algorithm will vary between column_coloring/row_coloring and symmetric_coloring, but that's okay: we can subtype AbstractColoringAlgorithm as follows

struct GreedyColoringAlgorithm <: AbstractColoringAlgorithm
    vertex_ordering_function::Function  # for instance largest degree first
end

and then dispatch

column_coloring(M, ::GreedyColoringAlgorithm) = # greedy distance-2 coloring
row_coloring(M, ::GreedyColoringAlgorithm) = # greedy distance-2 coloring
symmetric_coloring(M, ::GreedyColoringAlgorithm) = # greedy star coloring

image image

Checklist

codecov[bot] commented 5 months ago

Codecov Report

All modified and coverable lines are covered by tests :white_check_mark:

Project coverage is 100.00%. Comparing base (bb38b92) to head (840c20b).

Additional details and impacted files ```diff @@ Coverage Diff @@ ## main #43 +/- ## ========================================= Coverage 100.00% 100.00% ========================================= Files 6 6 Lines 63 64 +1 ========================================= + Hits 63 64 +1 ```

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.