下载  >  开发技术  >  其它  > 论文研究-用部分选主元的高斯消去法并行求解线性方程组 .pdf

论文研究-用部分选主元的高斯消去法并行求解线性方程组 .pdf 评分

用部分选主元的高斯消去法并行求解线性方程组,刘向娇,刘佳梅,高斯消去法,又称高斯消元法,实际上就是我们俗称的加减消元法。数学上,高斯消去法或称高斯-约当消去法,由高斯和约当得名(很��
国武技论文在线 http:/www.paper.edu.cn 第·步将4选为主元素,并把主元素所在的行定为主元行,然后将主元行换到第行得 4254 10.51.251 第一步消元0 0.5-1 1207 01.51.256 10.51.251 10.51.251 第二步消元 0.250.5 第三步消元小01 0.250.5 00-0.8755.25 00 消元过程的结果归结到下列三角形方程组 1+0.52+1.253=1 0.25=0.5 回代,得 =9 串行部分选主元高斯消去算法 先部分选主元然后回代的串行高斯消去算法如下所示: 0 to n-1 loc[1] endfor fori←0ton-l 找到主元行 picked} magnitude←0 forj←iton-1 ifa[loc], i>magnitude magnitude←|aloc],i endif endfor cmp loc[i← -loclpicked loc[ picked]←mp 将第i列中位于未标记行中的元索消为0} forj←i-1ton-1 alocu, i/alloci],i fork←i+1ton+1 3 国武技论文在线 http:/www.paper.edu.cn a[loc],k]←a[locj],k]-a[loc[i],k]×t endfor endor endfor {回代} fori←-n-1 down to0 x[i]a[loc[], n]/a[loci],i] forj←0toi-1do a[loc],n]←a[locj],n]-x[×a[loc[j,i endfor endfor 该算法有两个值得注意的特性: 1.没有独立的数组来存储向量b,而是用b邻接A创建个n行n+1列的增广矩阵。 因此,在这个算法中a代表这个增广矩阵 2.算法每次迭代中间接地访问主元行,而不是直接地将主元行和第i行相父换。数组 元素loci记录了第i次达代中所用的主元行的下标[4] 并行部分选主元高斯消去算法 算法思想 在上面的串行算法中位于最内层下标为k的for循环和位于中间层的下标为j的for循 环都可以拿来并行执行,换句话说,一旦找到主元行,对所有没被标记的行的修改就可以同 时进行。在每一行内,一旦系数a[oc],ia[loc[,订被计算出来了,那么这一行内从位置 i+1开始的n1个元素的修改工作也可以同时进行 在并行化的过程中,由于高斯消去法是利用主元行i对其余各行j>i),作初等行变换, 各行计算之间没有数据相关关系,因此可以对矩阵A按行划分。考虑到在计算过程中处理 器之间的负载均衡,对A采用行交叉划分。设处理器个数为p,矩阵A的阶数为n,m|/1, 对矩阵A行交叉划分后,编号为i(i=0,1,…,p-1)的处理器含有A的第i,ip,…,i(m-1)p 行和向量B的第i,ip,…,i(m-1)p一共m个元素 矩阵划分好以后,接下来的主要⊥作是寻找主元行。我们发现为了决定主元行,需要对 分布在不同处理器中的第i列的各个元素进行规约。我们可以把这过程称为巡回赛,因为 与主元行的第i列中存储的具体数值(胜利者的得分)相比,我们对主元行的位置(胜利者的身 份)更感兴趣 在第i次迭代进行的过程中,主元行的确定需要两个步骤。首先,每个进程在它所负责 的未标记的行中寻找在第列数值最大的那一行。第二,进程加入寻找主元行的巡同赛[S] 在每次迭代过稈中,这一步都是首先要完成的,之后还有一个涉及通信的仟务,如图1 所示。为了计算a[j,k]的新值,其对应的任务需要访问a[,i、a[ picked,门和a[ Picked,k 的值。每个任务至少分配到A的一行,所以这个任务既然控制了a[j,k],那么也就控制着 面,i]。但是a[ picked,i和 alpicked,k]的值可能为另外一个仨务所控制。因此,我们还需 要做次广播[3] 国武技论文在线 http:/www.paper.edu.cn aCk in0 [picked picked picked]k 图1迭代时通信任务图 算法实现 输入:系数矩阵 常数向量 输出:解向量 对所有处坦器 my rank( my rank=0,…,p-1)同时执行如下的算法 倖消去过程* i=0m-1 (1. 1) (my rank j) (ii)Imax[OFai+l, vI (i)k-i+1m-1 t=v n-1 (ak,切)max]) InaX [O-ak, t], Imax[1]-k Imax 2=t, Imax 3=my rank (1.2) (i)vi*p+ i1)[or-ali, v] 1 (akk, t)>lmax[oD Imax[o=ak, t], Imax[1]k max12」t,lmax3」= my rank (1.3)将每一个处里器中的Imax元素广播到其他所有处理器中 (1. 4) maxvalve=getpivort( max), maxrow-getrow(max) (15) (i([maxrank=j] and [i,maxrow]) Innerexchangerow() 国武技论文在线 http:/www.paper.edu.cn (i)( maxrank为) outerexchangerowO (1.6) nk ()k=v+1n-1 ali, k]=ali, k]ali i) bil=bila「i ai, v=1 (ill) k- tlk」=ali,k」 (iv)fn=bi] ()广播主行到所有处理器 接收广播来的主行元素存与数组f中 (1.7) ly rank≤j) k-i+I m-1 ak, w=a[k, w]-flw]a[ (iibkk-b[k]fn]ak,v (18) (mv ran k-i m -1 ak, w=ak, wl-flwrak, v] 泮*回代过程* sum=0.0 i=m-1 0 0 (my rank j) (i)[*p+j](b[i]-sum[i]/a[i, i*p+j 〔i)将[i*p+j播到所有处理器中 sum[k]=sum[k]ak, i*p+tj] [pti /*非主行所在的处理器 (iv)接收广播米的[p+j的值 (v)(my rank>j) k-0i-1 sum kI= sunk]ak,i*p小j[pj」 nk< sum[k]=sum[k]+akk, i pj][i* p+j 国武技论文在线 http:/www.paper.edu.cn 算法分析 在第ⅰ次迭代主元行确定的两个步骤中,每个进稈在它所负责的未标记的行中寻找在第 列中最大的那一行的时间复杂度是Onp),而进程加入寻找主元行的巡回赛的时间复杂度 是O(logp) 综合考虑通信的总开销,我们发现亩向行的部分选主元的高斯消去算法的总消息延迟是 O( blog),而总的消息传输时间是O(n2ogp)6] 参考文献 ]陈国良安虹陈崚等.并行算法实践[M」高等教育出版社.2004年1月第九章P504511 2」胡光在C中实现带主元选择的高斯消太法求解线性方程凵刂大众科技2006年第八期 [3]陈文光译MPⅠ与 Open MP并行程序设计(C语言版川M清华大学出版社2004年10月 [4]陈国良等并行算法实践[M高等教育出版社2004年1月 [5]陆鑫达等译并行栏序设计(第2版M]机械工业出版社.2005年5月 [6]张厶泉陈英译并行算法导论[M]机械工业出版社2004年2月

...展开详情
所需积分/C币:11 上传时间:2019-08-16 资源大小:233KB
举报 举报 收藏 收藏
分享 分享
三种消元法(全主元、Gauss消去法、列主元)

三种消元法(全主元、Gauss消去法、列主元)三种消元法(全主元、Gauss消去法、列主元)三种消元法(全主元、Gauss消去法、列主元)三种消元法(全主元、Gauss消去法、列主元)

立即下载
ModbusTCP/RTU网关设计

基于UIP协议栈,实现MODBUS联网,可参考本文档资料,有MODBUS协议介绍

立即下载
html+css+js制作的一个动态的新年贺卡

该代码是http://blog.csdn.net/qq_29656961/article/details/78155792博客里面的代码,代码里面有要用到的图片资源和音乐资源。

立即下载
iCopy解码软件v1.0.1.7.exe

解ic,id,hid卡密码破解ic,id,hid卡密码破解ic,id,hid破解ic,id,hid卡破解ic,id,hid卡密码密码卡密码破解ic,id,hid卡...

立即下载
分布式服务框架原理与实践(高清完整版)

第1章应用架构演进1 1.1传统垂直应用架构2 1.1.1垂直应用架构介绍2 1.1.2垂直应用架构面临的挑战4 1.2RPC架构6 1.2.1RPC框架原理6 1.2.2最简单的RPC框架实现8 1.2.3业界主流RPC框架14 1.2.4RPC框架面临的挑战17 1.3SOA服务化架构18 1.3.1面向服务设计的原则18 1.3.2服务治理19 1.4微服务架构21 1.4.1什么是微服务21 1.4.2微服务架构对比SOA22 1.5总结23 第2章分布式服务框架入门25 2.1分布式服务框架诞生背景26 2.1.1应用从集中式走向分布式.26?

立即下载
Camtasia 9安装及破解方法绝对有效

附件中注册方法亲测有效,加以整理与大家共享。 由于附件大于60m传不上去,另附Camtasia 9百度云下载地址。免费自取 链接:http://pan.baidu.com/s/1kVABnhH 密码:xees

立即下载
电磁场与电磁波第四版谢处方 PDF

电磁场与电磁波第四版谢处方 (清晰版),做天线设计的可以作为参考。

立即下载
压缩包爆破解密工具(7z、rar、zip)

压缩包内包含三个工具,分别可以用来爆破解密7z压缩包、rar压缩包和zip压缩包。

立即下载
source insight 4.0.0087 注册机序列号Patched(2017/10/17)

最新的sourceinsight4.0.0087和谐license及和谐文件。真正的4087版本,使用附件中的license文件,替换sourceinsight4.exe

立即下载
Java项目经验汇总(简历项目素材)

Java项目经验汇总(简历项目素材)

立即下载