Skip to content

Add power-of-two covers - #117

Merged
timholy merged 3 commits into
mainfrom
teh/pow2
Nov 19, 2026
Merged

timholy merged 3 commits into
mainfrom
teh/pow2

Conversation

@timholy

@timholy timholy commented Nov 19, 2026

Copy link
Copy Markdown
Member

In some cases, bitwise covariance is a major asset. Because of gauge freedom, rounding the output does not guarantee covariance. This adds dedicated solvers that never round internally, so that outputs are always covariant. It also adds public (not exported) names for obtaining the exponents directly, so that cases of over/underflow can be handled.

`MatrixCovers.symcover_exponents(A)` (public, not exported) returns
integer exponents `α` with `2^(α[i] + α[j]) >= |A[i,j]|`, and
`symcover(A; pow2=true)` returns the factors `2 .^ α`. Scaling by
these factors is free of rounding, and the exponents are exactly
covariant under power-of-two diagonal rescaling whenever every support
component has a nonzero diagonal entry.

The exponents `ceil(log2|A[i,j]|)` are read exactly from the
floating-point representation. Integer reference exponents, which shift
exactly under rescaling, reduce `A` to a residual matrix that does not
change; the existing symcover heuristic runs on that residual, its
factors are rounded up to powers of two, and integer boost and
Gauss-Seidel tightening passes finish the cover so that every row is
tight on some entry.

Version bumped to 2.1.0.

Assisted-by: Claude Opus 5.5 <noreply@anthropic.com>
`MatrixCovers.cover_exponents(A)` (public, not exported) returns integer
exponents `α`, `β` with `2^(α[i] + β[j]) >= |A[i,j]|`, and
`cover(A; pow2=true)` returns the factors. The cover products are exactly
covariant under power-of-two diagonal rescaling on any support; the
factors follow the `cover_min` balance convention rounded to integers.

With the transversal start, a maximum-weight transversal of the exponent
matrix and integer optimal duals come from the existing assignment
solver run on integer-valued exponents, where its arithmetic is exact.
The duals are made canonical (a floored layer-average start on the group
graph, raised to the least feasible point above it), so the slacks fed
to the floating-point stages do not change under rescaling; the result
is rounded and repaired in integers and stays tight on every
maximum-weight transversal. The unconstrained start uses integer
reference exponents and runs the existing heuristic on the residual
matrix, as in the symmetric case. `start=:geomean` is rejected.

The layer-average starts take floored means for integer values, and
`_max_product_transversal` accepts values that are already logarithms.

Assisted-by: Claude Opus 5.5 <noreply@anthropic.com>
`symcover` and `cover` gain a `pow2` keyword, and the exponent solvers
`symcover_exponents` and `cover_exponents` are new entrypoints that
return `int64` arrays.

Assisted-by: Claude Opus 5.5 <noreply@anthropic.com>
@codecov

codecov Bot commented Nov 19, 2026 •

Copy link
Copy Markdown

Codecov Report

❌ Patch coverage is 99.50000% with 2 lines in your changes missing coverage. Please review.
✅ Project coverage is 98.39%. Comparing base (19030b0) to head (dc3c851).

Files with missing lines Patch % Lines
src/pow2_covers.jl 99.48% 2 Missing ⚠️
Additional details and impacted files
@@            Coverage Diff             @@
##             main     #117      +/-   ##
==========================================
+ Coverage   98.34%   98.39%   +0.05%     
==========================================
  Files          26       27       +1     
  Lines        8290     8685     +395     
==========================================
+ Hits         8153     8546     +393     
- Misses        137      139       +2     

☔ 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.

@timholy
timholy merged commit 81acf94 into main Nov 19, 2026
7 checks passed
@timholy
timholy deleted the teh/pow2 branch November 19, 2026 11:36
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

1 participant