×

zbMATH — the first resource for mathematics

Optimal Jacobian accumulation is NP-complete. (English) Zbl 1158.68013
Summary: We show that the problem of accumulating Jacobian matrices by using a minimal number of floating-point operations is NP-complete by reduction from ensemble computation. The proof makes use of the fact that, deviating from the state-of-the-art assumption, algebraic dependences can exist between the local partial derivatives. It follows immediately that the same problem for directional derivatives, adjoints, and higher derivatives is NP-complete, too.

MSC:
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
65D25 Numerical differentiation
Software:
ADOL-C; TAF; TAPENADE
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Personal communication with Steihaug, T. Bergen University, Norway, and Griewank, A. at Humboldt University Berlin (2005)
[2] Baur W., Strassen V. (1983) The complexity of partial derivatives. Theoret. Comput. Sci. 22, 317–330 · Zbl 0498.68028 · doi:10.1016/0304-3975(83)90110-X
[3] Berz, M., Bischof, C., Corliss, G., Griewank, A. (eds.) Computational differentiation: techniques, applications, and tools. In: Proceedings Series. SIAM Philadelphia (1996) · Zbl 0857.00033
[4] Bischof, C., Haghighat, M.: Hierarchical approaches to automatic differentiation. In: [3], pp. 82–94 · Zbl 0874.65012
[5] Bücker, M., Corliss, G., Hovland, P., Naumann, U., Norris, B. (eds.) Automatic Differentiation: Applications, Theory, and Tools. Lecture Notes in Computational Science and Engineering, vol. 50. Springer, Berlin Heidelberg New York (2005) · Zbl 1084.65002
[6] Corliss G., Faure C., Griewank A., Hascoët L., Naumann U. (eds) (2002) Automatic Differentiation of Algorithms – From Simulation to Optimization. Springer, Berlin Heidelberg New York
[7] Corliss, G., Griewank, A. (eds.) Automatic Differentiation: Theory, Implementation, and Application. Proceedings Series. SIAM Philadelphia (1991) · Zbl 0747.00030
[8] Garey M., Johnson D. (1979) Computers and Intractability – A Guide to the Theory of NP-completeness. W. H. Freeman and Company, San Francisco · Zbl 0411.68039
[9] Giering, R., Kaminski, T.: Applying TAF to generate efficient derivative code of Fortran 77-95 programs. In: Proceedings of GAMM 2002, Augsburg, Germany (2002)
[10] Griewank A. (2000) Evaluating derivatives. Principles and techniques of algorithmic differentiation Frontiers in Applied Mathematics, vol 19. SIAM, Philadelphia · Zbl 0958.65028
[11] Griewank A., Juedes D., Utke J. (1996) ADOL–C, a package for the automatic differentiation of algorithms written in C/C++. ACM Trans. Math. Softw. 22(2): 131–167 · Zbl 0884.65015 · doi:10.1145/229473.229474
[12] Griewank A., Naumann U. (2003) Accumulating Jacobians as chained sparse matrix products. Math. Prog. 3(95): 555–571 · Zbl 1023.90053 · doi:10.1007/s10107-002-0329-7
[13] Griewank, A., Reese, S.: On the calculation of Jacobian matrices by the Markovitz rule. In: [7], pp. 126–135 · Zbl 0782.65027
[14] Griewank, A., Vogel, O.: Analysis and exploitation of Jacobian scarcity. In: Proceedings of HPSC Hanoi. Springer, Berlin Heidelberg New York (2003) · Zbl 1065.65069
[15] Hascoët, L., Pascual, V.: Tapenade 2.1 user’s guide. Technical report 300, INRIA (2004)
[16] Heath M. (1998) Scientific Computing. An Introductory Survey. McGraw-Hill, New York · Zbl 0903.68072
[17] Kelley, C.: Solving Nonlinear Equations with Newton’s Method. SIAM Philadelphia (2003) · Zbl 1031.65069
[18] Naumann, U.: Elimination techniques for cheap Jacobians. In: [6], chap. 29, pp. 247–253 (2001)
[19] Naumann U. (2002) Cheaper Jacobians by simulated annealing. SIAM J. Opt. 13(3): 660–674 · Zbl 1055.90092 · doi:10.1137/S1052623400368394
[20] Naumann U. (2004) Optimal accumulation of Jacobian matrices by elimination methods on the dual computational graph. Math. Prog. 3(99): 399–421 · Zbl 1070.90108 · doi:10.1007/s10107-003-0456-9
[21] Naumann U., Utke J. (2005) Optimality-preserving elimination of linearities in Jacobian accumulation. Electron. Trans. Numer. Anal. (ETNA) 21, 134–150 · Zbl 1120.65315
[22] Naumann, U., Utke, J., Wunsch, C., Hill, C., Heimbach, P., Fagan, M., Tallent, N., Strout, M.: Adjoint code by source transformation with open ad/f. In: Proceedings of the European Conference on Computational Fluid Dynamics (ECCOMAS CFD 2006). TU Delft (2006) · Zbl 1291.65140
[23] Speelpenning, B.: Compiling fast partial derivatives of functions given by algorithms. Ph.D. Thesis, University of Chicago (1980)
[24] Walther, A.: Program reversal schedules for single- and multi-processor machines. Ph.D. Thesis, Institute of Scientific Computing, Technical University Dresden (1999)
[25] Walther, A., Griewank, A.: New results on program reversals. In: [6], chapt. 28, pp. 237–243. Springer, Berlin Heidelberg New York (2001)
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.