×

zbMATH — the first resource for mathematics

DAG reversal is NP-complete. (English) Zbl 1192.68490
Summary: Runs of numerical computer programs can be visualized as directed acyclic graphs (DAGs). We consider the problem of restoring the intermediate values computed by such a program (the vertices in the DAG) in reverse order for a given upper bound on the available memory. The minimization of the associated computational cost in terms of the number of performed arithmetic operations is shown to be NP-complete. The reversal of the data-flow finds application, for example, in the efficient evaluation of adjoint numerical programs. We derive special cases of numerical programs that require the intermediate values exactly in reverse order, thus establishing the NP-completeness of the optimal adjoint computation problem. Last but not least, we review some state-of-the-art approaches to efficient data-flow reversal taken by existing software tools for automatic differentiation.

MSC:
68R10 Graph theory (including graph drawing) in computer science
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] ()
[2] ()
[3] ()
[4] ()
[5] Garey, M.; Johnson, D., Computers and intractability—A guide to the theory of NP-completeness, (1979), W.H. Freeman and Company · Zbl 0411.68039
[6] Giering, R.; Kaminski, T., Recipes for adjoint code construction, ACM transactions on mathematical software, 24, 4, 437-474, (1998) · Zbl 0934.65027
[7] Griewank, A., Evaluating derivatives. principles and techniques of algorithmic differentiation, (2000), SIAM · Zbl 0958.65028
[8] L. Hascoët, M. Araya-Polo, The adjoint data-flow analyses: Formalization, properties, and applications, in: [2], Springer, 2005, pp. 135-146 · Zbl 1270.65089
[9] Hascoët, L.; Naumann, U.; Pascual, V., To-be-recorded analysis in reverse mode automatic differentiation, Future generation computer systems, 21, 1401-1417, (2005)
[10] L. Hascoët, V. Pascual, Tapenade 2.1 user’s guide, Technical report 300, INRIA, 2004
[11] Heimbach, P.; Hill, C.; Giering, R., An efficient exact adjoint of the parallel MIT general circulation model, generated via automatic differentiation, Future generation computer systems, 21, 8, 1356-1371, (2005)
[12] Maier, M.; Naumann, U., Intraprocedural adjoint code generated by the differentiation-enabled nagware Fortran compiler, ()
[13] U. Naumann, J. Riehme, Computing adjoints with the NAGWare Fortran 95 compiler, in: [2], Springer, 2005, pp. 159-170 · Zbl 1270.65090
[14] Naumann, U.; Utke, J., Optimality-preserving elimination of linearities in Jacobian accumulation, Electronic transactions on numerical analysis, 21, 134-150, (2005), Special Volume on Combinatorial Scientific Computing · Zbl 1120.65315
[15] Naumann, U.; Utke, J., Source templates for the automatic generation of adjoint code through static call graph reversal, (), 338-346
[16] Tarjan, R.; Gilbert, J.; Lengauer, T., The pebbling problem is complete for polynomial space, SIAM J. comput. (9), 513-524, (1980) · Zbl 0456.68045
[17] Utke, J.; Lyons, A.; Naumann, U., Efficient reversal of the intraprocedural flow of control in adjoint computations, Journal of systems and software, 79, 1280-1294, (2006)
[18] A. Walther, Program reversal schedules for single- and multi-processor machines, PhD thesis, Institute of Scientific Computing, Technical University Dresden, Germany, 1999
[19] A. Walther, A. Griewank, New results on program reversals, in: [3], Springer, 2001, pp. 237-243, Chapter 28
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.