基于最小程序行为分解的模式伴随化

模式伴随是自动微分领域中的重要内容之一.基于最小程序行为分解讨论了模式伴随的基本原理和方法,为自动伴随工具的设计与实现提供了基本的理论依据.运用这种方法得到的伴随模式不仅在计算时间、空间存储开销以及代码的复杂性3个方面取得了比较理想的结果,而且在软件实现上较简单.还讨论了树形结构最小程序行为的伴随化方法.

模式伴随化的基本规则及其代价分析

从程序语法结构而不是从具体问题本身出发,提出了基于最小程序行为分解的模式伴随化方法.此方法无论在算法设计上还是在软件实现上均更具普遍性,并具有许多独特的优点.它保留了断点存储技术在减少浮点计算量和降低存储开销方面的优点,同时克服了其仅仅适用于计算过程均匀可分假设的局限性.首先给出了模式伴随化实现的基本规则,详细介绍了基于最小程序行为分解的模式伴随化方法.然后,基于自动微分(AD)基本假设定义了可分程序空间和微分代价函数,得到了两个反映计算微分代价的基本常数σ和μ.在计算过程均匀可分性假设下,讨论了断点存储在浮点计算量和空间存储开销上的最优实现,证明了深度划分在这两个方面同时具有对数复杂性的结论.最后,详细论证了基于最小程序行为分解的模式伴随化方法在浮点计算量和空间存储开销两个方面同时具有过程引用和划分深度依赖性.