Iterated greedy recoloring for row and column colorings

[vchuravy]

Adds Culberson's iterated greedy recoloring as an option of GreedyColoringAlgorithm for :row and :column colorings:

GreedyColoringAlgorithm(order; recoloring_iterations=0)

Each pass recolors the vertices greedily (partial_distance2_coloring!) in an order where the vertices of each color class are consecutive. The vertices of a class are pairwise independent, so a pass never increases the number of colors (Culberson & Luo, 1996). The classes are ordered by decreasing color in odd passes and by decreasing size in even passes, so the result is deterministic. With a tuple of orders, each order's coloring is recolored before the best one is kept. The option is ignored for symmetric and bidirectional colorings, where a pass would also have to preserve the star/acyclic structure, and for forced_colors (ConstantColoringAlgorithm).

Motivation: Ariadne.jl assembles sparse Jacobians by colored forward- or reverse-mode AD, one product per color, so every color costs one Jacobian-vector product per assembly. Number of column colors on this branch:

pattern	lower bound (max row count)	greedy	+ 10 passes	+ 50 passes	+ 200 passes
sprand(Bool, 2000, 2000, 0.003)	15	20	17	17	16
5-point Laplacian, 60 × 60	5	7	7	7	7
30 × 30 elements × 16 dofs, dense blocks, face coupling (DG-like)	80	112	112	112	112

On unstructured patterns, recoloring closes much of the gap. On the full patterns of structured discretizations, the greedy coloring is already a fixed point of the recoloring, with deterministic or random class orders. There, it pays off on the small conflict graph of a class-constrained (quotient) coloring (#345): 5 colors for the Laplacian and 80 for the DG-like pattern, both equal to the lower bound.

Cost: each pass costs about as much as one greedy coloring (for the DG-like pattern, 14400 columns: ~0.08 s per pass), so the default stays 0.

Changes

• src/coloring.jl: iterated_greedy_recoloring! (documented in the dev docs)
• src/interface.jl: recoloring_iterations keyword (an ArgumentError if negative), applied in the :column and :row _coloring methods
• tests: monotonicity over 1/10/50 passes for row and column colorings, a random instance where recoloring helps, decompression tests on random instances (with their own RNG, so the instances of the existing test sets are unchanged), and JET type-stability checks

Locally on Julia 1.11: order.jl, random.jl, type_stability.jl, JET, doctests and allocation tests pass. Aqua's persistent-tasks check fails in my environment on main too.

Draft: open for feedback on the API (a keyword of GreedyColoringAlgorithm vs. a separate post-processing step, and the name).

🤖 Generated with Claude Code

[codecov]

Codecov Report

✅ All modified and coverable lines are covered by tests.
✅ Project coverage is 99.18%. Comparing base (b88875a) to head (a974f55).

Additional details and impacted files

@@            Coverage Diff             @@
##             main     #344      +/-   ##
==========================================
+ Coverage   99.17%   99.18%   +0.01%     
==========================================
  Files          22       22              
  Lines        2304     2339      +35     
==========================================
+ Hits         2285     2320      +35     
  Misses         19       19              

☔ View full report in Codecov by Harness.
📢 Have feedback on the report? Share it here.

🚀 New features to boost your workflow:

• ❄️ Test Analytics: Detect flaky tests, report on failures, and find test suite problems.

[gdalle]

Thanks! I'll take a look next week on my train to Germany