Quotient coloring: one color per class of columns or rows

[vchuravy]

Stacked on #344 (iterated greedy recoloring), which this PR needs for its default. The diff of this PR alone is the last commit, 640a728.

Adds QuotientColoringAlgorithm(classes, algo), a column/row coloring in which all columns (rows) with the same class label get the same color:

QuotientColoringAlgorithm(classes, algo=GreedyColoringAlgorithm(; recoloring_iterations=30))

Two classes conflict if any of their columns have a nonzero in a common row. quotient_pattern builds the conflict pattern of the classes (classes × distinct rows), and algo colors its columns. The class colors are then expanded to the columns. Columns of the same class must be structurally orthogonal; otherwise an ArgumentError is thrown. The algorithm plugs in through the ADTypes interface (ADTypes.column_coloring/row_coloring), so coloring checks the result like any other ADTypes.AbstractColoringAlgorithm.

Motivation: for discretizations on structured meshes, greedy colorings of the full pattern miss the translation structure, and recoloring does not help there (see #344: the greedy coloring is already a fixed point). Labeling each column by its local index in the element and the position of the element modulo a small periodic cell (e.g., 5 × 5 elements) gives a conflict pattern with few columns and very few distinct rows (49 for the examples below), so many recoloring passes are cheap. Number of column colors:

pattern	lower bound	greedy	best of 5 orders*	quotient, 5 × 5 cell, no recoloring	quotient, 5 × 5 cell (default, 30 passes)	time (default)
5-point Laplacian, 60 × 60	5	7	5	8	5	< 0.01 s
30 × 30 elements × 16 dofs, dense blocks, face coupling (DG-like)	80	112	96	128	80	0.09 s

* GreedyColoringAlgorithm((NaturalOrder(), LargestFirst(), SmallestLast(), IncidenceDegree(), DynamicLargestFirst())) on the full pattern.

The order of the class coloring barely matters (natural, largest first and the five orders above all give 5 / 80 with 30 passes), but recoloring does. The cell must fit the stencil: for the 5-point stencil, 3 × 3 and 4 × 4 cells cannot hold the optimal period-5 coloring (8 colors for the Laplacian with a 4 × 4 cell, 144 = 9 × 16 for the DG-like pattern with a 3 × 3 cell). The docstring says so.

Changes

• src/quotient.jl: QuotientColoringAlgorithm (exported, in the API docs, with a doctest), quotient_pattern (dev docs), and ADTypes.column_coloring/row_coloring methods
• test/quotient.jl: the quotient pattern (deduplication, errors), the Laplacian with optimal 5 colors for column and row partitions (with compress/decompress), classes constant on cells, trivial classes equal to greedy, an error for a too small cell, and a block pattern reaching its lower bound

Locally on Julia 1.11: quotient.jl, adtypes.jl, constant.jl, order.jl, JET, doctests and Aqua's undocumented-names check pass.

Draft because it depends on #344. Open questions: the name, the default algo, and whether a helper for block classes (local index × cell label) belongs in SMC or in user code.

🤖 Generated with Claude Code

[codecov]

Codecov Report

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

Additional details and impacted files

@@            Coverage Diff             @@
##             main     #345      +/-   ##
==========================================
+ Coverage   99.17%   99.19%   +0.02%     
==========================================
  Files          22       23       +1     
  Lines        2304     2365      +61     
==========================================
+ Hits         2285     2346      +61     
  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.