EHZ capacity algorithms (HK2017, Tube, Billiard). When to use each, runtime characteristics, applicability domains.
This skill covers the three EHZ capacity algorithms available in rust_viterbo: HK2017, Tube, and Billiard. Use this to decide which algorithm to apply and understand performance characteristics.
Note: Algorithm crates (hk2017, tube, billiard) are currently stubs awaiting reimplementation. Sections marked "(LEGACY VERSION)" contain performance data from legacy experiments that may not match reimplemented code.
| Algorithm | Domain | Complexity | Practical Limit | Status |
|---|---|---|---|---|
| HK2017 (naive) | Any polytope | O(F!) | F <= 8 | Unimplemented |
| HK2017 (graph-pruned) | Any polytope | unknown | F <= 10 | Unimplemented |
| Tube | No Lagrangian 2-face | unknown | unknown | Unimplemented |
| Billiard | Lagrangian product | O(E^6) | unknown | Unimplemented |
Where F = number of facets, E = number of edges.
time_ms = 5.51e-04 * permutations^1.059
Simplified: ~1 microsecond per permutation (linear scaling), R^2 = 0.9997.
For F facets: perms = sum_{k=2}^{F} F!/(F-k)!
Example: F=5 gives 20 + 60 + 120 + 120 = 320 permutations.
| Budget | Max Facets (Naive) | Max Facets (GraphPruned) |
|---|---|---|
| 1 second | 8 | 9 |
| 5 seconds | 9 | 10 |
| 30 seconds | 10 | 10+ |
FFI enforces a 10-facet hard limit to prevent runaway computation.
GraphPruned enumerates only cycles in the facet adjacency graph instead of all ordered subsets.
| Facets | Naive Time | GraphPruned Time | Speedup |
|---|---|---|---|
| 5 | 0.27 ms | 0.13 ms | 2.0x |
| 8 | 111 ms | 15 ms | 7.4x |
| 9 | 1383 ms | 551 ms | 2.5x |
Best speedup on axis-aligned polytopes (tesseract) where adjacency graph is sparse.
t_ms = beta * tubes, where beta ~ 1.6 us/tube
R^2 ~ 0.92 (less predictable than HK2017).
Tube algorithm requires the polytope to be non-Lagrangian (no Lagrangian 2-faces).
| Polytope | Tube Time | HK2017 Status |
|---|---|---|
| Cross-polytope (16f) | 1.2s | Infeasible |
| 24-cell (24f) | 249ms | Infeasible |
| Polytope | Facets | Capacity | Algorithm |
|---|---|---|---|
| 4-simplex | 5 | 0.4167 | HK2017 |
| Tesseract | 8 | 4.0 | HK2017 |
| Cross-polytope | 16 | 1.0 | Tube |
| 24-cell | 24 | 2.0 | Tube |
The Mahler inequality states: c(K) * c(K^polar) >= 4.
Tesseract x Cross-polytope (polar duals):
24-cell (self-dual):
These polytopes are extremal for Mahler in 4D.
| Function | % | Category |
|---|---|---|
| tube_capacity | 23.8% | Algorithm |
| intersect_polygons | 16.2% | Geometry |
| Memory ops (malloc/free/memcpy) | ~23% | Memory |
Profile: Memory-bound (many small tubes).
| Function | % | Category |
|---|---|---|
| tube_capacity | 32.7% | Algorithm |
| do_inverse4 | 13.3% | Linear algebra |
| intersect_polygons | 12.5% | Geometry |
Profile: Compute-bound (fewer, larger computations).
For a k-facet permutation, closure requires: sum_i beta_i * n_i = 0, beta_i >= 0
Tesseract normals come in opposite pairs (+e_j, -e_j). For any facet sequence, there's likely a "balancing" normal available.