Publication: On optimality preserving eliminations for the minimum edge count and optimal Jacobian accumulation problems in linearized DAGs
Introduction
Applications
Tools
Research Groups
Workshops
Publications
   List Publications
   Advanced Search
   Info
   Add Publications
My Account
About

On optimality preserving eliminations for the minimum edge count and optimal Jacobian accumulation problems in linearized DAGs

- Article in a journal -
 

Author(s)
Viktor Mosenkis , Uwe Naumann

Published in
Optimization Methods and Software

Year
2012

Publisher
Taylor and Francis

Abstract
The minimum edge count (MEC) and optimal Jacobian accumulation problems in linearized directed acyclic graphs (DAGs) result from the combinatorics induced by the associativity of the chain rule of differential calculus. This paper discusses a suitable graph formalism followed by proving a number of results that yield a considerable search space reduction for both problems. An algorithmic link between numerical analysis and theoretical computer science is established. Although both problems are believed to be NP-hard in general, a linear-time algorithm is presented solving the MEC problem for a specified subclass of l-DAGs.

AD Theory and Techniques
Combinatorics, X-Country

BibTeX
@ARTICLE{
         Mosenkis2012Oop,
       title = "On optimality preserving eliminations for the minimum edge count and optimal
         {J}acobian accumulation problems in linearized {DAGs}",
       author = "Mosenkis, Viktor and Naumann, Uwe",
       publisher = "Taylor and Francis",
       year = "2012",
       journal = "Optimization Methods and Software",
       volume = "27",
       pages = "337--358",
       doi = "10.1080/10556788.2011.580745",
       abstract = "The minimum edge count (MEC) and optimal Jacobian accumulation problems in
         linearized directed acyclic graphs (DAGs) result from the combinatorics induced by the associativity
         of the chain rule of differential calculus. This paper discusses a suitable graph formalism followed
         by proving a number of results that yield a considerable search space reduction for both problems.
         An algorithmic link between numerical analysis and theoretical computer science is established.
         Although both problems are believed to be NP-hard in general, a linear-time algorithm is presented
         solving the MEC problem for a specified subclass of l-DAGs.",
       ad_theotech = "Combinatorics, X-Country",
       number = "2"
}


back
  

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