A Comprehensive Evaluation of Vertex Elimination Algorithms for Algorithmic Differentiation
Alex Crane, Pål Grønås Drange, Eli Friedman, Paul D. Hovland, Jan Hückelheim, Andrew Lyons, Yosuke Mizutani, Macéo Ottavy, Blair D. Sullivan · 2026
Read A Comprehensive Evaluation of Vertex Elimination Algorithms for Algorithmic Differentiation by Alex Crane, Pål Grønås Drange, Eli Friedman, Paul D. Hovland, Jan Hückelheim, Andrew Lyons, Yosuke Mizutani, Macéo Ottavy, Blair D. Sullivan (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-24280.txt.
Description
Crane and eight co-authors evaluate vertex heuristics for algorithmic differentiation. Finding the elimination order is NP-complete, so practice relies on heuristics never tested at scale. The team builds new integer-programming formulations for optimal elimination and a minimum-edge-count goal, scaling to graphs ten to a hundred times larger. On a new corpus of medium graphs with known optima, they test existing heuristics. They add a tight analysis of forward and reverse modes, a simple separator-based algorithm, and the first lower bounds for both problems.
Catalog record
| CREATOR | Alex Crane, Pål Grønås Drange, Eli Friedman, Paul D. Hovland, Jan Hückelheim, Andrew Lyons, Yosuke Mizutani, Macéo Ottavy, Blair D. Sullivan |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 145495 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.24280