并行計(jì)算線性方程組的求解

2023/2/61現(xiàn)代密碼學(xué)理論與實(shí)踐之五基本術(shù)語線性方程組的定義和符號(hào)

a1,1x1+a1,2x2+…+a1,nxn=b1a2,1x1+a2,1x2+…+a2,nxn=b2an,1x1+an,1x2+…+an,nxn=bn記為AX=b2023/2/62現(xiàn)代密碼學(xué)理論與實(shí)踐之五

上三角方程組的求解上三角方程組的回代解法并行化

(1)SISD上的回代算法

Begin(1)fori=ndownto1do(1.1)xi=bi/aii(1.2)forj=1toi-1do

bj=bj-ajixi

aji=0

endfor

endforEnd可并行化2023/2/63現(xiàn)代密碼學(xué)理論與實(shí)踐之五

上三角方程組的求解上三角方程組的回代解法并行化

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

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

-算法

Beginfori=ndownto1doxi=bi/aiiforallPj,where1≤j≤pdofork=jtoi-1steppdo

bk=bk-akixi

aki=0

endfor

endfor

endforEnd//p(n)=n,t(n)=n2023/2/64現(xiàn)代密碼學(xué)理論與實(shí)踐之五三對角方程組的求解直接求解法奇偶規(guī)約法2023/2/65現(xiàn)代密碼學(xué)理論與實(shí)踐之五

三對角方程組的求解Gauss消去法(難以并行化)

①消元

②回代注：由于三對角

方程組的特殊性，一次消元或一次回代，只涉及鄰近一個(gè)方程，故難以并行化。2023/2/66現(xiàn)代密碼學(xué)理論與實(shí)踐之五

三對角方程組的直接求解法奇偶規(guī)約求解法(可并行化)三對角方程可以寫成如下形式

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/22023/2/67現(xiàn)代密碼學(xué)理論與實(shí)踐之五

三對角方程組的求解②重復(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)可以并行化；③回代求解可以并行化2023/2/68現(xiàn)代密碼學(xué)理論與實(shí)踐之五稠密線性方程組的求解有回代的高斯消去法

無回代的高斯-約旦法

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

2023/2/69現(xiàn)代密碼學(xué)理論與實(shí)踐之五

有回代的高斯消去法算法基本原理求解過程分為消元和回代兩個(gè)階段，消元是將系數(shù)矩陣A化為上三角陣T，然后對TX=c進(jìn)行回代求解。消元過程中可以應(yīng)用選主元方法，增加算法的數(shù)值穩(wěn)定性。下面是消元過程圖：2023/2/610現(xiàn)代密碼學(xué)理論與實(shí)踐之五

有回代的高斯消去法并行化分析消元和回代均可以并行化；選主元也可以并行化；消元過程的并行化圖示：處理器按行劃分2023/2/611現(xiàn)代密碼學(xué)理論與實(shí)踐之五

無回代的高斯-約旦法串行算法原理

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

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

2023/2/612現(xiàn)代密碼學(xué)理論與實(shí)踐之五

無回代的高斯-約旦法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

<—0

Pik(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)？2023/2/613現(xiàn)代密碼學(xué)理論與實(shí)踐之五

無回代的高斯-約旦法成本最優(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.52023/2/614現(xiàn)代密碼學(xué)理論與實(shí)踐之五迭代求解的高斯-賽德爾法串行算法原理

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

則認(rèn)為迭代是收斂的。并行化分析由于每次迭代需要使用本次迭代的前面部分值，因而難以得到同步的并行算法，下面給出一個(gè)異步的并行算法。2023/2/615現(xiàn)代密碼學(xué)理論與實(shí)踐之五迭代求解的高斯-賽德爾法MIMD異步并行算法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

End2023/2/616現(xiàn)代密碼學(xué)理論與實(shí)踐之五稀疏線性方程組的求解線性方程組的并行化方法稀疏線性方程組的迭代解法高斯-賽德爾迭代法的并行化2023/2/617現(xiàn)代密碼學(xué)理論與實(shí)踐之五線性方程方程的并行化方法線性方程組選擇算法的考慮因素系數(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?2023/2/618現(xiàn)代密碼學(xué)理論與實(shí)踐之五線性方程方程的并行化方法求解方法的并行化

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

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

-Gauss-Jordan消去法

-LU分解法

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

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