物理学论文-自动微分转换系统及其应用.doc

物理学论文-自动微分转换系统及其应用摘要自动微分转换系统（DFT）由LASG和LSEC联合研制开发，目前已拥有成熟的版本。本文对DFT系统的功能、特色及其基本应用作了全面的介绍，并给出了一些颇具说服力的数值试验结果。同时，本文提出了统计准确率评价的概念，这对评价一类自动微分工具及其微分模式代码的可靠性与有效性提供了一种客观的尺度。最后，本文还详细讨论了运用切线性模式求解雅可比矩阵的问题，给出了求解初始输入矩阵的有效算法。关键词自动微分切线性模式数据相关分析统计准确率1.引言计算微分大致经历了从商微分，符号微分，手写代码到自动微分几个阶段。与其它几种微分方法相比，自动微分具有代码简练、计算精度高及投入人力少等优点。自动微分实现的基本出发点是：一个数据相对独立的程序对象（模式、过程、程序段、数值语句乃至数值表达式），无论多么复杂，总可以分解为一系列有限数目的基本函数（如sin、exp、log）和基本运算操作（加、减、乘、除、乘方）的有序复合；对所有这些基本函数及基本运算操作，重复使用链式求导法则，将得到的中间结果自上而下地做正向积分就可以建立起对应的切线性模式，而自下而上地做反向积分就可以建立起对应的伴随模式1。基于自动微分方法得到的切线性模式和伴随模式，在变分资料同化2、系统建模与参数辨识3、参数的敏感性分析4、非线性最优化以及数值模式的可预测性分析5等问题中有着十分广泛的应用。迄今为止，已有数十所大学和研究所各自开发了能够用于求解切线性模式的自动微分系统，比较典型的有TAMC系统6、ADJIFOR系统7和ODYSSEE系统8。在一些特定的运用中，它们都是比较成功的，但在通用性和复杂问题的处理效率上还存在许多不足。通常，自动生成切线性模式的关键难题在于对象自身的强相关性，这给系统全局分析（如数据IO相关分析和数据依赖相关分析）和微分代码的整体优化都带来了很多困难。同时，对于程序对象不可导处的准确识别和微分处理，至今仍还没有一个统一而有效的算法。另外，最优或有效求解稀疏雅可比矩阵一直是衡量一个自动微分系统有效性的重要尺度。统计准确率被我们视为评价一类自动微分工具及其微分模式代码可靠性与有效性的重要尺度。其基本假设是：如果对于定义域空间内随机抽样获得的至多有限个n维初始场（或网格点），微分模式输出的差分和微分逼近是成功的；那么对于定义域空间内所有可能初始场（或网格点），微分模式输出的差分和微分逼近都是成功的。微分模式统计准确率评价的具体方法是：在所有随机抽样得到的初始场（或网格点）附近，当输入扰动逐渐趋向于机器有效精度所能表示的最小正值时，模式输出的差分和微分之间应该有足够精度有效位数上的逼近。DFT系统具有许多优点，它能够完全接受用FORTRAN77语言编写的源代码，微分代码结构清晰，其微分处理能力与问题和对象的规模及复杂性无关。它基于YACC实现，具有很强的可扩展性。DFT系统具有四个重要特色。它通过对象全局依赖相关分析，准确求解雅可比矩阵的稀疏结构，自动计算有效初始输入矩阵，从而可以用较小的代价求得整个雅可比矩阵。同时，它可以自动生成客观评价微分模式效率与可靠性的测试程序，对奇异函数做等价微分处理，并采用二元归约的方法，在语句级层次上实现微分代码优化。2.系统概况DFT系统主要由两部分组成：微分代码转换和微分代码评价，图2.1。微分代码转换部分接受用户输入指令并自动分析对象模式，生成切线性模式代码及其相关测试代码，后者直接构成微分代码评价系统的主体。微分代码评价是DFT系统的一个重要特色。DFT系统的开发小组认为，一个微分模式如果在可靠性、时间和存储效率上没有得到充分的验证，至少对实际应用而言，它将是毫无意义的。原模式切线性模式统计评价结果图2.1DFT系统结构简图2.1微分代码转换DFT系统是基于YACC在UNIX环境下开发的，其结构图2.2所示。通过DFT系统产生的切线性模式代码成对出现，并在语句级程度上做了简化，可读性很强，如图2.4。切线性模式评价函数集图2.2微分代码转换微分代码转换部分从功能上分为四个部分：词法分析，语义分析，对象复杂性及数据相关分析和微分代码转换。对于一组具有复杂数据相关的程序模式对象，通常需要系统运行两遍才能得到有效而可靠的微分代码。这主要有两方面的考虑：其一，根据对象的复杂性（如最大语句长度、最大变量维数、子过程或函数数目、子过程或函数内最大变量数目等对象特征）选择合适的系统参数以求最优的运行代价；其二，模式内各子过程或函数之间以及一个子过程或函数内往往具有很强的数据相关性，需要事先保存对象的相关信息并且在考虑当前对象的属性之前必须做上下文相关分析。图2.3PERIGEE源程序代码图2.4DFT系统生成的切线性代码2.2微分代码评价通常，评价一个编译系统的性能有很多方面，如处理速度、结果代码可靠性及质量、出错诊断、可扩展和可维护性等。对于一类自动微分系统来说，由于软件开发人力的局限以及对象模式的复杂多样性,通过自动转换得到的微分模式并非常常是有效而可靠的（即无论是在数学意义上还是在程序逻辑上应与期待的理想结果一致），因而在微分模式被投入实际应用前，往往需要投入一定的人力来对其做严格的分析测试。对切线性模式做统计评价测试的主要内容可以简单叙述为：在网格化的模式定义域空间内，选择所有可能的网格点形成微分模式计算的初始场；在不同的网格点附近，随机选取至少个线性无关的初始扰动，对每个扰动输入分别进行网格点逼近，统计考察模式输出差分和微分在有效位数上的逼近程度。图2.5描述了整个测试过程，它包含网格点数据随机采样（1）和网格点数据逼近（2）两级循环。图2.5切线性模式代码的测试过程3.系统主要特色DFT系统并不是一个完整的FORTRAN编译器，但它几乎可以接受和处理所有FORTRAN77编写的源模式代码，并且可以很方便地扩展并接受FORTRAN90编写的源模式代码。本节将着重介绍DFT系统（版本3.0）的以下几个重要特色。3.1结构化的微分实现DFT系统采用标准化的代码实现，切线性模式的扰动变量和基态值变量、微分计算语句和基态值计算语句总是成对出现，并具有清晰的程序结构。微分代码保持了原模式本身的结构和风格（如并行和向量特性、数据精度等），即语句到语句、结构到结构的微分实现。在奇异点或不可导处，DFT系统对微分扰动采取简单的清零处理，实践证明这对抑制扰动计算溢出具有重要意义，但并不影响评价测试结果。3.2全局数据相关分析DFT系统具有较强的数据相关分析能力，它包括全局数据IO相关分析、全局数据依赖相关分析、全局过程相关分析以及数据迭代相关分析几个不同方面。数据依赖相关与数据IO相关关系密切，但又存在根本不同。前者强调每个变量在数学关系上的依赖性；而后者描述了一个对象的输入输出特性，且具有相对性，即任何一个变量参数，无论它是独立变量还是依赖变量，在数学意义上都可等价为一个既是输入又是输出的参数来处理。DFT系统记录所有过程参数的IO属性表，通过深度递归相关计算，准确计算每个过程参数的最终IO属性。DFT系统通过对数据相关矩阵做模二和及自乘迭代计算（An+1=AnAn2）来完成数据的依赖相关分析，这种算法具有很好的对数收敛特性。DFT系统通过全局过程相关分析的结果，自动生成模式的局部或整体相关引用树结构（如图3.1），这对用户分析复杂数值模式和微分评价测试都具有很好的指导作用。DFT系统还具有分析局部数据迭代相关和函数迭代相关的能力，这两种形式的数据迭代相关是自动微分实现颇具挑战的难题之一。图3.1GPSRayshooting模式的相关树结构片段3.3自动生成测试程序基于IO相关分析的结果，DFT系统自动生成微分测试代码，分别对切线性模式的可靠性和运行代价做统计评价测试。特别地，DFT系统还可将任何模式参数都视为输入输出参数，生成在数学意义上等价的测试代码，这样处理的不利之处在于往往需要极高的存储开销。3.4基于语句级的代码优化目前，DFT系统仅仅具备局地优化能力。在语句级微分实现上采用二元归约的方法对微分代码进行优化是DFT系统的一个重要特色。根据右端表达式的乘法复杂性及含变元数目的不同，DFT系统采取不同的分解策略。二元归约的方法避免了微分计算中的许多冗余计算，在一些复杂的非线性表达式的微分计算中具有最小的计算代价，同时也非常适合于微分系统的软件实现。同时，对于某些特殊的运算操作（除法、乘方）和特殊函数（如sqrt、exp），DFT系统较好地利用了基态值计算得到的中间结果，避免了微分实现中的冗余计算。4.系统应用运用自动微分工具得到的切线性模式，可以在无截断误差意义下求解函数的数值微分