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.
65K Numerical methods for mathematical programming, optimization and variational techniques
65H Nonlinear algebraic or transcendental equations
Full Text: DOI
[1] Bauer, F. L., computational graphs and rounding error, SIAM J. Numer. Anal., 11, 87-96, (1974) · Zbl 0337.65028
[2] an integer programming approach to optimal derivative accumulationRecent Advances in Algorithmic DifferentiationLecture Notes in Computational Science and Engineering87SpringerBerlin/Heidelberg2012221231
[3] Gilbert, J. R., A note on the NP-completeness of vertex elimination on directed graphs, SIAM J. Alg. Disc. Methods, 1, 3, 292-294, (1980) · Zbl 0496.68030
[4] Griewank, A.; Walther, A., Evaluating Derivatives. Principles and Techniques of Algorithmic Differentiation, (2008), SIAM, Philadelphia, PA · Zbl 1159.65026
[5] Place holder for Ph.D. 27(2):337–358, to appear in RWTH Aachen publication. Available at
[6] Mosenkis, V.; Naumann, U., on optimality preserving eliminations for the minimum edge count and optimal Jacobian accumulation problems in linearized dags, Optim. Methods Softw., 27, 2, 337-358, (2012) · Zbl 1238.05259
[7] Naumann, U., optimal accumulation of Jacobian matrices by elimination methods on the dual computational graph, Math. Program., 99, 3, 399-421, (2004) · Zbl 1070.90108
[8] Naumann, U., optimal Jacobian accumulation is NP-complete, Math. Program., 112, 427-441, (2006) · Zbl 1158.68013
[9] Naumann, U.; Hu, Y., optimal vertex elimination in single-expression-use graphs, ACM Trans. Math. Softw., 35, 1, 2:1-2:20, (2008)
[10] Rose, D.; Tarjan, R., algorithmic aspects of vertex elimination on directed graphs, J. Appl. Math., 34, 1, 176-197, (1978) · Zbl 0377.65013
[11] Utke, J.; Naumann, U.; Fagan, M.; Tallent, N.; Strout, M.; Heimbach, P.; Hill, C.; Wunsch, C., openad/F: A modular open-source tool for automatic differentiation of Fortran codes, ACM Trans. Math. Softw., 34, 4, 18:1-18:36, (2008) · Zbl 1291.65140
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.