krylov子空间方法解线性方程组的并行性能分析及应用

《krylov子空间方法解线性方程组的并行性能分析及应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Krylov子空间方法解线性方程组的并行性能分析及应用Krylov子空间方法解线性方程组的并行性能分析及应用Krylov子空间方法解线性方程组的并行性能分析及应用Krylov子空间方法解线性方程组的并行性能分析及应用Krylov子空间方法解线性方程组的并行性能分析及应用Krylov子空间方法解线性方程组的并行性能分析及应用Krylov子空间方法解线性方程组的并行性能分析及应用刘青昆堑些盘张德富02I6南京大学计算机软件新技术面.重点实验室,南京大学计算机系(京210093)摘要许多并行计算问题,在结合并行机的特有体系结构时,要对算法的并行性能度其可扩展性进行分析.它决定了

2、该算法解决有关问题是否有效,并进一步判断所用的井行计算乐统是否符告求解问题的要求.文章通过对Kfflov子空间中两种有效算法一PCG算法和GMRES(m)算法在一类并行系统中形成的并行算法的性能进行了分析,给出了算求解问题规模与处理机数与加速比的关系结果表明.GMRES(m)算法比PCG算法曼适合于并行关攮词Krylov子空间线性方程组并行性能ParalieIEfficiencyAnalysisofKryiovSubspaceMethodsforLargeSparseLinearAlgebraicSystemsandApplicationLiuQingkunShuJiwu

3、ZhangDefu(StateKeyLaboratoryforNovelSoftwareTechnologyatNanjingUniversity,DepartmentofComputerScienceandTechnology,NanjingUniversity,Nanjing210093)Abstract:Inthispaper.wefindtherelationsamongthescaleofthealgebraicsystems.multipr0ce∞0TandspeedbyanalyzingparallelefficiencyofPCGalgorithmandG

4、MRES(malgorithminKrylovsubspacemethods.There—sultproclaimsthatGMRESalgorithmisapttoparallelcomparingtoPCGalgorithm.Thispapervestheappli-cationofPCGalgorithmandGMRES)algorithmtonumericalsimulationofreservoirKeywords:Krylovsubspacemethods,linearalgebraicsystems,parallelefficiency1引言Krylov于空

5、间方法是解大型稀疏线性方程组一种较好的算法.大型问题的并行计算,有两个问题是经常受到关注的,一个是对给定的并行计算环境,能够推测出求解问题的规模与所获得的加速比变化的关系.另一个是对给定规模的问题求解,通信对加速比的影响情况.对于这两个问题,它们将决定该算法解决有关问题是否有效,进一步判断所用的并行计算系统是否符合求解问题的要求.因此在结合并行机的特有体系结构时,要对算法的并行性能及其可扩展性进行分析.文章对Krylov子空间中两种有救算法一PCG算法和GMRES(m)算法在一类并行系统中形成的并行算法的性能进行了分析.结果表明,GMRES(m)算法比PCG算法更适合于并

6、行.2Krylov子空间方法及并行计算结构假定N阶线性方程组:Ax=bA为大型稀疏非奇异NxN的矩阵:设初值x口,定义r~=b-Axo.Krylov子空间方法是迭代法,造代m步产生子空间K(A,)=Span(to,A,…,AT0)和近似解xm∈xo+K,并且满足Petrov-Galerkin条件:rm上这里如将k表示m维子空间的一组基作列的矩阵.不同的可以导出不同的算法,如共轭梯度法(cG),PCG,CR,广义共轭剩余法(GCR),0RTHOMIN,广义极小剩余法(GM—aES)等等.近年来实际情况表明,PCG和GMRES(m)方法是Krylov子空间方法中两种较有效的算

7、法,PCG法用于对称正定线性方程组的求解,GMERS(m)法主要用于求解非对称线性方程组,这两个算法主要涉及向量计算及矩阵与向量相乘,适合于在并行处理机中并行计算,因此可以形成对应的并行算法,研究它们的并行性能则对于整个Krylov子空间方法也具有较普遍的代表性.这里并行系统结构是由P个处理机P,,…,组成一个,/Px,/的二维网格连接的,如图1.问题的计算物理区域fl大小为N:,/Nx,/N的区域块.将物理区域fl也分解成,/x,/-_个子区域f1,,-,,区域块对应地分配到处理机上(i:1,2,…,p),每个物理子区域nj