并行計(jì)算-29中科大

并行計(jì)算

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

第八章基本通訊操作

第九章稠密矩陣運(yùn)算

第十章線性方程組的求解

第十一章快速傅里葉變換

第十章線性方程組的求解

10.1三角形方程組的求解

10.2三對(duì)角方程組的求解

10.3稠密線性方程組的求解

10.4稀疏線性方程組的求解

10.1三角形方程組的求解

10.1.1基本術(shù)語(yǔ)

10.1.2上三角方程組的求解

國(guó)家高性能計(jì)算中心（合肥）52023/2/6基本術(shù)語(yǔ)線性方程組的定義和符號(hào)

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ù)語(yǔ)

10.1.2上三角方程組的求解

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

(1)SISD上的回代算法

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

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

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

-算法

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

10.1三角形方程組的求解

10.2三對(duì)角方程組的求解

10.3稠密線性方程組的求解

10.4稀疏線性方程組的求解

10.2三對(duì)角方程組的求解

10.2.1直接求解法

10.2.2奇偶規(guī)約法

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

①消元

②回代注：由于三對(duì)角的

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

10.2.1直接求解法

10.2.2奇偶規(guī)約法

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

三對(duì)角方程可以寫成如下形式

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

①利用上下相鄰方程消去偶序號(hào)方程中的奇下標(biāo)變量: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方程乘上某個(gè)數(shù)消去2i方程中的f2ix2i-1項(xiàng),2i+1方程乘上某個(gè)數(shù)消去2i方程中的h2ix2i+1項(xiàng),使2i方程變?yōu)?/p>

αix2i-2+βix2i+γix2i+2=ηii=1,2,…,n/2國(guó)家高性能計(jì)算中心（合肥）142023/2/6三對(duì)角方程組的直接求解法②重復(fù)①最終可得: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并行化分析:

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

10.1三角形方程組的求解

10.2三對(duì)角方程組的求解

10.3稠密線性方程組的求解

10.4稀疏線性方程組的求解

10.3稠密線性方程組的求解

10.3.1有回代的高斯消去法

10.3.2無(wú)回代的高斯-約旦法

10.3.3迭代求解的高斯-賽德?tīng)柗?/p>

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

10.3.1有回代的高斯消去法

10.3.2無(wú)回代的高斯-約旦法

10.3.3迭代求解的高斯-賽德?tīng)柗?/p>

國(guó)家高性能計(jì)算中心（合肥）202023/2/6無(wú)回代的高斯-約旦法串行算法原理

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

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

國(guó)家高性能計(jì)算中心（合肥）212023/2/6無(wú)回代的高斯-約旦法SIMD-CREW上的并行算法

(1)處理器:

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

處理器編號(hào)為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)時(shí)間分析:t(n)=O(n),p(n)=O(n2),c(n)=O(n3)成本最優(yōu)？國(guó)家高性能計(jì)算中心（合肥）222023/2/6無(wú)回代的高斯-約旦法成本最優(yōu)？串行算法的最優(yōu)時(shí)間：由于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)時(shí)間為O(nx)2<x<2.510.3稠密線性方程組的求解

10.3.1有回代的高斯消去法

10.3.2無(wú)回代的高斯-約旦法

10.3.3迭代求解的高斯-賽德?tīng)柗?/p>

國(guó)家高性能計(jì)算中心（合肥）242023/2/6迭代求解的高斯-賽德?tīng)柗ù兴惴ㄔ?/p>

如果對(duì)某個(gè)k,給定的誤差允許值c有

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

Begin(1)oldi

xi0,newixi0

(2)生成進(jìn)程i(3)進(jìn)程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三對(duì)角方程組的求解

10.3稠密線性方程組的求解

10.4稀疏線性方程組的求解

10.4稀疏線性方程組的求解

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

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

10.4.3高斯-賽德?tīng)柕ǖ牟⑿谢?/p>

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

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

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

-Gauss-Jordan消去法

-LU分解法

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

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

-ConjugateGradient10.4稀疏線