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

CREATORAlex 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
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE145495
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.24280

Browse the full library · About the Tower of Babel