《并行计算：第十章 线性方程组的求解》由会员分享，可在线阅读，更多相关《并行计算：第十章 线性方程组的求解（36页珍藏版）》请在金锄头文库上搜索。
1、并行计算 Parallel Computing 主讲人 徐 云 Spring, 2014Spring, 2014 第三篇 并行数值算法 第九章 稠密矩阵运算 第十章 线性方程组的求解 第十一章 快速傅里叶变换 第十二章 数值计算的基本支撑技术 第十章 线性方程组的求解 10.1 三角形方程组的求解 10.1.1 基本术语 10.1.2 上三角方程组的求解 10.2 三对角方程组的求解 10.3 稠密线性方程组的求解 10.4 稀疏线性方程组的求解 国家高性能计算中心（合肥） 4 基本术语 ? ? 线性方程组的定义和符号线性方程组的定义和符号 a a a a 1,11,11,11,1 x x x
2、 x1 1 1 1 + a+ a+ a+ a1,2 1,21,21,2 x x x x2 2 2 2 + + + + + a+ a+ a+ a1,n 1,n1,n1,n x x x xn n n n = b= b= b= b 1 1 1 1 a a a a 2,12,12,12,1 x x x x1 1 1 1 + a+ a+ a+ a2,1 2,12,12,1 x x x x2 2 2 2 + + + + + a+ a+ a+ a2,n 2,n2,n2,n x x x xn n n n = b= b= b= b 2 2 2 2 a a a a n,1n,1n,1n,1 x x x x1 1
3、1 1 + a+ a+ a+ an,1 n,1n,1n,1 x x x x2 2 2 2 + + + + + + + + a a a an,n n,nn,nn,n x x x xn n n n = = = = b b b b n n n n 记为记为AX=bAX=b = = = nnnnnn n n b b b b x x x x aaa aaa aaa A ? ? ? ? ? 2 1 2 1 21 22221 11211 , 第十章 线性方程组的求解 10.1 三角形方程组的求解 10.1.1 基本术语 10.1.2 上三角方程组的求解 10.2 三对角方程组的求解 10.3 稠密线性方程组
4、的求解 10.4 稀疏线性方程组的求解 国家高性能计算中心（合肥） 6 上三角方程组的求解 ? ? 上三角方程组的回代解法并行化上三角方程组的回代解法并行化 (1)SISD(1)SISD上的回代算法上的回代算法 BeginBegin (1)for i=n (1)for i=n downtodownto 1 do1 do (1.1)x(1.1)x i i =b=b i i / /a a ii ii (1.2)for j=1 to i(1.2)for j=1 to i- -1 do1 do b b j j =b b j j - -a a ji jix x i i a aji ji =0=0 end
5、forendfor endforendfor EndEnd 可并行化可并行化 国家高性能计算中心（合肥） 7 上三角方程组的求解 ? ? 上三角方程组的回代解法并行化上三角方程组的回代解法并行化 (2)SIMD(2)SIMD- -CREWCREW上的并行回代算法上的并行回代算法 - - 划分划分: p: p个处理器行循环带状划分个处理器行循环带状划分 - - 算法算法 BeginBegin for i=n for i=n downtodownto 1 do1 do x x i i =b=b i i / /a a ii ii for all for all P P j j , where 1,
6、where 1j jp dop do for k=j to ifor k=j to i- -1 step p do1 step p do b bk k =b b k k - -a aki ki x x i i a aki ki =0=0 endforendfor endforendfor endforendfor End / End / p(np(n)=n, )=n, t(nt(n)=n)=n P1 Pj P1 Pj 行 1 j 1+p j+p 第十章 线性方程组的求解 10.1 三角形方程组的求解 10.2 三对角方程组的求解 10.2.1 直接求解法 10.2.2 奇偶规约法 10.3 稠
7、密线性方程组的求解 10.4 稀疏线性方程组的求解 国家高性能计算中心（合肥） 9 三对角方程组的直接求解法 ? ? GaussGauss消去法消去法( (难以并行化难以并行化) ) 消元消元 回代回代 注：由于三对角的注：由于三对角的 方程组的特殊性，方程组的特殊性， 一次消元或一次一次消元或一次 回代，只涉及邻回代，只涉及邻 近一个方程，故近一个方程，故 难以并行化。难以并行化。 第十章 线性方程组的求解 10.1 三角形方程组的求解 10.2 三对角方程组的求解 10.2.1 直接求解法 10.2.2 奇偶规约法 10.3 稠密线性方程组的求解 10.4 稀疏线性方程组的求解 国家高性能
8、计算中心（合肥） 11 三对角方程组的奇偶规约求解法 ? ? 奇偶规约求解法奇偶规约求解法( (可并行化可并行化) ) 三对角方程可以写成如下形式三对角方程可以写成如下形式 f f i i x x i i- -1 1 +g+g i i x x i i +h+h i i x x i+1i+1=b =b i i i=1ni=1n f f 1 1 =h h n n =0=0 ? ? 串行算法描述串行算法描述 利用上下相邻方程消去偶序号方程中的奇下标变量利用上下相邻方程消去偶序号方程中的奇下标变量: : f f 2i2i- -1 1 x x 2i2i- -2 2+g +g2i 2i- -1 1 x x
9、 2i2i- -1 1+h +h2i 2i- -1 1 x x 2i 2i =b =b2i 2i- -1 1 f f 2i2i x x 2i2i- -1 1 + g+ g2i 2i x x 2i 2i + + h h2i2i x x 2i+1 2i+1 =b=b2i 2i f f 2i+12i+1 x x 2i 2i +g +g2i+1 2i+1 x x 2i+12i+1+h +h2i+1 2i+1 x x 2i+2 2i+2 =b =b2i+1 2i+1 2i2i- -1 1方程乘上某个数消去方程乘上某个数消去2i2i方程中的方程中的f f2i 2i x x 2i2i- -1 1项 项, 2
10、i+1, 2i+1方程乘上某个数方程乘上某个数 消去消去2i2i方程中的方程中的h h2i 2i x x 2i+12i+1项 项, , 使使2i2i方程变为方程变为 i i x x 2i2i- -2 2+ + i i x x 2i2i+ + i i x x 2i+22i+2= = i i i=1,2,i=1,2,n/2,n/2 国家高性能计算中心（合肥） 12 重复重复最终可得最终可得: : case 1: casecase 1: case 2: 2: g g1 1x x1 1 +h+h 1 1x x 2 2 =b =b1 1 . . f f 2 2x x 1 1 +g+g 2 2x x2 2
11、 +h+h 2 2x x3 3 =b=b2 2 . . f f 3 3x x 2 2 +g +g 3 3x x3 3 +h+h 3 3x x4 4 =b=b3 3 . . f f 4 4x x 3 3 +g +g 4 4x x 4 4 =b =b4 4 . . 可以分别得到可以分别得到 g g1 1x x1 1 +h+h 1 1x x 2 2 =b =b1 1 或 或 g g1 1x x1 1 +h+h 1 1x x 2 2 =b =b 1 1 f f 2 2x x 1 1 +g+g 2 2x x 2 2 =b =b2 2 f f 2 2x x 1 1 +g+g 2 2x x2 2 +h+h
12、2 2x x 3 3 =b =b2 2 f f 3 3x x2 2 +g+g 3 3x x 3 3 =b =b 3 3 解得解得 x x 1 1 ,x,x2 2 或 或 x x 1 1 , x, x 2 2 , x, x 3 3 回代求解回代求解x x ? ? 并行化分析并行化分析: :、消去奇下标可以并行化；消去奇下标可以并行化； 回代求解可以并行化回代求解可以并行化 三对角方程组的奇偶规约求解法 第十章 线性方程组的求解 10.1 三角形方程组的求解 10.2 三对角方程组的求解 10.3 稠密线性方程组的求解 10.3.1 有回代的高斯消去法 10.3.2 无回代的高斯-约旦法 10.3
13、.3 迭代求解的高斯-赛德尔法 10.4 稀疏线性方程组的求解 国家高性能计算中心（合肥） 14 有回代的高斯消去法 ? ? 算法基本原理算法基本原理 ? ? 求解过程分为消元和回代两个阶段，消元是将系数矩阵求解过程分为消元和回代两个阶段，消元是将系数矩阵 A A化为上三角阵化为上三角阵T T，然后对，然后对TX=cTX=c进行回代求解。进行回代求解。 ? ? 消元过程中可以应用选主元方法，增加算法的数值稳定消元过程中可以应用选主元方法，增加算法的数值稳定 性。性。 ? ? 下面是消元过程图：下面是消元过程图： 国家高性能计算中心（合肥） 15 有回代的高斯消去法 ? ? 并行化分析并行化分析
14、 ? ? 消元和回代均可以并行化；消元和回代均可以并行化； ? ? 选主元也可以并行化；选主元也可以并行化； ? ? 消元过程的并行化图示：处理器按行划分消元过程的并行化图示：处理器按行划分 主元行 图10.1 待改变的元素 不变化的元素 待消为0的元素 已消为0的元素 可并行化部分 第十章 线性方程组的求解 10.1 三角形方程组的求解 10.2 三对角方程组的求解 10.3 稠密线性方程组的求解 10.3.1 有回代的高斯消去法 10.3.2 无回代的高斯-约旦法 10.3.3 迭代求解的高斯-赛德尔法 10.4 稀疏线性方程组的求解 国家高性能计算中心（合肥） 17 无回代的高斯-约旦法 ? ? 串行算法原理串行算法原理 消元消元: : 通过初等行变换通过初等行变换, ,将将( (A,bA,b) )化为主对角线矩阵化为主对角线矩阵, , ( (方便起见方便起见, , 记记b b为为A A的第的第n+1n+1列列) ) 求解求解: : x x j j =a=a j,n+1 j,n+1/a /a jj jj
