资源描述：
《PC10 中科大 并行计算 教学课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、并行计算中国科学技术大学计算机科学与技术系国家高性能计算中心(合肥)2004年12月2021/8/261现代密码学理论与实践之五第三篇并行数值算法第八章基本通讯操作第九章稠密矩阵运算第十章线性方程组的求解第十一章快速傅里叶变换2021/8/262现代密码学理论与实践之五第十章线性方程组的求解10.1三角形方程组的求解10.2三对角方程组的求解10.3稠密线性方程组的求解10.4稀疏线性方程组的求解2021/8/263现代密码学理论与实践之五10.1三角形方程组的求解10.1.1基本术语10.1.2上三角方程组的求解2021/8/264现代密码学理论与实
2、践之五基本术语线性方程组的定义和符号a1,1x1+a1,2x2+…+a1,nxn=b1a2,1x1+a2,1x2+…+a2,nxn=b2an,1x1+an,1x2+…+an,nxn=bn记为AX=b10.1三角形方程组的求解10.1.1基本术语10.1.2上三角方程组的求解2021/8/266现代密码学理论与实践之五上三角方程组的求解上三角方程组的回代解法并行化(1)SISD上的回代算法Begin(1)fori=ndownto1do(1.1)xi=bi/aii(1.2)forj=1toi-1dobj=bj-ajixiaji=0endforendforE
3、nd可并行化上三角方程组的求解上三角方程组的回代解法并行化(2)SIMD-CREW上的并行回代算法-划分:p个处理器行循环带状划分-算法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稀疏线性方程组的求解2021/8/269现代密码学理论与实践之五10.2
4、三对角方程组的求解10.2.1直接求解法10.2.2奇偶规约法2021/8/2610现代密码学理论与实践之五三对角方程组的直接求解法Gauss消去法(难以并行化)①消元②回代注：由于三对角的方程组的特殊性，一次消元或一次回代，只涉及邻近一个方程，故难以并行化。10.2三对角方程组的求解10.2.1直接求解法10.2.2奇偶规约法2021/8/2612现代密码学理论与实践之五三对角方程组的直接求解法奇偶规约求解法(可并行化)三对角方程可以写成如下形式fixi-1+gixi+hixi+1=bii=1~nf1=hn=0串行算法描述①利用上下相邻方程消去偶序号
5、方程中的奇下标变量:f2i-1x2i-2+g2i-1x2i-1+h2i-1x2i=b2i-1f2ix2i-1+g2ix2i+h2ix2i+1=b2if2i+1x2i+g2i+1x2i+1+h2i+1x2i+2=b2i+12i-1方程乘上某个数消去2i方程中的f2ix2i-1项,2i+1方程乘上某个数消去2i方程中的h2ix2i+1项,使2i方程变为αix2i-2+βix2i+γix2i+2=ηii=1,2,…,n/2三对角方程组的直接求解法②重复①最终可得:case1:case2:g1x1+h1x2=b1.f2x1+g2x2+h2x3=b2.f3x2+
6、g3x3+h3x4=b3.f4x3+g4x4=b4.可以分别得到g1x1+h1x2=b1或g1x1+h1x2=b1f2x1+g2x2=b2f2x1+g2x2+h2x3=b2f3x2+g3x3=b3解得x1,x2或x1,x2,x3③回代求解x并行化分析:①、②消去奇下标可以并行化；③回代求解可以并行化第十章线性方程组的求解10.1三角形方程组的求解10.2三对角方程组的求解10.3稠密线性方程组的求解10.4稀疏线性方程组的求解2021/8/2615现代密码学理论与实践之五10.3稠密线性方程组的求解10.3.1有回代的高斯消去法10.3.2无回代的高斯
7、-约旦法10.3.3迭代求解的高斯-赛德尔法2021/8/2616现代密码学理论与实践之五有回代的高斯消去法算法基本原理求解过程分为消元和回代两个阶段，消元是将系数矩阵A化为上三角阵T，然后对TX=c进行回代求解。消元过程中可以应用选主元方法，增加算法的数值稳定性。下面是消元过程图：有回代的高斯消去法并行化分析消元和回代均可以并行化；选主元也可以并行化；消元过程的并行化图示：处理器按行划分10.3稠密线性方程组的求解10.3.1有回代的高斯消去法10.3.2无回代的高斯-约旦法10.3.3迭代求解的高斯-赛德尔法2021/8/2619现代密码学理论与实
8、践之五无回代的高斯-约旦法串行算法原理①消元:通过初等行变换,将(A,b)化为主对角线矩阵,(
