zbMATH — the first resource for mathematics

On lower bounds for optimal Jacobian accumulation. (English) Zbl 06949133
Summary: The task of finding a way to compute $$F'$$ by using the minimal number of multiplications is generally referred to as the Optimal Jacobian Accumulation (OJA) problem. Often a special case of the $$OJA$$ problem is examined, where the accumulation of the Jacobian is considered as a transformation of the linearized directed acyclic graph (l-DAG) $$G$$ into $$G'$$, such that $$G'$$ is a subgraph of the complete directed bipartite graph $$K_{n,m}$$. 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 (VE) or Edge Elimination (EE) problem. Both the VE and EE 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 VE and EE problems.
MSC:
 65K Numerical methods for mathematical programming, optimization and variational techniques 65H Nonlinear algebraic or transcendental equations