Publication: On lower bounds for optimal Jacobian accumulation
Introduction
Applications
Tools
Research Groups
Workshops
Publications
   List Publications
   Advanced Search
   Info
   Add Publications
My Account
About

On lower bounds for optimal Jacobian accumulation

- Article in a journal -
 

Author(s)
Viktor Mosenkis , Uwe Naumann

Published in
Special issue of Optimization Methods & Software: Advances in Algorithmic Differentiation Optimization Methods & Software

Editor(s)
Bruce Christianson, Shaun A. Forth, Andreas Griewank

Year
2018

Publisher
Taylor & Francis

Abstract
The task of finding a way to compute by using the minimal number of multiplications is generally referred to as the Optimal Jacobian Accumulation problem. Often a special case of the problem is examined, where the accumulation of the Jacobian is considered as a transformation of the linearized directed acyclic graph (l-DAG) G into , such that is a subgraph of the complete directed bipartite graph . The transformation of the l-DAG is performed by elimination methods. The most commonly used elimination methods are vertex elimination and edge elimination. The problem of transforming an l-DAG into a bipartite graph by vertex or edge eliminations with minimal costs is generally referred as the Vertex Elimination or Edge Elimination problem. Both the and problems are conjectured to be NP-hard. Thus Branch and bound based algorithms in addition to greedy heuristics are used to solve these problems. For efficient application of such algorithms, good lower bounds are essential. In this paper, we develop a new approach for computing the lower bounds for the optimal solution of the and problems.

Cross-References
Christianson2018Sio

BibTeX
@ARTICLE{
         Mosenkis2018Olb,
       crossref = "Christianson2018Sio",
       author = "Viktor Mosenkis and Uwe Naumann",
       title = "On lower bounds for optimal {J}acobian accumulation",
       journal = "Optimization Methods \& Software",
       volume = "33",
       number = "4--6",
       pages = "1264--1287",
       year = "2018",
       publisher = "Taylor \& Francis",
       doi = "10.1080/10556788.2017.1397145",
       url = "https://doi.org/10.1080/10556788.2017.1397145",
       eprint = "https://doi.org/10.1080/10556788.2017.1397145",
       abstract = "The task of finding a way to compute by using the minimal number of multiplications
         is generally referred to as the Optimal Jacobian Accumulation problem. Often a special case of the
         problem is examined, where the accumulation of the Jacobian is considered as a transformation of the
         linearized directed acyclic graph (l-DAG) G into , such that is a subgraph of the complete directed
         bipartite graph . The transformation of the l-DAG is performed by elimination methods. The most
         commonly used elimination methods are vertex elimination and edge elimination. The problem of
         transforming an l-DAG into a bipartite graph by vertex or edge eliminations with minimal costs is
         generally referred as the Vertex Elimination or Edge Elimination problem. Both the and problems are
         conjectured to be NP-hard. Thus Branch and bound based algorithms in addition to greedy heuristics
         are used to solve these problems. For efficient application of such algorithms, good lower bounds
         are essential. In this paper, we develop a new approach for computing the lower bounds for the
         optimal solution of the and problems.",
       booktitle = "Special issue of Optimization Methods \& Software: Advances in
         Algorithmic Differentiation",
       editor = "Bruce Christianson and Shaun A. Forth and Andreas Griewank"
}


back
  

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