On lower bounds for optimal Jacobian accumulation. (2nd November 2018)

• Record Type: Journal Article
• Authors: Mosenkis, Viktor; Naumann, Uwe
• Is Part Of: Optimization methods and software. Volume 33:Number 4/6(2018)
• Page Start: 1264
• Page End: 1287
• Publication Date: 2018-11-02
• Subjects: vertex elimination -- edge elimination -- optimal Jacobian accumulation -- lower bounds -- branch and bound; 65K -- 65H; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2017.1397145
• Languages: English
• ISSNs: 1055-6788

Abstract

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 theVertex Elimination ( ) orEdge 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.