改進(jìn)的空間高精度曲面建模-ad算法

改進(jìn)的空間高精度曲面建模-ad算法

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