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

作　　者：程强[1] 张林波[1] 王斌[2] 

机构地区：[1]中国科学院计算数学与科学工程计算研究所科学与工程计算国家重点实验室(LSEC),北京100080 [2]中国科学院大气物理研究所大气科学和地球流体力学国家重点实验室(LASG),北京100029

出　　处：《中国科学（E辑）》2004年第6期601-618,共18页Science in China(Series E)

基　　金：国家杰出青年科学基金(49825109);国家重点基础研究发展规划(G2839200;G1999032805;G1999032801);中国科学院重要创新方向(KZCXZ 2-208)资助项目

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

关 键 词：模式伴随化 代价分析 自动微分 最小程序行为 浮点计算 程序语法结构 

分 类 号：TB112[理学—数学]