針對求解有限元分析的特征值問題,提出了一種隱式重啟動Arnoldi/Lanczos方法的子區(qū)域并行算法。隱式重啟動Arnoldi/Lanczos利用重啟動技術(shù)以提高所需譜的收斂性,并能有效處理Krylov基形成問題、存儲所需的內(nèi)存問題、計算成本問題。并行算法中采取子區(qū)域接子區(qū)域方法、重疊和非重疊網(wǎng)格劃分技術(shù)。采用壓縮數(shù)據(jù)結(jié)構(gòu)來儲存系數(shù)矩陣。對Krylov的數(shù)值線性代數(shù)運算和隱式重啟動法中的數(shù)值線性代數(shù)運算的并行化進行了研究。數(shù)值算例表明:該算法具有良好的適用性和效率,適合分布式儲存體系的機群。 

【文章來源】：應(yīng)用力學(xué)學(xué)報. 2017,34(02)北大核心

【文章頁數(shù)】：8 頁

【部分圖文】：

非重疊網(wǎng)格劃分方式

226應(yīng)用力學(xué)學(xué)報第34卷(N1)，位于劃分界面上的節(jié)點分為主邊界節(jié)點(N2)和從屬邊界節(jié)點(N3)，界面節(jié)點在第i個子區(qū)域中為主邊界節(jié)點，而在共享該節(jié)點的所有其它子區(qū)域中為從屬邊界節(jié)點。不包含邊界節(jié)點的單元為內(nèi)部單元，而包含邊界節(jié)點的單元為邊界單元。區(qū)域劃分如圖3所示。圖3非重疊網(wǎng)格劃分方式Fig.3Anon-overlappingmeshpartitioningscheme圖4重疊網(wǎng)格劃分方式Fig.4Anoverlappingmeshpartitioningscheme3.2重疊劃分對重疊區(qū)域劃分，定義一組由其它分區(qū)的節(jié)點組成新節(jié)點，稱為虛節(jié)點(N4)，由主邊界節(jié)點N2和虛節(jié)點N4構(gòu)成共享單元，將一組共享單元加到非重疊區(qū)域的網(wǎng)格形成重疊區(qū)域。圖4表示重疊區(qū)域劃分。3.3壓縮數(shù)據(jù)結(jié)構(gòu)壓縮數(shù)據(jù)結(jié)構(gòu)，如壓縮稀疏行格式是基于圖的數(shù)據(jù)結(jié)構(gòu)。在有限元方法中，關(guān)聯(lián)到網(wǎng)格的圖總是無指向的，即，如果元素0ijk≠，那么元素0jik≠。文獻[16]提出了一個CSR的變化格式，稱為壓縮稀疏行列格式(CSRC)。在CSRC格式中，對角線以下的非零元素存儲在CSR格式，而對角線以上的非零元素存儲在壓縮稀疏列格式(CSC)。對角線的元素存儲在一個單獨的數(shù)組ad中、數(shù)組au存儲上半部分，數(shù)組al存儲下半部分。第i行的第一個元素用ia(i)定位，另一個數(shù)組ja存儲元素ijk的列號。CSRC格式的主要優(yōu)點是只需要存儲數(shù)組ja所需內(nèi)存的一半；用來存儲非對角元素的兩個數(shù)組能更快地進行內(nèi)存訪問。采取CSRC格式，算法3描述非對稱情況下矩陣向量積的算法。doi=1，n/循環(huán)(loopover)ui=u(i)t=ad(i)*uidok=ia(i)，ia(i+1)－1/對方程i的下部非零項循環(huán)(loopoverthelowernonzeroentriesofequationi)jak=ja(k)t=t+al(k)*u(jak)p(jak)=p(jak)+au(k)*ui/上部列(uppercolumn)enddop(i)=tenddo圖5非對稱

，需要進行三級運算。Hk=QTHkQ，Tk=QTTkQ，Vk=VkQ(18)矩陣Q是Hk或Tk的一個因子，由于這些矩陣已復(fù)制，因而不需要進行通信。4數(shù)值算例本文數(shù)值計算是在DELL工作站機群上進行。該機群由4臺雙CPU的DELL工作站通過100.0Mbps以太網(wǎng)連接而成，共有8個CPU(2.4GHzXeonchips，512KBcache)，每個節(jié)點內(nèi)存1.0GB。每臺工作站都有真實的IP地址，使用消息傳遞接口(MPI)。操作系統(tǒng)為RedHatLinux9.0。4.1對稱問題算例為測試算法的性能，以壩體及地基的二維平面應(yīng)變模型作為算例，如圖9所示，計算其特征值和特征向量。采用兩個隱式重啟動，建立一個50步的Lanczos分解，特征值收斂容許值取為1×10-10。進行重疊和非重疊區(qū)域劃分，整個區(qū)域劃分為與處理器數(shù)相等的子區(qū)域，每個子區(qū)域有大約相等的單元數(shù)。每個子區(qū)域映射到各相應(yīng)的處理器。各處理器得到子區(qū)域單元數(shù)據(jù)后，相應(yīng)子區(qū)域中的計算在各處理器中進行。劃分的網(wǎng)格包含273827個8節(jié)點二次單元、1647436個自由度。圖9壩體及其地基的計算模型Fig.9Themodelofdamandfoundation為評價并行性能，分別用1個、2個、4個、6個、8個處理器對所求問題進行求解。圖10和圖11分別顯示了非重疊和重疊劃分的算法加速比和效率，可見非重疊劃分較重疊劃分的加速比要大，計算性能更好。從中也可發(fā)現(xiàn)，隨著處理器數(shù)的增加，計算性能變差，這是由于出現(xiàn)大部分數(shù)據(jù)通信和同步的PCG迭代部分增加，以及問題的粒度減小而造成，因而通信開銷增加。圖10對稱問題算例的并行加速比Fig.10Parallelspeedupforsymmetriccase圖11對稱問題算例的并行效率Fig.11Parallelefficiencyforsymmetriccase圖12非對稱問題算例的并行加速比Fig.12Parallelspeedupfornon-symme


本文編號：2998082