物理學(xué)論文-自動(dòng)微分轉(zhuǎn)換系統(tǒng)及其應(yīng)用.doc

物理學(xué)論文-自動(dòng)微分轉(zhuǎn)換系統(tǒng)及其應(yīng)用摘要自動(dòng)微分轉(zhuǎn)換系統(tǒng)（DFT）由LASG和LSEC聯(lián)合研制開發(fā)，目前已擁有成熟的版本。本文對DFT系統(tǒng)的功能、特色及其基本應(yīng)用作了全面的介紹，并給出了一些頗具說服力的數(shù)值試驗(yàn)結(jié)果。同時(shí)，本文提出了統(tǒng)計(jì)準(zhǔn)確率評(píng)價(jià)的概念，這對評(píng)價(jià)一類自動(dòng)微分工具及其微分模式代碼的可靠性與有效性提供了一種客觀的尺度。最后，本文還詳細(xì)討論了運(yùn)用切線性模式求解雅可比矩陣的問題，給出了求解初始輸入矩陣的有效算法。關(guān)鍵詞自動(dòng)微分切線性模式數(shù)據(jù)相關(guān)分析統(tǒng)計(jì)準(zhǔn)確率1.引言計(jì)算微分大致經(jīng)歷了從商微分，符號(hào)微分，手寫代碼到自動(dòng)微分幾個(gè)階段。與其它幾種微分方法相比，自動(dòng)微分具有代碼簡練、計(jì)算精度高及投入人力少等優(yōu)點(diǎn)。自動(dòng)微分實(shí)現(xiàn)的基本出發(fā)點(diǎn)是：一個(gè)數(shù)據(jù)相對獨(dú)立的程序?qū)ο螅Ｊ?、過程、程序段、數(shù)值語句乃至數(shù)值表達(dá)式），無論多么復(fù)雜，總可以分解為一系列有限數(shù)目的基本函數(shù)（如sin、exp、log）和基本運(yùn)算操作（加、減、乘、除、乘方）的有序復(fù)合；對所有這些基本函數(shù)及基本運(yùn)算操作，重復(fù)使用鏈?zhǔn)角髮?dǎo)法則，將得到的中間結(jié)果自上而下地做正向積分就可以建立起對應(yīng)的切線性模式，而自下而上地做反向積分就可以建立起對應(yīng)的伴隨模式1?；谧詣?dòng)微分方法得到的切線性模式和伴隨模式，在變分資料同化2、系統(tǒng)建模與參數(shù)辨識(shí)3、參數(shù)的敏感性分析4、非線性最優(yōu)化以及數(shù)值模式的可預(yù)測性分析5等問題中有著十分廣泛的應(yīng)用。迄今為止，已有數(shù)十所大學(xué)和研究所各自開發(fā)了能夠用于求解切線性模式的自動(dòng)微分系統(tǒng)，比較典型的有TAMC系統(tǒng)6、ADJIFOR系統(tǒng)7和ODYSSEE系統(tǒng)8。在一些特定的運(yùn)用中，它們都是比較成功的，但在通用性和復(fù)雜問題的處理效率上還存在許多不足。通常，自動(dòng)生成切線性模式的關(guān)鍵難題在于對象自身的強(qiáng)相關(guān)性，這給系統(tǒng)全局分析（如數(shù)據(jù)IO相關(guān)分析和數(shù)據(jù)依賴相關(guān)分析）和微分代碼的整體優(yōu)化都帶來了很多困難。同時(shí)，對于程序?qū)ο蟛豢蓪?dǎo)處的準(zhǔn)確識(shí)別和微分處理，至今仍還沒有一個(gè)統(tǒng)一而有效的算法。另外，最優(yōu)或有效求解稀疏雅可比矩陣一直是衡量一個(gè)自動(dòng)微分系統(tǒng)有效性的重要尺度。統(tǒng)計(jì)準(zhǔn)確率被我們視為評(píng)價(jià)一類自動(dòng)微分工具及其微分模式代碼可靠性與有效性的重要尺度。其基本假設(shè)是：如果對于定義域空間內(nèi)隨機(jī)抽樣獲得的至多有限個(gè)n維初始場（或網(wǎng)格點(diǎn)），微分模式輸出的差分和微分逼近是成功的；那么對于定義域空間內(nèi)所有可能初始場（或網(wǎng)格點(diǎn)），微分模式輸出的差分和微分逼近都是成功的。微分模式統(tǒng)計(jì)準(zhǔn)確率評(píng)價(jià)的具體方法是：在所有隨機(jī)抽樣得到的初始場（或網(wǎng)格點(diǎn)）附近，當(dāng)輸入擾動(dòng)逐漸趨向于機(jī)器有效精度所能表示的最小正值時(shí)，模式輸出的差分和微分之間應(yīng)該有足夠精度有效位數(shù)上的逼近。DFT系統(tǒng)具有許多優(yōu)點(diǎn)，它能夠完全接受用FORTRAN77語言編寫的源代碼，微分代碼結(jié)構(gòu)清晰，其微分處理能力與問題和對象的規(guī)模及復(fù)雜性無關(guān)。它基于YACC實(shí)現(xiàn)，具有很強(qiáng)的可擴(kuò)展性。DFT系統(tǒng)具有四個(gè)重要特色。它通過對象全局依賴相關(guān)分析，準(zhǔn)確求解雅可比矩陣的稀疏結(jié)構(gòu)，自動(dòng)計(jì)算有效初始輸入矩陣，從而可以用較小的代價(jià)求得整個(gè)雅可比矩陣。同時(shí)，它可以自動(dòng)生成客觀評(píng)價(jià)微分模式效率與可靠性的測試程序，對奇異函數(shù)做等價(jià)微分處理，并采用二元?dú)w約的方法，在語句級(jí)層次上實(shí)現(xiàn)微分代碼優(yōu)化。2.系統(tǒng)概況DFT系統(tǒng)主要由兩部分組成：微分代碼轉(zhuǎn)換和微分代碼評(píng)價(jià)，圖2.1。微分代碼轉(zhuǎn)換部分接受用戶輸入指令并自動(dòng)分析對象模式，生成切線性模式代碼及其相關(guān)測試代碼，后者直接構(gòu)成微分代碼評(píng)價(jià)系統(tǒng)的主體。微分代碼評(píng)價(jià)是DFT系統(tǒng)的一個(gè)重要特色。DFT系統(tǒng)的開發(fā)小組認(rèn)為，一個(gè)微分模式如果在可靠性、時(shí)間和存儲(chǔ)效率上沒有得到充分的驗(yàn)證，至少對實(shí)際應(yīng)用而言，它將是毫無意義的。原模式切線性模式統(tǒng)計(jì)評(píng)價(jià)結(jié)果圖2.1DFT系統(tǒng)結(jié)構(gòu)簡圖2.1微分代碼轉(zhuǎn)換DFT系統(tǒng)是基于YACC在UNIX環(huán)境下開發(fā)的，其結(jié)構(gòu)圖2.2所示。通過DFT系統(tǒng)產(chǎn)生的切線性模式代碼成對出現(xiàn)，并在語句級(jí)程度上做了簡化，可讀性很強(qiáng)，如圖2.4。切線性模式評(píng)價(jià)函數(shù)集圖2.2微分代碼轉(zhuǎn)換微分代碼轉(zhuǎn)換部分從功能上分為四個(gè)部分：詞法分析，語義分析，對象復(fù)雜性及數(shù)據(jù)相關(guān)分析和微分代碼轉(zhuǎn)換。對于一組具有復(fù)雜數(shù)據(jù)相關(guān)的程序模式對象，通常需要系統(tǒng)運(yùn)行兩遍才能得到有效而可靠的微分代碼。這主要有兩方面的考慮：其一，根據(jù)對象的復(fù)雜性（如最大語句長度、最大變量維數(shù)、子過程或函數(shù)數(shù)目、子過程或函數(shù)內(nèi)最大變量數(shù)目等對象特征）選擇合適的系統(tǒng)參數(shù)以求最優(yōu)的運(yùn)行代價(jià)；其二，模式內(nèi)各子過程或函數(shù)之間以及一個(gè)子過程或函數(shù)內(nèi)往往具有很強(qiáng)的數(shù)據(jù)相關(guān)性，需要事先保存對象的相關(guān)信息并且在考慮當(dāng)前對象的屬性之前必須做上下文相關(guān)分析。圖2.3PERIGEE源程序代碼圖2.4DFT系統(tǒng)生成的切線性代碼2.2微分代碼評(píng)價(jià)通常，評(píng)價(jià)一個(gè)編譯系統(tǒng)的性能有很多方面，如處理速度、結(jié)果代碼可靠性及質(zhì)量、出錯(cuò)診斷、可擴(kuò)展和可維護(hù)性等。對于一類自動(dòng)微分系統(tǒng)來說，由于軟件開發(fā)人力的局限以及對象模式的復(fù)雜多樣性,通過自動(dòng)轉(zhuǎn)換得到的微分模式并非常常是有效而可靠的（即無論是在數(shù)學(xué)意義上還是在程序邏輯上應(yīng)與期待的理想結(jié)果一致），因而在微分模式被投入實(shí)際應(yīng)用前，往往需要投入一定的人力來對其做嚴(yán)格的分析測試。對切線性模式做統(tǒng)計(jì)評(píng)價(jià)測試的主要內(nèi)容可以簡單敘述為：在網(wǎng)格化的模式定義域空間內(nèi)，選擇所有可能的網(wǎng)格點(diǎn)形成微分模式計(jì)算的初始場；在不同的網(wǎng)格點(diǎn)附近，隨機(jī)選取至少個(gè)線性無關(guān)的初始擾動(dòng)，對每個(gè)擾動(dòng)輸入分別進(jìn)行網(wǎng)格點(diǎn)逼近，統(tǒng)計(jì)考察模式輸出差分和微分在有效位數(shù)上的逼近程度。圖2.5描述了整個(gè)測試過程，它包含網(wǎng)格點(diǎn)數(shù)據(jù)隨機(jī)采樣（1）和網(wǎng)格點(diǎn)數(shù)據(jù)逼近（2）兩級(jí)循環(huán)。圖2.5切線性模式代碼的測試過程3.系統(tǒng)主要特色DFT系統(tǒng)并不是一個(gè)完整的FORTRAN編譯器，但它幾乎可以接受和處理所有FORTRAN77編寫的源模式代碼，并且可以很方便地?cái)U(kuò)展并接受FORTRAN90編寫的源模式代碼。本節(jié)將著重介紹DFT系統(tǒng)（版本3.0）的以下幾個(gè)重要特色。3.1結(jié)構(gòu)化的微分實(shí)現(xiàn)DFT系統(tǒng)采用標(biāo)準(zhǔn)化的代碼實(shí)現(xiàn)，切線性模式的擾動(dòng)變量和基態(tài)值變量、微分計(jì)算語句和基態(tài)值計(jì)算語句總是成對出現(xiàn)，并具有清晰的程序結(jié)構(gòu)。微分代碼保持了原模式本身的結(jié)構(gòu)和風(fēng)格（如并行和向量特性、數(shù)據(jù)精度等），即語句到語句、結(jié)構(gòu)到結(jié)構(gòu)的微分實(shí)現(xiàn)。在奇異點(diǎn)或不可導(dǎo)處，DFT系統(tǒng)對微分?jǐn)_動(dòng)采取簡單的清零處理，實(shí)踐證明這對抑制擾動(dòng)計(jì)算溢出具有重要意義，但并不影響評(píng)價(jià)測試結(jié)果。3.2全局?jǐn)?shù)據(jù)相關(guān)分析DFT系統(tǒng)具有較強(qiáng)的數(shù)據(jù)相關(guān)分析能力，它包括全局?jǐn)?shù)據(jù)IO相關(guān)分析、全局?jǐn)?shù)據(jù)依賴相關(guān)分析、全局過程相關(guān)分析以及數(shù)據(jù)迭代相關(guān)分析幾個(gè)不同方面。數(shù)據(jù)依賴相關(guān)與數(shù)據(jù)IO相關(guān)關(guān)系密切，但又存在根本不同。前者強(qiáng)調(diào)每個(gè)變量在數(shù)學(xué)關(guān)系上的依賴性；而后者描述了一個(gè)對象的輸入輸出特性，且具有相對性，即任何一個(gè)變量參數(shù)，無論它是獨(dú)立變量還是依賴變量，在數(shù)學(xué)意義上都可等價(jià)為一個(gè)既是輸入又是輸出的參數(shù)來處理。DFT系統(tǒng)記錄所有過程參數(shù)的IO屬性表，通過深度遞歸相關(guān)計(jì)算，準(zhǔn)確計(jì)算每個(gè)過程參數(shù)的最終IO屬性。DFT系統(tǒng)通過對數(shù)據(jù)相關(guān)矩陣做模二和及自乘迭代計(jì)算（An+1=AnAn2）來完成數(shù)據(jù)的依賴相關(guān)分析，這種算法具有很好的對數(shù)收斂特性。DFT系統(tǒng)通過全局過程相關(guān)分析的結(jié)果，自動(dòng)生成模式的局部或整體相關(guān)引用樹結(jié)構(gòu)（如圖3.1），這對用戶分析復(fù)雜數(shù)值模式和微分評(píng)價(jià)測試都具有很好的指導(dǎo)作用。DFT系統(tǒng)還具有分析局部數(shù)據(jù)迭代相關(guān)和函數(shù)迭代相關(guān)的能力，這兩種形式的數(shù)據(jù)迭代相關(guān)是自動(dòng)微分實(shí)現(xiàn)頗具挑戰(zhàn)的難題之一。圖3.1GPSRayshooting模式的相關(guān)樹結(jié)構(gòu)片段3.3自動(dòng)生成測試程序基于IO相關(guān)分析的結(jié)果，DFT系統(tǒng)自動(dòng)生成微分測試代碼，分別對切線性模式的可靠性和運(yùn)行代價(jià)做統(tǒng)計(jì)評(píng)價(jià)測試。特別地，DFT系統(tǒng)還可將任何模式參數(shù)都視為輸入輸出參數(shù)，生成在數(shù)學(xué)意義上等價(jià)的測試代碼，這樣處理的不利之處在于往往需要極高的存儲(chǔ)開銷。3.4基于語句級(jí)的代碼優(yōu)化目前，DFT系統(tǒng)僅僅具備局地優(yōu)化能力。在語句級(jí)微分實(shí)現(xiàn)上采用二元?dú)w約的方法對微分代碼進(jìn)行優(yōu)化是DFT系統(tǒng)的一個(gè)重要特色。根據(jù)右端表達(dá)式的乘法復(fù)雜性及含變元數(shù)目的不同，DFT系統(tǒng)采取不同的分解策略。二元?dú)w約的方法避免了微分計(jì)算中的許多冗余計(jì)算，在一些復(fù)雜的非線性表達(dá)式的微分計(jì)算中具有最小的計(jì)算代價(jià)，同時(shí)也非常適合于微分系統(tǒng)的軟件實(shí)現(xiàn)。同時(shí)，對于某些特殊的運(yùn)算操作（除法、乘方）和特殊函數(shù)（如sqrt、exp），DFT系統(tǒng)較好地利用了基態(tài)值計(jì)算得到的中間結(jié)果，避免了微分實(shí)現(xiàn)中的冗余計(jì)算。4.系統(tǒng)應(yīng)用運(yùn)用自動(dòng)微分工具得到的切線性模式，可以在無截?cái)嗾`差意義下求解函數(shù)的數(shù)值微分