Optimal vertex elimination in single-expression-use graphs
Optimal vertex elimination in single-expression-use graphs
复制标题
单表达式使用图中的最佳顶点消除
DOI：
10.1145/1377603.1377605
复制
发表时间：
2008
影响因子：
2.7
通讯作者：
Naumann U
中科院分区：
文献类型：
--
作者：
Naumann U
用于Fortran程序自动微分的源转换工具ADIFOR使用预累积技术，与标准前向模式相比，可以显著加快切线线性代码的速度。反向模式自动微分应用于所有标量分配，以生成用于计算局部梯度的有效代码。众所周知，反向模式不一定是计算这些语句级梯度的最佳选择，因为它不能最小化所需的操作数量。本文提出了一种有效的算法来解决这个组合优化问题。相应的软件可在我们的网站上免费下载。自动微分软件的开发者可以将该算法集成到他们的工具中，在线性化的计算图上用消元法计算标量多元函数的导数。组合优化问题的目标是最小化的算术运算的数量进行的消除算法是已知的NP-完全。在这篇文章中，我们提出了一个多项式算法来解决这个问题的实例的相关子类。所提出的方法依赖于在多项式时间内计算二分图中的顶点覆盖的能力。这个图算法的简化版本中使用的差分启用NAGWare Fortran编译器的研究原型的局部梯度的标量分配的上下文中的自动生成高效的切线线性代码的数值程序的预积累。
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.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.
登录
查看更多内容
DOI：
--
发表时间：
2005
期刊：
影响因子：
--
作者：
U. Naumann
通讯作者：
U. Naumann
影响因子：
2.7
作者：
U. Naumann
通讯作者：
U. Naumann
通过源变换和顶点消除生成的雅可比代码可以与手工编码一样高效
DOI：
--
发表时间：
2004
期刊：
TOMS
影响因子：
--
作者：
S. Forth;E. Tadjouddine;J. Pryce;J. Reid
通讯作者：
J. Reid
雅可比稀缺性的分析与利用
DOI：
--
发表时间：
2003
期刊：
International Conference on High Performance Scientific Computing
影响因子：
--
作者：
A. Griewank;Olaf Vogel
通讯作者：
Olaf Vogel
自动微分：应用、理论和实现（计算科学与工程讲义）
DOI：
--
发表时间：
2006
期刊：
影响因子：
--
作者：
Martin Bücker;G. Corliss;P. Hovland;U. Naumann;Boyana Norris
通讯作者：
Boyana Norris