{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:37:11Z","timestamp":1750307831066,"version":"3.41.0"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2008,7,22]],"date-time":"2008-07-22T00:00:00Z","timestamp":1216684800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2008,7,22]]},"abstract":"<jats:p>The source transformation tool for automatic differentiation of Fortran programs ADIFOR uses a preaccumulation technique to speed up tangent-linear codes significantly compared to the standard forward mode. Reverse mode automatic differentiation is applied to all scalar assignments to generate efficient code for the computation of local gradients. It has been well known for some time that reverse mode is not necessarily the optimal choice for the computation of these statement-level gradients as it does not minimize the number of operations required. This article presents an efficient algorithm for the solution of this combinatorial optimization problem. The corresponding software is freely available for downloading on our website. Developers of software for automatic differentiation are invited to integrate the algorithm into their tools.<\/jats:p>\n          <jats:p>Gradients of scalar multivariate functions can be computed by elimination methods on the linearized computational graph. The combinatorial optimization problem that aims to minimize the number of arithmetic operations performed by the elimination algorithm is known to be NP-complete. In this article we present a polynomial algorithm for solving a relevant subclass of this problem's instances. The proposed method relies on the ability to compute vertex covers in bipartite graphs in polynomial time. A simplified version of this graph algorithm is used in a research prototype of the differentiation-enabled NAGWare Fortran compiler for the preaccumulation of local gradients of scalar assignments in the context of automatic generation of efficient tangent-linear code for numerical programs.<\/jats:p>","DOI":"10.1145\/1377603.1377605","type":"journal-article","created":{"date-parts":[[2008,7,29]],"date-time":"2008-07-29T13:22:19Z","timestamp":1217337739000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Optimal vertex elimination in single-expression-use graphs"],"prefix":"10.1145","volume":"35","author":[{"given":"Uwe","family":"Naumann","sequence":"first","affiliation":[{"name":"RWTH Aachen University, Aachen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuxiao","family":"Hu","sequence":"additional","affiliation":[{"name":"RWTH Aachen University, Aachen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,7,25]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(83)90110-X"},{"volume-title":"Proceedings Series. SIAM.","author":"Berz M.","key":"e_1_2_1_2_1"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/99.537089"},{"volume-title":"Proceedings Series. SIAM. 82--94","author":"Bischof C.","key":"e_1_2_1_4_1"},{"volume":"50","volume-title":"Lecture Notes in Computational Science and Engineering","author":"B\u00fccker M.","key":"e_1_2_1_5_1"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Corliss G. Faure C. Griewank A. Hascoet L. and Naumann U. Eds. 2002. Automatic Differentiation of Algorithms\u2014From Simulation to Optimization. Springer Berlin Germany.   Corliss G. Faure C. Griewank A. Hascoet L. and Naumann U. Eds. 2002. Automatic Differentiation of Algorithms\u2014From Simulation to Optimization. Springer Berlin Germany.","DOI":"10.1007\/978-1-4613-0075-5"},{"volume-title":"Proceedings Series. SIAM.","author":"Corliss G.","key":"e_1_2_1_7_1"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/321694.321699"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Ford L. and Fulkerson D. 1962. Flows in Networks. Princeton University Press.  Ford L. and Fulkerson D. 1962. Flows in Networks. Princeton University Press.","DOI":"10.1515\/9781400875184"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1024074.1024076"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/293686.293695"},{"key":"e_1_2_1_12_1","volume-title":"Principles and Techniques of Algorithmic Differentiation. Frontiers in Applied Mathematics","volume":"19","author":"Griewank A.","year":"2000"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/229473.229474"},{"volume-title":"Proceedings Series. SIAM. 126--135","author":"Griewank A.","key":"e_1_2_1_14_1"},{"volume-title":"Proceedings of the International Conference on High Performance Scientific Computing (HPSC). Springer.","author":"Griewank A.","key":"e_1_2_1_15_1"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Harary F. 1969. Graph Theory. Addison-Wesley.  Harary F. 1969. Graph Theory. Addison-Wesley.","DOI":"10.21236\/AD0705364"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/0202019"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/355887.355890"},{"key":"e_1_2_1_19_1","first-page":"116","article-title":"Graphs and matrices (Hungarian)","volume":"38","author":"K\u00f6nig D.","year":"1931","journal-title":"Mat. Fiz. Lapok"},{"key":"e_1_2_1_20_1","unstructured":"Naumann U. 1999. Efficient calculation of Jacobian matrices by optimized application of the chain rule to computational graphs. Ph.D. thesis Technical University Dresden Dresden Germany.  Naumann U. 1999. Efficient calculation of Jacobian matrices by optimized application of the chain rule to computational graphs. Ph.D. thesis Technical University Dresden Dresden Germany."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-003-0456-9"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/3114201.3114717"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1114268.1114270"},{"volume":"50","volume-title":"Lecture Notes on Computational Science and Engineering","author":"Naumann U.","key":"e_1_2_1_24_1"},{"volume-title":"Automatic Differentiation: Applications, Theory, and Tools","series-title":"Lecture Notes on Computational Science and Engineering","author":"Utke J.","key":"e_1_2_1_25_1"}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1377603.1377605","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1377603.1377605","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:57:56Z","timestamp":1750255076000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1377603.1377605"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,7,22]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,7,22]]}},"alternative-id":["10.1145\/1377603.1377605"],"URL":"https:\/\/doi.org\/10.1145\/1377603.1377605","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"type":"print","value":"0098-3500"},{"type":"electronic","value":"1557-7295"}],"subject":[],"published":{"date-parts":[[2008,7,22]]},"assertion":[{"value":"2006-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2007-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-07-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}