《并行计算.6方程》由会员分享，可在线阅读，更多相关《并行计算.6方程（25页珍藏版）》请在金锄头文库上搜索。
1、并 行 计 算线性方程组的求解*1现代密码学理论与实践之五基本术语l线性方程组的定义和符号a1,1x1 + a1,2x2 + + a1,nxn = b1a2,1x1 + a2,1x2 + + a2,nxn = b2an,1x1 + an,1x2 + + an,nxn = bn记为 AX=b Date2现代密码学理论与实践之五上三角方程组的求解l上三角方程组的回代解法并行化(1)SISD上的回代算法Begin(1)for i=n downto 1 do(1.1)xi=bi/aii(1.2)for j=1 to i-1 dobj=bj-ajixiaji=0endforendforEnd可并行化Da
2、te3现代密码学理论与实践之五上三角方程组的求解l上三角方程组的回代解法并行化(2)SIMD-CREW上的并行回代算法- 划分: p个处理器行循环带状划分- 算法Beginfor i=n downto 1 doxi=bi/aiifor all Pj, where 1jp dofor k=j to i-1 step p dobk=bk-akixiaki=0endforendforendforEnd / p(n)=n, t(n)=n Date4现代密码学理论与实践之五三对角方程组的求解l直接求解法l奇偶规约法Date5现代密码学理论与实践之五三对角方程组的求解lGauss消去法(难以并行化) 消元
3、回代注：由于三对角方程组的特殊性，一次消元或一次回代，只涉及邻近一个方程，故难以并行化。Date6现代密码学理论与实践之五三对角方程组的直接求解法l奇偶规约求解法(可并行化)三对角方程可以写成如下形式fixi-1+gixi+hixi+1=bi i=1nf1=hn=0l串行算法描述利用上下相邻方程消去偶序号方程中的奇下标变量: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项
4、, 2i+1方程乘上某个数 消去2i方程中的h2ix2i+1项, 使2i方程变为 ix2i-2+ix2i+ix2i+2=i i=1,2,n/2Date7现代密码学理论与实践之五三对角方程组的求解重复最终可得:case 1: case 2: g1x1+h1x2 =b1 .f2x1+g2x2+h2x3 =b2 .f3x2 +g3x3+h3x4=b3 .f4x3 +g4x4 =b4 .可以分别得到g1x1+h1x2 =b1 或 g1x1+h1x2 =b1 f2x1+g2x2 =b2 f2x1+g2x2+h2x3 =b2 f3x2+g3x3 =b3解得 x1,x2 或 x1, x2, x3 回代求解x
5、l并行化分析: 、消去奇下标可以并行化；回代求解可以并行化Date8现代密码学理论与实践之五稠密线性方程组的求解l有回代的高斯消去法l无回代的高斯-约旦法l迭代求解的高斯-赛德尔法Date9现代密码学理论与实践之五有回代的高斯消去法l算法基本原理l求解过程分为消元和回代两个阶段，消元是将系数矩阵A化为上三 角阵T，然后对TX=c进行回代求解。l消元过程中可以应用选主元方法，增加算法的数值稳定性。l下面是消元过程图：Date10现代密码学理论与实践之五有回代的高斯消去法l并行化分析l消元和回代均可以并行化；l选主元也可以并行化；l消元过程的并行化图示：处理器按行划分Date11现代密码学理论与实
6、践之五无回代的高斯-约旦法l串行算法原理 消元: 通过初等行变换,将(A,b)化为主对角线矩阵,(方便起见, 记b为A的第n+1列) 求解: xj=aj,n+1/ajj Date12现代密码学理论与实践之五无回代的高斯-约旦法lSIMD-CREW上的并行算法(1)处理器: n2+n个处理器, 这些处理器排成n(n+1)的矩阵, 处理器编号为Pik, i=1n, k=1n+1(2)并行化分析消元的并行化: / O(n)for j=1 to n-1, each Pik Par-do /第j次消元Pij(ij): aij j, k=j+1n+1): aik i(n)=O(nx) 综上，串行算法的最优
7、时间为O(nx) 2iaikoldk)/aiiuntil i=1n| oldi - newi |cxi newiEnd Date16现代密码学理论与实践之五稀疏线性方程组的求解l线性方程组的并行化方法l稀疏线性方程组的迭代解法l高斯-赛德尔迭代法的并行化Date17现代密码学理论与实践之五线性方程方程的并行化方法l线性方程组选择算法的考虑因素l系数矩阵A的结构ldense Gaussian elimination, etclSparse iterative methodltriangular substitution, odd-even reductionlcertain PDEs multi
8、grid, etcl计算精度要求lGaussian elimination: more accurate, more expensivelConjugate gradients: less accurate, less expensivel计算环境要求larchitecture, available languages, compiler qualityllibraries?Date18现代密码学理论与实践之五线性方程方程的并行化方法l求解方法的并行化(1)直接解法的并行化(用于稠密线性方程组)- Gauss消去法(包括选主元的Gauss消去法)- Gauss-Jordan消去法- LU分解法
9、(2)迭代法的并行化(用于稠密和稀疏线性方程组)- Jacobi- Gauss-Seidel(可异步并行化)- Jacobi OverRelaxation(JOR)- Gauss-Seidel OverRelaxation(SOR)- Conjugate GradientDate19现代密码学理论与实践之五稀疏线性方程方程的迭代解法l迭代解法Date20现代密码学理论与实践之五高斯-赛德尔迭代法的并行化l由PDE离散产生的稀疏线性方程组(1)Laplace方程Date21现代密码学理论与实践之五高斯-赛德尔迭代法的并行化(2)由五点格式的离散化(假设g(x,y)=0)Date22现代密码学理论与实践之五高斯-赛德尔迭代法的并行化A为稀疏的块三对角矩阵 Date23现代密码学理论与实践之五高斯-赛德尔迭代法的并行化lGauss-Seidel迭代解法的并行化(1)两种串行算法的计算顺序及其并行化顺序1 顺序2 注: 顺序1难以并行化；顺序2可以小规模并行化Date24现代密码学理论与实践之五高斯-赛德尔迭代法的并行化(2) 红黑着色并行算法并行计算所有的红点并行计算所有的黑点重复、直至满足精度要求 Date25现代密码学理论与实践之五
