Publication: Call Tree Reversal is NP-Complete
Introduction
Applications
Tools
Research Groups
Workshops
Publications
   List Publications
   Advanced Search
   Info
   Add Publications
My Account
About

Call Tree Reversal is NP-Complete

- incollection -
 

Author(s)
Uwe Naumann

Published in
Advances in Automatic Differentiation

Editor(s)
Christian H. Bischof, H. Martin Bücker, Paul D. Hovland, Uwe Naumann, J. Utke

Year
2008

Publisher
Springer

Abstract
The data flow of a numerical program is reversed in its adjoint. We discuss the combinatorial optimization problem that aims to find optimal checkpointing schemes at the level of call trees. For a given amount of persistent memory the objective is to store selected arguments and/or results of subroutine calls such that the overall computational effort (the total number of floating-point operations performed by potentially repeated forward evaluations of the program) of the data-flow reversal is minimized. CALL TREE REVERSAL is shown to be NP-complete.

Cross-References
Bischof2008AiA

AD Theory and Techniques
Adjoint, Checkpointing

BibTeX
@INCOLLECTION{
         Naumann2008CTR,
       title = "Call Tree Reversal is {NP}-Complete",
       doi = "10.1007/978-3-540-68942-3_2",
       author = "Uwe Naumann",
       abstract = "The data flow of a numerical program is reversed in its adjoint. We discuss the
         combinatorial optimization problem that aims to find optimal checkpointing schemes at the level of
         call trees. For a given amount of persistent memory the objective is to store selected arguments
         and/or results of subroutine calls such that the overall computational effort (the total number of
         floating-point operations performed by potentially repeated forward evaluations of the program) of
         the data-flow reversal is minimized. CALL TREE REVERSAL is shown to be NP-complete.",
       crossref = "Bischof2008AiA",
       pages = "13--22",
       booktitle = "Advances in Automatic Differentiation",
       publisher = "Springer",
       editor = "Christian H. Bischof and H. Martin B{\"u}cker and Paul D. Hovland and Uwe
         Naumann and J. Utke",
       isbn = "978-3-540-68935-5",
       issn = "1439-7358",
       year = "2008",
       ad_theotech = "Adjoint, Checkpointing"
}


back
  

Contact:
autodiff.org
Username:
Password:
(lost password)