中国科学技术大学：《并行计算 Parallel Computing》课程教学资源（PPT课件讲稿）第三篇 并行数值算法 第十章 线性方程组的求解

中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 第三篇并行数值算法 第八章基本通讯操作 第九章稠密矩阵运算 第十章线性方程组的求解 第十一章快速傅里叶变换

第三篇 并行数值算法 第八章 基本通讯操作 第九章 稠密矩阵运算 第十章 线性方程组的求解 第十一章 快速傅里叶变换

中国料学火计算机科学与波术系 niversity of Science and Technology of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 第十章线性方程组的求解 10.1三角形方程组的求解 102三对角方程组的求解 10.3稠密线性方程组的求解 10.4稀疏线性方程组的求解

第十章 线性方程组的求解 10.1 三角形方程组的求解 10.2 三对角方程组的求解 10.3 稠密线性方程组的求解 10.4 稀疏线性方程组的求解

中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 101三角形方程组的求解 10.1.1基本术语 1012上三角方程组的求解

10.1 三角形方程组的求解 10.1.1 基本术语 10.1.2 上三角方程组的求解

中国料学火计算机科学与波术系 niversity of Science and Technology of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 基本术语 ■线性方程组的定义和符号 a1凶+a12X2+…+a1mx=b1 a21+a2×2+……+a2Xn=b2 Can, 1.1 +aix+ 十anX n n 记为 AX=b 12 b A X 国家高性能计算中心(合肥 2021/2/19

国家高性能计算中心（合肥） 5 2021/2/19 基本术语 ▪ 线性方程组的定义和符号 a1,1x1 + a1,2x2 + … + a1,nxn = b1 a2,1x1 + a2,1x2 + … + a2,nxn = b2 an,1x1 + an,1x2 + … + an,nxn = bn 记为 AX=b             =             =             = n n n n n n n n b b b b x x x x a a a a a a a a a A          2 1 2 1 1 2 2 1 2 2 2 1 1 1 2 1 ,

中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 101三角形方程组的求解 1011基本术语 10.1.2上三角方程组的求解

10.1 三角形方程组的求解 10.1.1 基本术语 10.1.2 上三角方程组的求解

中国料学火计算机科学与波术系 niversity of Science and Technology of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 上三角方程组的求解 ■上三角方程组的回代解法并行化 (1)SSD上的回代算法 Begin (for i=n downto l do (1.1)x=b/ai (1.2)for j=1 to i-1 do = 0 可养行化 endfor endfor End 国家高性能计算中心(合肥 2021/2/19

国家高性能计算中心（合肥） 7 2021/2/19 上三角方程组的求解 ▪ 上三角方程组的回代解法并行化 (1)SISD上的回代算法 Begin (1)for i=n downto 1 do (1.1)xi=bi /aii (1.2)for j=1 to i-1 do bj=bj -ajixi aji=0 endfor endfor End 可并行化

中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 上三角方程组的求解 ■上三角方程组的回代解法并行化 (2) SIMD-CREW上的并行回代算法 划分:p个处理器行循环带状划分 算法 Be egIn for i=n downto 1 do Pi ;=b;/a for all p, where 1≤j≤pdoH for k=j to i-1 step p do Pj k-akixi an;=0 endfor endfor endfor End //p(n)=n,t(n)=n 国家高性能计算中心(合肥 2021/2/19

国家高性能计算中心（合肥） 8 2021/2/19 上三角方程组的求解 ▪ 上三角方程组的回代解法并行化 (2)SIMD-CREW上的并行回代算法 - 划分: p个处理器行循环带状划分 - 算法 Begin for i=n downto 1 do xi=bi /aii for all Pj , where 1≤j≤p do for k=j to i-1 step p do bk=bk -akixi aki=0 endfor endfor endfor End // p(n)=n, t(n)=n P1 Pj P1 Pj 行 1 j 1+p j+p

中国料学火计算机科学与波术系 niversity of Science and Technology of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 第十章线性方程组的求解 101三角形方程组的求解 10.2三对角方程组的求解 10.3稠密线性方程组的求解 10.4稀疏线性方程组的求解

第十章 线性方程组的求解 10.1 三角形方程组的求解 10.2 三对角方程组的求解 10.3 稠密线性方程组的求解 10.4 稀疏线性方程组的求解

中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 102三对角方程组的求解 10.2.1直接求解法 102.2奇偶规约法

10.2 三对角方程组的求解 10.2.1 直接求解法 10.2.2 奇偶规约法

中国料学火计算机科学与波术系 niversity of Science and Technology of China D三P去RT三刊TFC口PTER三巴 NCE AND了N。LDr 三对角方程组的直接茲解法 Gau洧去法(难以并行化 ①消元 ②回代 注:由于三对角的 不变化的元素 方程组的特殊性, 次消元或一次 回代,只涉及邻 主元a 近一个方程,故 难以并行化。 待改变的元素 已消为0的元素 待消为0的元素 国家高性能计算中心(合肥 2021/2/19

国家高性能计算中心（合肥） 11 2021/2/19 i i 待改变的元素 不变化的元素 待消为0的元素 已消为0的元素 主元aii 三对角方程组的直接求解法 ▪ Gauss消去法(难以并行化) ①消元 ②回代 注：由于三对角的 方程组的特殊性， 一次消元或一次 回代，只涉及邻 近一个方程，故 难以并行化