并行計算-29中科大

并行計算

中國科學技術(shù)大學計算機科學與技術(shù)系國家高性能計算中心(合肥)2004年12月第三篇并行數(shù)值算法

第八章基本通訊操作

第九章稠密矩陣運算

第十章線性方程組的求解

第十一章快速傅里葉變換

第十章線性方程組的求解

10.1三角形方程組的求解

10.2三對角方程組的求解

10.3稠密線性方程組的求解

10.4稀疏線性方程組的求解

10.1三角形方程組的求解

10.1.1基本術(shù)語

10.1.2上三角方程組的求解

國家高性能計算中心（合肥）52023/2/6基本術(shù)語線性方程組的定義和符號

a1,1x1+a1,2x2+…+a1,nxn=b1a2,1x1+a2,1x2+…+a2,nxn=b2an,1x1+an,1x2+…+an,nxn=bn記為AX=b

10.1三角形方程組的求解

10.1.1基本術(shù)語

10.1.2上三角方程組的求解

國家高性能計算中心（合肥）72023/2/6上三角方程組的求解上三角方程組的回代解法并行化

(1)SISD上的回代算法

Begin(1)fori=ndownto1do(1.1)xi=bi/aii(1.2)forj=1toi-1dobj=bj-ajixiaji=0endforendforEnd可并行化國家高性能計算中心（合肥）82023/2/6上三角方程組的求解上三角方程組的回代解法并行化

(2)SIMD-CREW上的并行回代算法

-劃分:p個處理器行循環(huán)帶狀劃分

-算法

Beginfori=ndownto1doxi=bi/aiiforallPj,where1≤j≤pdofork=jtoi-1steppdobk=bk-akixiaki=0endforendforendforEnd//p(n)=n,t(n)=n第十章線性方程組的求解

10.1三角形方程組的求解

10.2三對角方程組的求解

10.3稠密線性方程組的求解

10.4稀疏線性方程組的求解

10.2三對角方程組的求解

10.2.1直接求解法

10.2.2奇偶規(guī)約法

國家高性能計算中心（合肥）112023/2/6三對角方程組的直接求解法Gauss消去法(難以并行化)

①消元

②回代注：由于三對角的

方程組的特殊性，一次消元或一次回代，只涉及鄰近一個方程，故難以并行化。10.2三對角方程組的求解

10.2.1直接求解法

10.2.2奇偶規(guī)約法

國家高性能計算中心（合肥）132023/2/6三對角方程組的直接求解法奇偶規(guī)約求解法(可并行化)

三對角方程可以寫成如下形式

fixi-1+gixi+hixi+1=bii=1~nf1=hn=0串行算法描述

①利用上下相鄰方程消去偶序號方程中的奇下標變量:f2i-1x2i-2+g2i-1x2i-1+h2i-1x2i=b2i-1

f2ix2i-1

+g2ix2i+h2ix2i+1

=b2if2i+1x2i+g2i+1x2i+1+h2i+1x2i+2=b2i+1

2i-1方程乘上某個數(shù)消去2i方程中的f2ix2i-1項,2i+1方程乘上某個數(shù)消去2i方程中的h2ix2i+1項,使2i方程變?yōu)?/p>

αix2i-2+βix2i+γix2i+2=ηii=1,2,…,n/2國家高性能計算中心（合肥）142023/2/6三對角方程組的直接求解法②重復①最終可得:case1:case2:g1x1+h1x2=b1.f2x1+g2x2+h2x3

=b2.f3x2+g3x3+h3x4=b3.f4x3+g4x4=b4.

可以分別得到

g1x1+h1x2=b1或g1x1+h1x2=b1f2x1+g2x2=b2f2x1+g2x2+h2x3=b2

f3x2+g3x3=b3解得x1,x2或x1,x2,x3

③回代求解x并行化分析:

①、②消去奇下標可以并行化；③回代求解可以并行化第十章線性方程組的求解

10.1三角形方程組的求解

10.2三對角方程組的求解

10.3稠密線性方程組的求解

10.4稀疏線性方程組的求解

10.3稠密線性方程組的求解

10.3.1有回代的高斯消去法

10.3.2無回代的高斯-約旦法

10.3.3迭代求解的高斯-賽德爾法

國家高性能計算中心（合肥）172023/2/6有回代的高斯消去法算法基本原理求解過程分為消元和回代兩個階段，消元是將系數(shù)矩陣A化為上三角陣T，然后對TX=c進行回代求解。消元過程中可以應(yīng)用選主元方法，增加算法的數(shù)值穩(wěn)定性。下面是消元過程圖：國家高性能計算中心（合肥）182023/2/6有回代的高斯消去法并行化分析消元和回代均可以并行化；選主元也可以并行化；消元過程的并行化圖示：處理器按行劃分10.3稠密線性方程組的求解

10.3.1有回代的高斯消去法

10.3.2無回代的高斯-約旦法

10.3.3迭代求解的高斯-賽德爾法

國家高性能計算中心（合肥）202023/2/6無回代的高斯-約旦法串行算法原理

①消元:通過初等行變換,將(A,b)化為主對角線矩陣,(方便起見,記b為A的第n+1列)

②求解:xj=a’j,n+1/a’jj

國家高性能計算中心（合肥）212023/2/6無回代的高斯-約旦法SIMD-CREW上的并行算法

(1)處理器:

n2+n個處理器,這些處理器排成n×(n+1)的矩陣,

處理器編號為Pik,i=1~n,k=1~n+1(2)并行化分析①消元的并行化://O(n)forj=1ton-1,eachPikPar-do//第j次消元Pij(i<>j):aij<—0Pik(i<>j,k=j+1~n+1):aik

<—aik-ajk(aij/ajj)endfor②求解:foreachPjj(j=1~n)Par-do:xj

<—aj,n+1/ajj//O(1)

(3)時間分析:t(n)=O(n),p(n)=O(n2),c(n)=O(n3)成本最優(yōu)？國家高性能計算中心（合肥）222023/2/6無回代的高斯-約旦法成本最優(yōu)？串行算法的最優(yōu)時間：由于x=A-1b

①A-1b(假設(shè)已有A-1):O(n2)②求A-1:

∴求A-1需要:2次n/2×n/2矩陣的逆i(n/2)6次n/2×n/2矩陣的乘m(n/2)2次n/2×n/2矩陣的加a(n/2)i(n)=i(n/2)+6m(n/2)+2a(n/2)a(n/2)=n2/2,m(n/2)=O((n/2)x)2<x<2.5=>i(n)=O(nx)綜上，串行算法的最優(yōu)時間為O(nx)2<x<2.510.3稠密線性方程組的求解

10.3.1有回代的高斯消去法

10.3.2無回代的高斯-約旦法

10.3.3迭代求解的高斯-賽德爾法

國家高性能計算中心（合肥）242023/2/6迭代求解的高斯-賽德爾法串行算法原理

如果對某個k,給定的誤差允許值c有

則認為迭代是收斂的。并行化分析由于每次迭代需要使用本次迭代的前面部分值，因而難以得到同步的并行算法，下面給出一個異步的并行算法。國家高性能計算中心（合肥）252023/2/6迭代求解的高斯-賽德爾法MIMD異步并行算法N個處理器(N≤n)生成n個進程,每個進程計算x的一個分量算法

Begin(1)oldi

xi0,newixi0

(2)生成進程i(3)進程irepeat(i)oldi

newi(ii)newi

(bi-∑k<iaik×oldk-∑k>iaik×oldk)/aiiuntil∑i=1~n|oldi

-newi|<cxi

newi

End第十章線性方程組的求解

10.1三角形方程組的求解

10.2三對角方程組的求解

10.3稠密線性方程組的求解

10.4稀疏線性方程組的求解

10.4稀疏線性方程組的求解

10.4.1線性方程組的并行化方法

10.4.2稀疏線性方程組的迭代解法

10.4.3高斯-賽德爾迭代法的并行化

國家高性能計算中心（合肥）282023/2/6線性方程方程的并行化方法線性方程組選擇算法的考慮因素系數(shù)矩陣A的結(jié)構(gòu)dense Gaussianelimination,etcSparse iterativemethodtriangular substitution,odd-evenreductioncertainPDEs multigrid,etc計算精度要求Gaussianelimination:moreaccurate,moreexpensiveConjugategradients:lessaccurate,lessexpensive計算環(huán)境要求architecture,availablelanguages,compilerqualitylibraries?國家高性能計算中心（合肥）292023/2/6線性方程方程的并行化方法求解方法的并行化

(1)直接解法的并行化(用于稠密線性方程組)

-Gauss消去法(包括選主元的Gauss消去法)

-Gauss-Jordan消去法

-LU分解法

(2)迭代法的并行化(用于稠密和稀疏線性方程組)

-Jacobi-Gauss-Seidel(可異步并行化)-JacobiOverRelaxation(JOR)-Gauss-SeidelOverRelaxation(SOR)

-ConjugateGradient10.4稀疏線