Jacobian code generated by source transformation and vertex elimination can be as efficient as hand-coding
Jacobian code generated by source transformation and vertex elimination can be as efficient as hand-coding
复制标题
通过源变换和顶点消除生成的雅可比代码可以与手工编码一样高效
DOI：
--
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
J. Reid
中科院分区：
文献类型：
--
作者：
S. Forth;E. Tadjouddine;J. Pryce;J. Reid
本文介绍了Eliad的第一组扩展结果，Eliad是一个源转化实现的基础 - 淘汰自动分化方法，用于计算Fortran Code（Griewank和Reese）（Griewank和Reese，算法自动差异）定义的函数的Jacobians：理论，实施，实施，以及实施，以及实施，以及实施，以及实施，以及应用，1991年，第126--135页）。我们介绍了必要的理论，该理论是针对用于线性的扩展雅各布系统的数值线性代数的众所周知的算法，该算法规定了功能代码中所有变量的衍生物之间的关系。使用示例，我们强调了顶点淘汰数值不稳定性的潜力。我们描述了我们工具Eliad的源转换实施，并从五个测试用例中提出了结果，其中四个摘自Minpack-2集合（Averick等人，报告ANL/MCS-TM-150，1992），并为此提供了手。可以使用编码的Jacobian代码。在五个计算机/编译器平台上，我们表明EliaD获得的Jacobian代码与手工编码的Jacobian代码一样有效。它的效率也比当前的最先进的状态（自动分化工具）高2到20倍，即使使用了这些工具，也使用了稀疏的雅各布压缩技术。我们证明了从一度使用的所有中间变量的（连续更新）扩展的Jacobian系统（连续更新的）扩展的雅各布系统的反向预淘汰的有效性。此后，单调前进/反向排序消除所有其他中间体的效率非常有效。在一个测试案例中，由Markowitz或相关VLR启发式方法确定的订单发现优越。发现Jacobian代码的陈述的重新排序，目的是减少从缓存到寄存器的数据的读取和写入，但被发现具有不同的效果，但可能非常有益。
This article presents the first extended set of results from EliAD, a source-transformation implementation of the vertex-elimination Automatic Differentiation approach to calculating the Jacobians of functions defined by Fortran code (Griewank and Reese, Automatic Differentiation of Algorithms: Theory, Implementation, and Application, 1991, pp. 126--135). We introduce the necessary theory in terms of well known algorithms of numerical linear algebra applied to the linear, extended Jacobian system that prescribes the relationship between the derivatives of all variables in the function code. Using an example, we highlight the potential for numerical instability in vertex-elimination. We describe the source transformation implementation of our tool EliAD and present results from five test cases, four of which are taken from the MINPACK-2 collection (Averick et al, Report ANL/MCS-TM-150, 1992) and for which hand-coded Jacobian codes are available. On five computer/compiler platforms, we show that the Jacobian code obtained by EliAD is as efficient as hand-coded Jacobian code. It is also between 2 to 20 times more efficient than that produced by current, state of the art, Automatic Differentiation tools even when such tools make use of sophisticated techniques such as sparse Jacobian compression. We demonstrate the effectiveness of reverse-ordered pre-elimination from the (successively updated) extended Jacobian system of all intermediate variables used once. Thereafter, the monotonic forward/reverse ordered eliminations of all other intermediates is shown to be very efficient. On only one test case were orderings determined by the Markowitz or related VLR heuristics found superior. A re-ordering of the statements of the Jacobian code, with the aim of reducing reads and writes of data from cache to registers, was found to have mixed effects but could be very beneficial.