改進的空間高精度曲面建模-ad算法

改進的空間高精度曲面建模-ad算法

1改進的hism-ad算法高精度曲線建模算法（ham）的研究始于20世紀(jì)80年代末。在冰斗形態(tài)建模中，首先應(yīng)用于冰斗模型建模。在此基礎(chǔ)上，我們成功應(yīng)用了基于dem的多段模型理論。土壤屬性空間模擬、氣候因素空間模擬以及其他地理和生態(tài)領(lǐng)域的模擬。同時,隨著HASM理論的發(fā)展與完善,各種HASM求解算法也相繼提出,如預(yù)處理共軛梯度法、多重網(wǎng)格算法、平差算法、自適應(yīng)算法及基于GPU的HASM加速算法等,但是,HASM計算效率一直沒有得到明顯的改善,以預(yù)處理共軛梯度算法為例,當(dāng)計算規(guī)模為1000×1000時,采用當(dāng)前普通計算機的時間消耗接近3小時。計算速度的限制已經(jīng)成為限制HASM理論進一步應(yīng)用的瓶頸。HASM計算耗時大的主要原因是該模型將曲面模擬問題轉(zhuǎn)化為大規(guī)模方程組的求解,因而不管采用何種迭代法,都難以獲得令人滿意的計算速度。為了提高計算速度,岳天祥等(2010)根據(jù)分組平差原理構(gòu)建了HASM局部算法,即HASM-AD算法。該算法將全局建立線性方程組求解問題轉(zhuǎn)化為局部方程組建立求解,一定程度上提高了模型的計算速度。但是,后續(xù)的實驗表明,由于該算法需要在局部窗口中判斷采樣點信息,當(dāng)計算規(guī)模增加后重復(fù)的查找操作會使得計算時間急劇增加。為了解決上述問題,本文對現(xiàn)有的HASM-AD算法進行改進,在分組平差計算原理的基礎(chǔ)上,通過在計算過程中為采樣點添加索引信息,避免了重復(fù)的查找操作而大幅提高計算速度。同時,改進的HASM-AD算法在遍歷獨立計算單元的過程中,計算第一類、第二類基本量及克式符號等變量,降低了模型計算過程中的內(nèi)存消耗。本文以全國陸地降水空間分布模擬為例,驗證了改進的HASM-AD算法在空間變量模擬研究中的適用性。2改進的哈m-ad算法2.1克式符號的計算與其他HASM算法相比,HASM-AD算法可以看作是一種局部算法。該算法根據(jù)分組平差計算原理,將計算區(qū)域劃分為一系列相鄰的5×5分析窗口,稱作獨立計算單元(圖1)。以中間3×3的格網(wǎng)點上真實值與初始值的差(稱作改正數(shù))作為未知數(shù),將高斯方程作為約束條件建立平差方程組,并結(jié)合采樣點信息(如果當(dāng)前5×5分析窗口中包含采樣點)建立最終的求解方程組(式1),5×5分析窗口的邊界點僅參與曲面基本量及克式符號的計算。其中,vi(i=0,…,8)代表分析窗口內(nèi)部解算格網(wǎng)點上的模擬變量的改正數(shù),作為方程組的未知數(shù);fi,j是格網(wǎng)點上初始值,由HASM模型的輸入驅(qū)動場給出;是采樣點值,同樣由HASM模型的輸入采樣點信息得到;E,G,L,M,N,Γ為曲面基本量和克式符號,可由驅(qū)動場計算得到,具體的計算表達式可參見參考文獻。在實際應(yīng)用中,可認(rèn)為一個獨立計算單元中至多包含一個采樣點,這樣一個獨立計算單元所建立的條件平差方程組是3階(獨立計算單元中不包含采樣點)或4階(獨立計算單元中包含采樣點)。因此,無論是采用直接法還是普通迭代法求解,計算量都很小,可以提高計算速度并減小內(nèi)存消耗。當(dāng)計算規(guī)模較小時,HASM-AD算法可以提高計算效率,但是實驗表明,由于每個獨立計算單元都需要進行采樣點信息查找操作,當(dāng)計算規(guī)模增大時HASM-AD算法計算耗時也急劇增加。例如,以個人計算機為例(基于VS2010平臺C++程序),當(dāng)計算規(guī)模為1000×1000時,預(yù)處理共軛梯度算法耗時為10774s,平差算法耗時為5741s,但是,當(dāng)計算規(guī)模增加到1400×1400時,預(yù)處理共軛梯度法消耗時間為20746s,而平差算法耗時則超過預(yù)處理共軛梯度算法,達到了22174s。因此,本文對HASM-AD算法做了進一步改進,旨在降低采樣點查找操作帶來的時間消耗,從而整體上提高HASM模型的效率。2.2立計算單元的檢索本文對HASM-AD算法作了兩處改進:(1)為采樣點添加索引信息,避免在每個獨立計算單元求解時都進行查找操作;(2)根據(jù)HASM-AD分組算法的特點,在分組計算過程中求解建立方程組所需要的第一類、第二類基本量及克式符號。這兩處改進不僅顯著提高了HASM-AD算法的運算速度,也節(jié)省了計算過程中的內(nèi)存空間需求,下面進行詳細(xì)說明。2.2.1采樣點索引創(chuàng)建規(guī)則圖中黑色實心圓代表采樣點,空心三角形則代表包含該采樣點的獨立計算單元中心點,其中,左上角、右下角的獨立計算單元用虛線框標(biāo)出。當(dāng)獨立計算單元中包含采樣點時,為建立條件平差方程組,還需要知道采樣點在3×3計算格網(wǎng)中的次序,以便決定條件平差方程組中第4個方程的非0系數(shù)。例如,圖2中左上角的空心三角形標(biāo)注的數(shù)字“8”表示以該點為中心的獨立計算單元中,采樣點所對應(yīng)的未知變量次序號為8(序號從0開始計),其余類推。{booltag;//標(biāo)識以當(dāng)前格網(wǎng)點為中心的計算單元中是否包含采樣點intcixu1;//標(biāo)識采樣點(如果有)在當(dāng)前計算單元中的順序(取值0-8)intcixu2;//標(biāo)識采樣點(如果有)在采樣數(shù)組中的順序號}Index[m×n];//m,n分別為計算區(qū)域的行號和列號在計算過程中,對采樣點數(shù)組遍歷一次,遍歷過程中對每個格網(wǎng)點都建立采樣點索引結(jié)構(gòu)體。索引創(chuàng)建規(guī)則為:對于當(dāng)前采樣點,首先,根據(jù)其坐標(biāo)信息確定該采樣點在計算矩陣中的位置(例如圖2中實心黑點);然后,對該采樣點所在的位置極其周圍的格網(wǎng)點(共9個)建立索引信息(圖2中空心三角形)。令空心三角形位置格網(wǎng)點所對應(yīng)的結(jié)構(gòu)體數(shù)組元素的tag值為1,表示以該格網(wǎng)點為中心的獨立計算單元內(nèi)包含采樣點;第二個變量cixu1按照圖中所標(biāo)注的進行賦值,例如,圖2第一個空心三角形處的格網(wǎng)點的cixu1賦值為8,表示以該格網(wǎng)點為中心的獨立計算單元中,采樣點在3×3計算單元中的序號為8;第三個變量cixu2賦值為當(dāng)前采樣點在采樣點數(shù)組中的序號,以便后面建立方程組時直接從采樣點數(shù)組中獲取該采樣點的屬性值。在后面獨立計算單元遍歷時,首先根據(jù)索引結(jié)構(gòu)體的tag變量判斷當(dāng)前計算單元是否包含采樣點,若包含,則分別從索引結(jié)構(gòu)體的第二個、第三個變量中得到采樣點在當(dāng)前計算單元中的順序,以及采樣點的屬性值,進而建立平差方程求解;若不包含,則直接建立不包含采樣點的平差方程組進行求解。2.2.2高效階次的高效計算本文對HASM-AD算法的另一個改進是取消計算過程中用來存儲第一類、第二類基本量及克式符號的全局?jǐn)?shù)組。其他HASM求解算法需要建立全局線性方程組進行求解,因此在方程組建立之前,首先需要計算每個格網(wǎng)點上的第一類基本量(3個)、第二類基本量(3個)及克式符號(6個),為此需要消耗的內(nèi)存是計算規(guī)模的12倍。如此大的內(nèi)存消耗在大規(guī)模計算中是不容忽視的。而分析HASM-AD算法的特點可以發(fā)現(xiàn),該算法實質(zhì)上是以5×5分析窗口遍歷計算區(qū)域,遍歷過程中建立條件平差方程組求解,因此,可在遍歷過程中實時計算當(dāng)前需要的第一類、第二類基本量,以及克式符號。此時不需要開辟數(shù)組空間,僅需定義若干變量即可。綜上分析,改進后的HASM-AD算法可以按照圖3的步驟進行。2.3計算速度比較HASM-AD算法包括采樣點信息索引創(chuàng)建和獨立計算單元計算兩個過程,其中,創(chuàng)建索引的過程只需要遍歷一遍采樣數(shù)組,時間可以忽略不計,因此,獨立計算單元計算是該算法的主要時間消耗。因為每個計算單元所求解方程組為3階或4階,故單個計算單元時間消耗基本一致,假設(shè)完成一個獨立計算單元計算所消耗的平均時間為t,而整個計算區(qū)域包含的獨立計算單元數(shù)目為M×N,M和N分別為計算區(qū)域的行數(shù)和列數(shù),因此,最后需要的計算總時間為(M×N)×t?？梢钥闯龈倪M的HASM-AD算法時間消耗與計算區(qū)域的格網(wǎng)數(shù)成正比,即計算時間隨著計算格網(wǎng)數(shù)目的增加而線性增加。為了驗證以上分析,本文統(tǒng)計了不同計算規(guī)模的改進HASM-AD算法時間消耗(圖4(b))。其中,實驗曲面為高斯合成曲面,采樣點采樣率為1%并且為隨機采樣。作為對比,同時統(tǒng)計了HASM預(yù)處理共軛梯度算法在相同計算規(guī)模下的時間消耗(圖4(a))?？梢钥闯?HASM-PCG計算時間隨計算規(guī)模增加呈指數(shù)形式增長,增長速度非?？?例如,當(dāng)計算規(guī)模為200×200時,時間消耗為165s,當(dāng)計算規(guī)模增加到1000×1000時,時間消耗達到了10744s。而改進的HASM-AD計算時間與計算規(guī)模呈近似線性關(guān)系,當(dāng)計算規(guī)模為200×200時,時間消耗僅為1s,當(dāng)計算規(guī)模增加到1000×1000時,時間消耗也僅為32s。由于將全局大規(guī)模線性方程組計算轉(zhuǎn)化為依次計算獨立計算單元中的條件平差方程組,并且改進的HASM-AD算法在獨立計算單元方程組建立過程中避免了重復(fù)的采樣點查找操作,而只需要進行布爾運算,因此,改進的HASM-AD算法計算效率與HASM-PCG算法相比得到了顯著提高。改進的HASM-AD算法同樣減小了計算過程中的內(nèi)存需求。由于將第一類、第二類基本量及克氏符號改為在遍歷獨立計算單元過程中實時計算,因此,算法在計算過程中僅需要存儲驅(qū)動場數(shù)組和存儲索引信息的結(jié)構(gòu)體數(shù)組(采樣點信息存儲空間忽略不計),并且索引結(jié)構(gòu)體中的變量為1個布爾型,2個整型,所以,若假設(shè)驅(qū)動場數(shù)組的存儲空間為M,則改進的HASM-AD算法的內(nèi)存需求不足2M。而對于其他建立全局線性方程組的算法,以HASM-PCG算法為例,在計算過程中需要存儲驅(qū)動場數(shù)據(jù)、第一類基本量、第二類基本量、克氏符號、方程組系數(shù)矩陣(用稀疏矩陣三元組格式)、方程組右端向量,以及迭代計算過程中的臨時變量,內(nèi)存總需求超過了20M。綜上分析看出,相比其他HASM求解算法,改進的HASM-AD算法計算速度有大幅度提高,同時計算過程中的內(nèi)存需求也明顯減少,因此,適用于大區(qū)域、大規(guī)模數(shù)據(jù)的空間變量模擬。關(guān)于數(shù)學(xué)曲面模擬的驗證可見參考文獻,本文以全國降雨量模擬來驗證改進后的HASM-AD算法在空間變量模擬中的精度,并說明該算法相比于其他HASM算法的效率優(yōu)勢。3模擬結(jié)果對比降水是陸地生物圈模型的主要驅(qū)動變量,是重要的農(nóng)業(yè)氣候資源。根據(jù)有限的降水觀測站插值得到區(qū)域降水連續(xù)的分布是生態(tài)學(xué)、農(nóng)用氣候?qū)W研究的熱點問題之一。目前應(yīng)用于降水空間分布模擬的研究中的方法主要有數(shù)學(xué)插值方法、人工神經(jīng)網(wǎng)絡(luò)、多元回歸分析等。王晨亮(2012),趙娜(2013)等將HASM引入到降水空間插值模擬中,獲得了精度更好的結(jié)果。為了驗證改進的HASM-AD算法的空間變量模擬精度及計算速度的優(yōu)勢,本文以模擬中國1951-2010年60年間的平均降水量作為驗證示例?？梢垣@取降水?dāng)?shù)據(jù)的氣象站點為712個(圖5),其中,選取605個站點(85%)的數(shù)據(jù)用來模擬降水分布,107個站點(15%)用作精度驗證。驗證站點為隨機選擇,共進行20次隨機選擇驗證。最后,統(tǒng)計改進的HASM-AD算法及比較算法(HASM-PCG算法)的模擬結(jié)果精度及時間消耗,如表1所示。由上可見,與HASM-PCG算法相比,在模擬精度方面改進的HASM-AD算法略有提高,HASM-PCG算法模擬結(jié)果的均方根誤差和平均絕對誤差分別是131.6400和77.9690,而改進的HASM-AD算法模擬結(jié)果的均方根誤差和平均絕對誤差則分別降低到131.4991和77.5088.從模型輸出結(jié)果(圖6)可以看出,改進的HASM-AD算法模擬得到的中國年平均降水分布合理,符合實際情況,能夠滿足大尺度上水文、生態(tài)研究需求。在計算速度方面,改進的HASM-AD算法優(yōu)勢更為明顯,對于本問題的計算規(guī)模(計算區(qū)域網(wǎng)格數(shù)目約為2×105),在相同的計算機環(huán)境下,HASM-PCG算法耗時1920s,而改進的HASM-AD算法僅需4s,計算速度提高了480倍。表明改進的HASM-AD算法在模擬精度不低于HASM-PCG算法的前提下能顯著提高計算速度,從而降低計算時間消耗。4改進的hism-ad算法模擬結(jié)果的比較與傳統(tǒng)的全局HASM算法不同,HASM-AD算法根據(jù)分組平差計算原理,將大規(guī)模線性方程組求解轉(zhuǎn)化為求解獨立計算單元中的平差方程組(3階或4階),因而在方程組求解階段可以顯著減少計算時間。而本文在HASM-AD算法的基礎(chǔ)上對采樣點添加了索引信息,避免了遍歷獨立計算單元過程中對采樣點信息的重復(fù)查找,因此,大幅提高了整個模擬過程的效率。本文得出的主要結(jié)論如下:(1)改進的HASM-AD算法添加了采樣點索引信息,避免了在計算過程中重復(fù)尋找計算單元中是否含有采樣點,極大地提高了HASM的計算速度。不同計算規(guī)模的數(shù)值實驗表明,HASM-AD算法計算時間隨計算區(qū)域網(wǎng)格數(shù)目增加而線性增加;(2)改進的HASM-AD算法取消模型運行初始階段的第一類、第二類基本量,以及克式符號的計算,在獨立計算單元的遍歷過程中實時動態(tài)計算所需要的基本量及克式符號值,顯著降低了HASM模型運行的內(nèi)存需求;(3)采用全國陸地降水模擬作為實例驗證改進的HASM-AD算法的模擬精度及計算效率,結(jié)果表明,改進的HASM-AD算法模擬結(jié)果精度優(yōu)于HASM-PCG算法的模擬結(jié)果,平均絕對誤差及誤差均方根均小于后者,而計算效率優(yōu)勢更為明顯,HASM-PCG算法耗時1920s,而HASM-A