线性方程组的求解.ppt

1、并行修正，第三篇并行数值算法第八章基本通信操作第九章稠密矩阵运算第十章线性方程式群的求解第十一章快速傅立叶变换， 第十章线性方程组的求解10.1三角形方程组的求解10.2三对角方程组的求解10.3稠密线性方程组的求解10.4稀疏线性方程组的求解10.1三角形方程组的求解10.1.1基本用语10.1.2上三角形方程组的求解，5，5， 2020/8/5、基本术语、线性方程组的定义和符号a1、1x1a1、2x2a1、nxn=b2 an 1x2 an、nxn=bn为AX=b、10.1三角形方程组的求解10.1.1基本术语10.1.2上三角形方程组的求解、7、7， 2020/8/5，上三角方程组的求解，

2、上三角方程组的回代解法并行化(1)SISD上的回代算法begin (1) fori=ndown to1do (1.1) Xi=bi/aii (1.2) forj=1toi 1上三角方程组的求解，上三角方程组的回代SIMD-CREW上的并行回圈代算法-分割： p个处理器行循环带状分割-算法begin fori=ndown to1doxi=bi/aiiforallpj，where1jpdo fork=jtoi-1 steppdobk=， 第10章线性方程组的求解10.1三角形方程组的求解10.2三对角方程组的求解10.3稠密线性方程组的求解10.4稀疏线性方程组的求解，10.2.1直接求解法10.

3、2奇数规则法，11，2020/8/5，三对角方程组Gauss消去法(难以并行化)消元的代注：三对角的方程组、10.2三对角方程组的求解10.2.1直接求解法10.2.2奇偶规约法，13，2020/8/5，三对角方程组的直接求解法，奇偶协议求解法(可并行化)三对角方程组， 通过上下邻接方程式删除偶数编号方程式中奇数下标变量3360 f2I-1 x2I-2 g2I-1 x2I-1 x2I， fixi-1 gixi hixi 1=bi i=1n f1=hn=0串行算法，其中b2if2I1x2ig2I1x2I1h2I2I2=b2I 12i-1方程乘以某个数量的消去2 I方程的f2ix2i-1项与某个数

4、的消去2i方程式的h2ix2i 1项相乘，2i方程式成为ix2i-2ix2iix2i2的2020/8/5， 三对角方程式的直接解法重复，最终得到3360 case 13360 case 23360 g1x1x2=b1. f2x1g2x2x3=b2. f3x2g3x3x4=b3. f4x3g4x4=b4.分别得到g1x1h1的1 g 2 x3=b3解求x1、x2或x1、x2、x3代解x并行化分析：可消除奇数下标。 回代求解可以并行化， 第10章线性方程式的求解10.1三角形方程式的求解10.2三对角方程式的求解10.3稠密线性方程式的求解10.4稀疏线性方程式的求解10.3稠密线性方程式群的求解

5、10.3.1次代的高斯消去法10.3.2次代的高斯约旦法10.3.3反复求解的高斯单元法，17，2020/8/8 应用回代的高斯消元法消元过程中选择主元的方法可以提高算法的数值稳定性。消元过程图如下：18，2020/8/5，有回代的高斯消去法，并行化分析消元和回代一起选择可以并行化的主元也可以并行化消元过程的并行化图：处理器按行分开， 10.3稠密线性方程组求解10.3.1次世代的高斯消去法10.3.2次世代的高斯约旦法10.3.3反复求解的高斯德尔法，20，2020/8 b )主对角线矩阵化，(为了方便起见，将b记作a的第n 1列) : xj=aj，n1/n 1 无回代的高斯约旦法，求simd的k=1n 1 (2)并行化分析消除元的并行化： /O(n) for j=1 to n-1，each Pik Par-do /第j次消除元pij (ij ) 333660 k=j1n1) 3360 aik aik 寻求end for 3360 foreachpjj (j=1n ) par-do 3360 xjaj，n1/、22，2020/8/5、无代高斯-约旦法、成本最好吗？ 串行算法的