Call tree reversal is NP-complete

MaRDI QIDQ3528765zbMATH OpenFDO

Authors Uwe Naumann

Publication date 17 October 2008

zbMATH Keywords

adjoint codecall tree reversalNP-completenessreverse mode automatic differentiation

Mathematics Subject Classification ID

Numerical differentiation (65D25) Numerical mathematical programming methods (65K05) Information storage and retrieval of data (68P20) Symbolic computation and algebraic computation (68W30) Combinatorial optimization (90C27)

Recommendations

• DAG reversal is NP-complete
• Program reversals for evolutions with non-uniform step costs
• scientific article; zbMATH DE number 2087170
• The Data-Flow Equations of Checkpointing in Reverse Automatic Differentiation
• Bounding the number of processors and checkpoints needed in time-minimal parallel reversal schedules

Cited in

(6)

• DAG reversal is NP-complete
• Bounding the number of processors and checkpoints needed in time-minimal parallel reversal schedules
• Algorithmic differentiation of numerical methods: tangent and adjoint solvers for parameterized systems of nonlinear equations
• A matrix-free exact Newton method
• Optimal re-materialization strategies for heterogeneous chains: how to train deep neural networks with limited memory
• 15 years of Adjoint Algorithmic Differentiation (AAD) in finance

This page was built for publication: Call tree reversal is NP-complete

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3528765)