中国科技大学并行计算课件10线性方程组的求解
37页1、并 行 计 算 中国科学技术大学计算机科学与技术系国家高性能计算中心(合肥)2004年12月Date1现代密码学理论与实践之五第三篇 并行数值算法 第八章 基本通讯操作 第九章 稠密矩阵运算 第十章 线性方程组的求解 第十一章 快速傅里叶变换 Date2现代密码学理论与实践之五第十章 线性方程组的求解 10.1 三角形方程组的求解 10.2 三对角方程组的求解 10.3 稠密线性方程组的求解 10.4 稀疏线性方程组的求解 Date3现代密码学理论与实践之五10.1 三角形方程组的求解 10.1.1 基本术语 10.1.2 上三角方程组的求解 Date4现代密码学理论与实践之五 基本术语 线性方程组的定义和符号 a1,1x1 + a1,2x2 + + a1,nxn = b1 a2,1x1 + a2,1x2 + + a2,nxn = b2 an,1x1 + an,1x2 + + an,nxn = bn 记为 AX=b Date5现代密码学理论与实践之五10.1 三角形方程组的求解 10.1.1 基本术语 10.1.2 上三角方程组的求解 Date6现代密码学理论与实践之五 上三角方程组的
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可并行化Date7现代密码学理论与实践之五 上三角方程组的求解 上三角方程组的回代解法并行化 (2)SIMD-CREW上的并行回代算法 - 划分: p个处理器行循环带状划分 - 算法 Begin for i=n downto 1 do xi=bi/aii for all Pj, where 1jp do for k=j to i-1 step p do bk=bk-akixi aki=0 endfor endfor endfor End / p(n)=n, t(n)=nDate8现代密码学理论与实践之五第十章 线性方程组的求解 10.1 三角形方程组的求解 10.2 三对角方程组的求解 10.3 稠密线性方程组的求解 10.4 稀疏线性方程组的求解 Date9现代密码学理论与实践之五10.2 三对角方程组的求解 10.2.
3、1 直接求解法 10.2.2 奇偶规约法 Date10现代密码学理论与实践之五 三对角方程组的直接求解法 Gauss消去法(难以并行化) 消元 回代 注:由于三对角的 方程组的特殊性, 一次消元或一次 回代,只涉及邻 近一个方程,故 难以并行化。Date11现代密码学理论与实践之五10.2 三对角方程组的求解 10.2.1 直接求解法 10.2.2 奇偶规约法 Date12现代密码学理论与实践之五 三对角方程组的直接求解法 奇偶规约求解法(可并行化) 三对角方程可以写成如下形式 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+1x2i +g2i+1x2i+1+h2i+1x2i+2 = b2i+1 2i-1方程乘上某个数消去2i方程中的f2ix2i-1项, 2i+1方程乘上某个数 消去2i方程中的h2ix2i+1项, 使2i方程变为 ix2i-2+ix2i
4、+ix2i+2=i i=1,2,n/2Date13现代密码学理论与实践之五 三对角方程组的直接求解法重复最终可得: case 1: case 2: g1x1+h1x2 =b1 . f2x1+g2x2+h2x3 =b2 . f3x2 +g3x3+h3x4=b3 . f4x3 +g4x4 =b4 . 可以分别得到 g1x1+h1x2 =b1 或 g1x1+h1x2 =b1 f2x1+g2x2 =b2 f2x1+g2x2+h2x3 =b2 f3x2+g3x3 =b3 解得 x1,x2 或 x1, x2, x3 回代求解x 并行化分析: 、消去奇下标可以并行化; 回代求解可以并行化Date14现代密码学理论与实践之五第十章 线性方程组的求解 10.1 三角形方程组的求解 10.2 三对角方程组的求解 10.3 稠密线性方程组的求解 10.4 稀疏线性方程组的求解 Date15现代密码学理论与实践之五10.3 稠密线性方程组的求解 10.3.1 有回代的高斯消去法 10.3.2 无回代的高斯-约旦法 10.3.3 迭代求解的高斯-赛德尔法Date16现代密码学理论与实践之五 有回代的高斯消去法
《中国科技大学并行计算课件10线性方程组的求解》由会员东***分享,可在线阅读,更多相关《中国科技大学并行计算课件10线性方程组的求解》请在金锄头文库上搜索。
幼儿园大班科学活动《智能留言机》课件
幼儿园大班语言绘本阅读《手电筒看见了什么》PPT
幼儿园小班科学《教宝宝认识动物》课件
幼儿园中班语言《灰狼家的小饭桶们》教案
【国家审计报告】审计报告W-06审计处罚决定书
【企业财务管理办法】会计档案管理办法
【员工主动离职-风险防范】劳动争议判决书
【员工被动离职-后续工作】70-070员工违反有关商业秘密的约定可以索赔吗
【员工被动离职-辞退申请】第六节 员工任免通知书
【员工被动离职-后续工作】70-050因员工的原因使服务期无法完成可以索赔吗
企业岗位管理制度12办公室行为规范
企业岗位管理制度30离职人员薪资发放通知单
幼儿园春游活动美丽的公园教案
呼职院电力机车制动机讲义11高速列车和重载列车制动
武理工《运输管理》教案第1章 运输系统
中海大海洋化学讲义02海洋的形成和海水的组成——兼论地球上水的起源、变迁和循环
武理工船舶柴油机习题库及答案04燃油喷射和燃烧
厦大海洋生态学课件07海洋初级生产力
华北理工水声学课件05声波在目标上的反射和散射-1目标强度及常见声纳目标的目标强度的一般特征
武理工船舶结构与设备课件02船体结构与管系-4专用船特殊船体结构特点
2022-03-29 50页
2022-03-24 39页
2022-03-24 45页
2022-03-24 14页
2022-03-24 17页
2021-11-22 77页
2021-11-22 68页
2021-11-22 55页
2021-11-22 96页