10.3 稠密线性方程组的求解
10.3.1 有回代的高斯消去法 10.3.2 无回代的高斯-约旦法 10.3.3 迭代求解的高斯-赛德尔法
有回代的高斯消去法
算法基本原理
求解过程分为消元和回代两个阶段，消元是将系数矩阵 A化为上三角阵T，然后对TX=c进行回代求解。 消元过程中可以应用选主元方法，增加算法的数值稳定 i 性。 下面是消元过程图：
计算精度要求
Gaussian elimination: more accurate, more expensive Conjugate gradients: less accurate, less expensive
计算环境要求
architecture, available languages, compiler quality libraries?
j i 1 k xik 1 (1 ) xik (bi aij x k a x ij j ) / aii j j i j i
2014-5-5 25
第十章 线性方程组的求解
10.1 三角形方程组的求解 10.2 三对角方程组的求解 10.3 稠密线性方程组的求解 10.4 稀疏线性方程组的求解
10.4 稀疏线性方程组的求解
10.4.1 线性方程组的并行化方法 10.4.2 稀疏线性方程组的迭代解法 10.4.3 高斯-赛德尔迭代法的并行化
2014-5-5 22
10.3 稠密线性方程组的求解
10.3.1 有回代的高斯消去法 10.3.2 无回代的高斯-约旦法 10.3.3 迭代求解的高斯-赛德尔法
迭代求解的高斯-赛德尔法
串行算法原理
k 1 i
1 k 1 k x aij x j aij x j bi aii j i j i 如果对某个k, 给定的误差允许值c有

②求解: xj=a’j,n+1/a’jj
2014-5-5
20
无回代的高Leabharlann -约旦法 SIMD-CREW上的并行算法
(1)处理器: n2+n个处理器, 这些处理器排成n×(n+1)的矩阵,
处理器编号为Pik, i=1~n, k=1~n+1 (2)并行化分析 ①消元的并行化: // O(n) for j=1 to n-1, each Pik Par-do //第j次消元 Pij(i<>j): aij <— 0 Pik(i<>j, k=j+1~n+1): aik <— aik-ajk(aij/ajj) end for ②求解: for each Pjj(j=1~n) Par-do: xj <— aj,n+1/ajj //O(1) (3)时间分析: t(n)=O(n), p(n)=O(n2), c(n)=O(n3) 成本最优？
2014-5-5 13
②重复①最终可得: case 1: g1x1+h1x2 =b1 f2x1+g2x2+h2x3 =b2 f3x2 +g3x3+h3x4=b3 f4x3 +g4x4 =b4 可以分别得到 g1x1+h1x2 =b1 或 f2x1+g2x2 =b2
解得 x1,x2 或 x1, x2, x3 ③回代求解x
图10.1
2014-5-5
18
10.3 稠密线性方程组的求解
10.3.1 有回代的高斯消去法 10.3.2 无回代的高斯-约旦法 10.3.3 迭代求解的高斯-赛德尔法
无回代的高斯-约旦法
串行算法原理
①消元: 通过初等行变换,将(A,b)化为主对角线矩阵, (方便起见, 记b为A的第n+1列)
①消元 ②回代 注：由于三对角的 方程组的特殊性， 一次消元或一次 回代，只涉及邻 近一个方程，故 难以并行化。
已消为 0 的元素
i
不变化的元素
i
主元aii
待改变的元素 待消为 0 的元素
11
2014-5-5
10.2 三对角方程组的求解
10.2.1 直接求解法 10.2.2 奇偶规约法
三对角方程组的直接求解法
并行计算
第三篇 并行数值算法
第八章 基本通讯操作 第九章 稠密矩阵运算 第十章 线性方程组的求解 第十一章 快速傅里叶变换
第十章 线性方程组的求解
10.1 三角形方程组的求解 10.2 三对角方程组的求解 10.3 稠密线性方程组的求解 10.4 稀疏线性方程组的求解
10.1 三角形方程组的求解
可并行化
2014-5-5
7
上三角方程组的求解
上三角方程组的回代解法并行化
(2)SIMD-CREW上的并行回代算法 - 划分: p个处理器行循环带状划分 - 算法 P 1 Begin P j for i=n downto 1 do xi=bi/aii for all Pj, where 1≤j≤p do P1 for k=j to i-1 step p do P j bk=bk-akixi aki=0 endfor endfor endfor End // p(n)=n, t(n)=n
x1 x x 2 , xn
2014-5-5
b1 b b 2 bn
5
10.1 三角形方程组的求解
10.1.1 基本术语 10.1.2 上三角方程组的求解
上三角方程组的求解
上三角方程组的回代解法并行化
(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
奇偶规约求解法(可并行化)
三对角方程可以写成如下形式 fixi-1+gixi+hixi+1=bi i=1~n f1=hn=0 串行算法描述
①利用上下相邻方程消去偶序号方程中的奇下标变量: f2i-1x2i-2+g2i-1x2i-1+h2i-1x2i =b2i-1 f2ix2i-1 + g2ix2i + h2ix2i+1 =b2i f2i+1x2i +g2i+1x2i+1+h2i+1x2i+2 = b2i+1 2i-1方程乘上某个数消去2i方程中的f2ix2i-1项, 2i+1方程乘上某个数 消去2i方程中的h2ix2i+1项, 使2i方程变为 αix2i-2+βix2i+γix2i+2=ηi i=1,2,…,n/2
Begin
(1)oldi xi0, newi xi0 (2)生成进程i (3)进程i repeat (i) oldi newi (ii)newi (bi-∑k<iaik×oldk-∑k>iaik×oldk)/aii until ∑i=1~n| oldi - newi |<c xi newi End
10.1.1 基本术语 10.1.2 上三角方程组的求解
基本术语
线性方程组的定义和符号
a1,1x1 + a1,2x2 + … + a1,nxn = b1 a2,1x1 + a2,1x2 + … + a2,nxn = b2 an,1x1 + an,1x2 + … + an,nxn = bn
记为 AX=b a11 a12 a1n a a a 22 2n A 21 , a a a n2 nn n1
2014-5-5 29
10.4 稀疏线性方程组的求解
10.4.1 线性方程组的并行化方法 10.4.2 稀疏线性方程组的迭代解法 10.4.3 高斯-赛德尔迭代法的并行化
稀疏线性方程方程的迭代解法
迭代解法
(1) Jacobi: xik 1 (bi aij x k j ) / aii
行 1 j 1+p j+p
2014-5-5
8
第十章 线性方程组的求解
10.1 三角形方程组的求解 10.2 三对角方程组的求解 10.3 稠密线性方程组的求解 10.4 稀疏线性方程组的求解
10.2 三对角方程组的求解
10.2.1 直接求解法 10.2.2 奇偶规约法
三对角方程组的直接求解法
Gauss消去法(难以并行化)
不变化的元素
i
主元行
待改变的元素 已消为 0 的元素
待消为 0 的元素
2014-5-5
图10.1
17
有回代的高斯消去法
并行化分析
消元和回代均可以并行化； 选主元也可以并行化； 消元过程的并行化图示：处理器按行划分
i
不变化的元素 已消为 0 的元素
i
主元行
可并行化部分
待改变的元素
待消为 0 的元素
a11 a21 an1 a12 a1n a22 a2 n an 2 ann a1,n 1 a2,n 1 an ,n 1 a11 a22 ann ,n 1 a1 ,n 1 a2 ,n 1 an
j i j i j i 1 k (2) Gauss Seidel: xik 1 (bi aij x k a x ij j ) / aii j
(3) JOR : (4) SOR :
xik 1 (1 ) xik (bi aij x k j ) / aii
2014-5-5 28
线性方程方程的并行化方法
求解方法的并行化