Optimal accumulation of Jacobian matrices by elimination methods on the dual computational graph

• 成果类型: Article
• 署名作者: Naumann, U
• 署名单位: United States Department of Energy (DOE); Argonne National Laboratory
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-003-0456-9
• 发表日期: 2004
• 页码: 399-421
• 关键词: vertex-elimination

摘要

The accumulation of the Jacobian matrix F' of a vector function F : R-n --> R-m can be regarded as a transformation of its linearized computational graph into a subgraph of the directed complete bipartite graph K-n,K-m. This transformation can be performed by applying different elimination techniques that may lead to varying costs for computing F'. This paper introduces face elimination as the basic technique for accumulating Jacobian matrices by using a minimal number of arithmetic operations. Its Superiority over both edge and vertex elimination methods is shown. The intention is to establish the conceptual basis for the ongoing development of algorithms for optimizing the computation of Jacobian matrices.