{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,11]],"date-time":"2026-02-11T13:02:12Z","timestamp":1770814932306,"version":"3.50.1"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2006,10,21]],"date-time":"2006-10-21T00:00:00Z","timestamp":1161388800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2007,11,30]]},"DOI":"10.1007\/s10107-006-0042-z","type":"journal-article","created":{"date-parts":[[2006,10,20]],"date-time":"2006-10-20T03:41:26Z","timestamp":1161315686000},"page":"427-441","source":"Crossref","is-referenced-by-count":25,"title":["Optimal Jacobian accumulation is NP-complete"],"prefix":"10.1007","volume":"112","author":[{"given":"Uwe","family":"Naumann","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2006,10,21]]},"reference":[{"key":"42_CR1","unstructured":"Personal communication with Steihaug, T. Bergen University, Norway, and Griewank, A. at Humboldt University Berlin (2005)"},{"key":"42_CR2","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/0304-3975(83)90110-X","volume":"22","author":"W. Baur","year":"1983","unstructured":"Baur W., Strassen V. (1983) The complexity of partial derivatives. Theoret. Comput. Sci. 22, 317\u2013330","journal-title":"Theoret. Comput. Sci."},{"key":"42_CR3","unstructured":"Berz, M., Bischof, C., Corliss, G., Griewank, A. (eds.) Computational differentiation: techniques, applications, and tools. In: Proceedings Series. SIAM Philadelphia (1996)"},{"key":"42_CR4","unstructured":"Bischof, C., Haghighat, M.: Hierarchical approaches to automatic differentiation. In: [3], pp. 82\u201394"},{"key":"42_CR5","doi-asserted-by":"crossref","unstructured":"B\u00fccker, 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)","DOI":"10.1007\/3-540-28438-9"},{"key":"42_CR6","volume-title":"Automatic Differentiation of Algorithms \u2013 From Simulation to Optimization","year":"2002","unstructured":"Corliss G., Faure C., Griewank A., Hasco\u00ebt L., Naumann U. (eds) (2002) Automatic Differentiation of Algorithms \u2013 From Simulation to Optimization. Springer, Berlin Heidelberg New York"},{"key":"42_CR7","unstructured":"Corliss, G., Griewank, A. (eds.) Automatic Differentiation: Theory, Implementation, and Application. Proceedings Series. SIAM Philadelphia (1991)"},{"key":"42_CR8","volume-title":"Computers and Intractability \u2013 A Guide to the Theory of NP-completeness","author":"M. Garey","year":"1979","unstructured":"Garey M., Johnson D. (1979) Computers and Intractability \u2013 A Guide to the Theory of NP-completeness. W. H. Freeman and Company, San Francisco"},{"key":"42_CR9","doi-asserted-by":"crossref","unstructured":"Giering, R., Kaminski, T.: Applying TAF to generate efficient derivative code of Fortran 77-95 programs. In: Proceedings of GAMM 2002, Augsburg, Germany (2002)","DOI":"10.1002\/pamm.200310014"},{"key":"42_CR10","volume-title":"Evaluating derivatives. Principles and techniques of algorithmic differentiation Frontiers in Applied Mathematics. vol 19.","author":"A. Griewank","year":"2000","unstructured":"Griewank A. (2000) Evaluating derivatives. Principles and techniques of algorithmic differentiation Frontiers in Applied Mathematics, vol 19. SIAM, Philadelphia"},{"issue":"2","key":"42_CR11","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1145\/229473.229474","volume":"22","author":"A. Griewank","year":"1996","unstructured":"Griewank A., Juedes D., Utke J. (1996) ADOL\u2013C, a package for the automatic differentiation of algorithms written in C\/C++. ACM Trans. Math. Softw. 22(2): 131\u2013167","journal-title":"ACM Trans. Math. Softw."},{"issue":"95","key":"42_CR12","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1007\/s10107-002-0329-7","volume":"3","author":"A. Griewank","year":"2003","unstructured":"Griewank A., Naumann U. (2003) Accumulating Jacobians as chained sparse matrix products. Math. Prog. 3(95): 555\u2013571","journal-title":"Math. Prog."},{"key":"42_CR13","unstructured":"Griewank, A., Reese, S.: On the calculation of Jacobian matrices by the Markovitz rule. In: [7], pp. 126\u2013135"},{"key":"42_CR14","unstructured":"Griewank, A., Vogel, O.: Analysis and exploitation of Jacobian scarcity. In: Proceedings of HPSC Hanoi. Springer, Berlin Heidelberg New York (2003)"},{"key":"42_CR15","unstructured":"Hasco\u00ebt, L., Pascual, V.: Tapenade 2.1 user\u2019s guide. Technical report 300, INRIA (2004)"},{"key":"42_CR16","volume-title":"Scientific Computing. An Introductory Survey.","author":"M. Heath","year":"1998","unstructured":"Heath M. (1998) Scientific Computing. An Introductory Survey. McGraw-Hill, New York"},{"key":"42_CR17","doi-asserted-by":"crossref","unstructured":"Kelley, C.: Solving Nonlinear Equations with Newton\u2019s Method. SIAM Philadelphia (2003)","DOI":"10.1137\/1.9780898718898"},{"key":"42_CR18","doi-asserted-by":"crossref","unstructured":"Naumann, U.: Elimination techniques for cheap Jacobians. In: [6], chap. 29, pp. 247\u2013253 (2001)","DOI":"10.1007\/978-1-4613-0075-5_29"},{"issue":"3","key":"42_CR19","doi-asserted-by":"crossref","first-page":"660","DOI":"10.1137\/S1052623400368394","volume":"13","author":"U. Naumann","year":"2002","unstructured":"Naumann U. (2002) Cheaper Jacobians by simulated annealing. SIAM J. Opt. 13(3): 660\u2013674","journal-title":"SIAM J. Opt."},{"issue":"99","key":"42_CR20","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1007\/s10107-003-0456-9","volume":"3","author":"U. Naumann","year":"2004","unstructured":"Naumann U. (2004) Optimal accumulation of Jacobian matrices by elimination methods on the dual computational graph. Math. Prog. 3(99): 399\u2013421","journal-title":"Math. Prog."},{"key":"42_CR21","first-page":"134","volume":"21","author":"U. Naumann","year":"2005","unstructured":"Naumann U., Utke J. (2005) Optimality-preserving elimination of linearities in Jacobian accumulation. Electron. Trans. Numer. Anal. (ETNA) 21, 134\u2013150","journal-title":"Electron. Trans. Numer. Anal. (ETNA)"},{"key":"42_CR22","unstructured":"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)"},{"key":"42_CR23","doi-asserted-by":"crossref","unstructured":"Speelpenning, B.: Compiling fast partial derivatives of functions given by algorithms. Ph.D. Thesis, University of Chicago (1980)","DOI":"10.2172\/5254402"},{"key":"42_CR24","unstructured":"Walther, A.: Program reversal schedules for single- and multi-processor machines. Ph.D. Thesis, Institute of Scientific Computing, Technical University Dresden (1999)"},{"key":"42_CR25","doi-asserted-by":"crossref","unstructured":"Walther, A., Griewank, A.: New results on program reversals. In: [6], chapt. 28, pp. 237\u2013243. Springer, Berlin Heidelberg New York (2001)","DOI":"10.1007\/978-1-4613-0075-5_28"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-006-0042-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-006-0042-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-006-0042-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T05:50:01Z","timestamp":1559109001000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-006-0042-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,10,21]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2007,11,30]]}},"alternative-id":["42"],"URL":"https:\/\/doi.org\/10.1007\/s10107-006-0042-z","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,10,21]]}}}