稀疏线性方程组的求解共轭梯度算法步骤.ppt_第1页
稀疏线性方程组的求解共轭梯度算法步骤.ppt_第2页
稀疏线性方程组的求解共轭梯度算法步骤.ppt_第3页
稀疏线性方程组的求解共轭梯度算法步骤.ppt_第4页
稀疏线性方程组的求解共轭梯度算法步骤.ppt_第5页
已阅读5页,还剩36页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、2020/8/7,Parallel Algorithms Chapter 13 Numerical Algorithms,Spring, 2018,2020/8/7,Solving linear systems of equations : Example: solving ordinary or partial differential equations numerically Least squares problems: Example: fitting curves or surfaces to experimental data Eigenvalue problems: Examp

2、le: analyzing vibrations,Standard Linear Algebra Problems,2020/8/7,Structure of A: dense Gaussian elimination, etc Sparse iterative method triangular substitution, odd-even reduction certain PDEs multigrid Desired Accuracy: Example: Gaussian elimination: more accurate, more expensive Conjugate gradi

3、ents: less accurate, less expensive Computer System architecture, available languages, compiler quality libraries?,Choice of Algorithm,2020/8/7,讲授内容,13.1 稠密线性方程组求解 13.2 稀疏线性方程组的求解 13.3 非线性方程的求根,2020/8/7,13.1 稠密线性方程组求解,13.1.1 一般求解方法 1. 线性方程组的定义和符号 a1,1x1 + a1,2x2 + + a1,nxn = b1 a2,1x1 + a2,1x2 + + a

4、2,nxn = b2 an,1x1 + an,1x2 + + an,nxn = bn 记为 AX=b,2020/8/7,13.1 稠密线性方程组求解,2. 可并行化的求解方法 (1)直接解法的并行化 - Gauss消去法(包括选主元的Gauss消去法) - Gauss-Jordan消去法 - LU分解法 (2)迭代法的并行化(也可用于稀疏线性方程组) - Jacobi - Gauss-Seidel(可异步并行化) - Jacobi OverRelaxation(JOR) - Gauss-Seidel OverRelaxation(SOR) - Conjugate Gradient,2020/8

5、/7,3. 示例: 上三角方程组的回代解法并行化 (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,13.1 稠密线性方程组求解,可并行化,2020/8/7,13.1 稠密线性方程组求解,(2)SIMD-CREW上的并行回代算法 - 划分: p个处理器行循环带状划分 - 算法 Begin for i=n downto 1 do xi=bi/aii for all Pj, where 1jp do for k=j

6、to i-1 step p do bk=bk-akixi aki=0 endfor endfor endfor End / p(n)=n, t(n)=n,2020/8/7,13.1 稠密线性方程组求解,13.1.2 SIMD-CREW上的Gauss-Jordan算法 1.串行算法原理(一种直接解法) 消元: 通过初等行变换,将(A,b)化为主对角线矩阵, (方便起见, 记b为A的第n+1列) 求解: xj=aj,n+1/ajj 注: 选主元的Gauss-Jordan消去法,2020/8/7,13.1 稠密线性方程组求解,2. SIMD-CREW上的并行算法 (1)处理器: n2+n个处理器,

7、这些处理器排成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 aik-ajk(aij/ajj) end for 求解: for each Pjj(j=1n) Par-do: xj aj,n+1/ajj /O(1) (3)时间分析: t(n)=O(n), p(n)=O(n2), c(n)=O(n3) 成本最优?,2020/8/7,13.1 稠密线性方程组求解,3. 串行算法的最优时间 由于

8、 x=A-1b A-1b(假设已有A-1): O(n2) 求A-1: 求A-1需要: 2次n/2n/2矩阵的逆 i(n/2) 6次n/2n/2矩阵的乘 m(n/2) 2次n/2n/2矩阵的加 a(n/2) i(n)=2i(n/2)+6m(n/2)+2a(n/2) a(n/2)=n2/2, m(n/2)=O(n/2)x) 2 i(n)=O(nx) 综上, 串行算法的最优时间为O(nx) 2x2.5,2020/8/7,讲授内容,13.1 稠密线性方程组求解 13.2 稀疏线性方程组的求解 13.3 非线性方程的求根,2020/8/7,Newton nonlinear solver asymptot

9、ically quadratic,Krylov accelerator spectrally adaptive,Schwarz preconditioner parallelizable,Three VIPs for Iterative Methods,2020/8/7,13.1 稠密线性方程组求解,13.1.3 MIMD-CREW上的Gauss-Seidel算法 1.串行算法原理(一种迭代解法) 如果对某个k, 给定的误差允许值c有 则认为迭代是收敛的。 2.并行化分析 由于每次迭代需要使用本次迭代的前面部分值,因而难以 得到同步的并行算法,下面给出一个异步的并行算法。,2020/8/7,1

10、3.1 稠密线性方程组求解,3. MIMD异步并行算法 - N个处理器(Nn)生成n个进程, 每个进程计算x的一个分量 - 算法 Begin (1)for all i: oldi xi0, newi xi0 (2)生成进程i (3)进程i repeat (i) oldi newi (ii)newi (bi-kiaikoldk)/aii until i=1n| oldi - newi |c xi newi End,2020/8/7,13.1 稠密线性方程组求解,- 示例: P454例13.2 - 算法分析 (1)从算法运行过程知, oldk需要同时读, 即CREW; (2)读取/修改参数oldk

11、时,需要一个信号灯Sk进行控制; (3)异步算法难以进行时间分析.,2020/8/7,13.2 稀疏线性方程组的求解,13.2.1 三对角方程组的求解 1. Gauss消去法(难以并行化) 消元 回代,2020/8/7,13.2 稀疏线性方程组的求解,2. 奇偶规约求解法(可并行化) 三对角方程可以写成如下形式 fixi-1+gixi+hixi+1=bi i=1n f1=hn=0 - 串行算法描述 利用上下相邻方程消去偶序号方程中的奇下标变量: f2i-1x2i-2+g2i-1x2i-1+h2i-1x2i =b2i-1 f2ix2i-1 + g2ix2i + h2ix2i+1 =b2i f2i

12、+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,2020/8/7,13.2 稀疏线性方程组的求解,重复最终可得: case 1: case 2: g1x1+h1x2 =b1 . f2x1+g2x2+h2x3 =b2 . f3x2 +g3x3+h3x4=b3 . f4x3 +g4x4=b4 . 可以分别得到 g1x1+h1x2 =b1 或 g1x1+h1x2 =b1 f2x

13、1+g2x2 =b2 f2x1+g2x2+h2x3 =b2 f3x2+g3x3 =b3 直接解得 x1,x2 或 x1, x2, x3 回代求解x - 并行化分析: 、消去奇下标可以并行化;回代求解可以并行化,2020/8/7,13.2 稀疏线性方程组的求解,13.2.2 稀疏线性方程组的迭代解法 1. 迭代解法,2020/8/7,13.2 稀疏线性方程组的求解,2. 由PDE离散产生的稀疏线性方程组 (1)Laplace方程,2020/8/7,13.2 稀疏线性方程组的求解,(2)由五点格式的离散化(假设g(x,y)=0),2020/8/7,13.2 稀疏线性方程组的求解,A为稀疏的块三对角

14、矩阵,2020/8/7,13.2 稀疏线性方程组的求解,3. Gauss-Seidel迭代解法的并行化 (1)两种串行算法的计算顺序及其并行化 顺序1 顺序2 注: 顺序1难以并行化;顺序2可以小规模并行化,2020/8/7,13.2 稀疏线性方程组的求解,(2) 红黑着色并行算法 并行计算所有的红点 并行计算所有的黑点 重复、直至满足精度要求,2020/8/7,13.2 稀疏线性方程组的求解,4. 共轭梯度法的并行化 SOR等迭代方法依赖于很难选取的参数,而 Hestenes-Stiefel共轭梯度法可避免此困难。 下面考虑A为对称正定矩阵 (1)共轭梯度法的基本思想 将线性方程组AX=b的

15、求解问题化为一个二次齐次函数 的极小优化问题。,2020/8/7,13.2 稀疏线性方程组的求解,AX=b与q(X)的关系,2020/8/7,13.2 稀疏线性方程组的求解,重要定理,2020/8/7,13.2 稀疏线性方程组的求解,(2)最优斜量法(最速下降法) 求解最小优化问题,通常使用最速下降法,一般描述如下:,2020/8/7,13.2 稀疏线性方程组的求解,最速下降法的迭代步骤:,2020/8/7,13.2 稀疏线性方程组的求解,最速下降法的迭代图示: 优点: . 程序简单,每步迭代计算量少,存储省。 . 对于不太好的初始点X(0),往往也能收敛。 缺点: 最速下降法是名不符实的,一

16、般来说,它只有线性的收敛速度。,椭球面簇图: q(x)=Ci q(x1,x2)=Ci,2020/8/7,13.2 稀疏线性方程组的求解,(3)共轭梯度法 1952年,Hestenes和Stiefel发现了共轭梯度法,对于n阶的线性方程组, 至多只要n步就能得到解。 以n2为例 从椭圆q(X)=q(X(0)上的X(0)点出发,用最优斜量法得到X(1), d(0)=-r(0)=b-AX(0) (负梯度方向) r(1)=AX(1)-b, 可以验证(r(0), r(1)=0, 说明-r(1)是q(X)=q(X(1)的内法向(负梯度). 第二步不走-r(1)方向,而走共轭方向p(1), 可以验证p(1)

17、,过椭圆中心X*. p(1)方向的极小点就是X*.,2020/8/7,13.2 稀疏线性方程组的求解,共轭梯度算法步骤:,2020/8/7,13.2 稀疏线性方程组的求解,共轭梯度法的并行化分析(思考题): 考虑PRAM模型 - 数据划分 每个处理器存有A的若干行,以及b、d、r的部分分量 - 计算和通讯 计算:矩阵和向量乘积、向量内积 时间? 通讯:矩阵和向量乘积、向量内积计算时的数据交换 时间? - 总时间?,2020/8/7,13.2 稀疏线性方程组的求解,稀疏系数矩阵的存储方法,2020/8/7,13.2 稀疏线性方程组的求解,稀疏系数矩阵的存储方法,2020/8/7,讲授内容,13.

18、1 稠密线性方程组求解 13.2 稀疏线性方程组的求解 13.3 非线性方程的求根,2020/8/7,13.3 非线性方程的求根,13.3.1 SIMD-CREW上的等分求根算法 1. 二分法求根原理 若f(x)在a, b上是连续的, 且有f(a)f(b)0, 则存在z(a, b) 使f(z)=0 2. SISD上的二分求根算法: P458算法13.6 3. SIMD-CREW上的等分求根算法 repeat 将a,b分为N等分, 等分点a=x0x1x2xN=b, Pi计算f(xi) 存在某个f(xi)=0, 输出xi 若不成立, 找xi,xi+1, 使f(xi)f(xi+1)0, axi, bxi+1 until |a-b|c 并行时间O(logN+1|a-b|),2020/8/7,13.3 非线性方程的求根,13.3.2 MIMD-CREW上的Newton求根算法 1. Newton求根法 设f(x)在a, b上是连续且f(x)0, f”(x)0, f(a)f(b)0, 取x0=b 第n+1次迭代: xn+1=xn-f(xn)/f

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论