Optimal Jacobian accumulation is NP-complete

DOI10.1007/S10107-006-0042-ZMaRDI QIDQ2465656zbMATH OpenOpenAlexWikidataFDO

Authors Uwe Naumann

Publication date 7 January 2008

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10107-006-0042-z

zbMATH Keywords

automatic differentiationcomplexityNP-completeness

Mathematics Subject Classification ID

Numerical differentiation (65D25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Accumulating Jacobians as chained sparse matrix products
• An enhanced Markowitz rule for accumulating Jacobian matrices efficiently
• On lower bounds for optimal Jacobian accumulation
• scientific article; zbMATH DE number 140023
• On optimality preserving eliminations for the minimum edge count and optimal Jacobian accumulation problems in linearized DAGs

Cites work

• Accumulating Jacobians as chained sparse matrix products
• Algorithm 755: ADOL-C
• Augmented non-quadratic penalty algorithms
• Automatic differentiation: Applications, theory, and implementations. Selected papers based on the presentation at the 4th international conference on automatic differentiation (AD), Chicago, IL, USA, July 20--23, 2004
• Cheaper Jacobians by Simulated Annealing
• Computational differentiation: techniques, applications, and tools
• Hierarchical approaches to automatic differentiation
• scientific article; zbMATH DE number 53680 (Why is no real title available?)
• scientific article; zbMATH DE number 140023 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1178942 (Why is no real title available?)
• scientific article; zbMATH DE number 2152997 (Why is no real title available?)
• scientific article; zbMATH DE number 1456803 (Why is no real title available?)
• OpenAD/F
• Optimality-preserving elimination of linearities in Jacobian accumulation
• Solving Nonlinear Equations with Newton's Method
• The complexity of partial derivatives

Cited in

(15)

• DAG reversal is NP-complete
• Automatic implementation of material laws: Jacobian calculation in a finite element code with TAPENADE
• An enhanced Markowitz rule for accumulating Jacobian matrices efficiently
• On optimality preserving eliminations for the minimum edge count and optimal Jacobian accumulation problems in linearized DAGs
• On lower bounds for optimal Jacobian accumulation
• A Simple and Efficient Tensor Calculus for Machine Learning
• CLEAR: covariant least-square refitting with applications to image restoration
• scientific article; zbMATH DE number 7779290 (Why is no real title available?)
• A matrix-free exact Newton method
• On sparse matrix chain products
• 15 years of Adjoint Algorithmic Differentiation (AAD) in finance
• Simplifying debiased inference via automatic differentiation and probabilistic programming
• A note on the computational complexity of chain rule differentiation
• Optimality-preserving elimination of linearities in Jacobian accumulation
• Zero variance differential geometric Markov chain Monte Carlo algorithms

Describes a project that uses

Uses Software

• ADOL-C
• TAPENADE
• TAF

This page was built for publication: Optimal Jacobian accumulation is NP-complete

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