稀疏线性方程组并行求解的若干研究
发布时间：2021-08-25 08:05
偏微分方程的数值求解问题,是通过使用数值离散方法将其转化为对稀疏线性方程组来求解的.常见的两种求解线性方程组为直接法和迭代法,当求解大型稀疏线性方程组时,迭代法中的Krylov子空间方法是最为重要、最常用的方法.直接将Krylov子空间方法在并行计算机运行,求解问题的效率往往非常低,所以探索能够适合在并行计算环境计算的Krylov子空间方法并行算法就十分有必要.在分布式内存并行计算机中,Krylov子空间方法中的内积计算引起的全局通信制约着并行算法的高效运行.所以成功的设计和实现Krylov子空间方法并行算法的关键方式就是削弱内积计算对全局通信开销的影响.由于内积计算会产生全局通信问题,本文对变预处理子逐次超松驰迭代（SOR）-双共轭残量法（BiCR）和预处理Jacobi一双共轭残量法（简称JBiCR）这两种方法进行了研究,其中变预处理子SOR一双共轭残量法（简称SOR-BiCR）是在双共轭残量法的基础上运用多种预条件技术得到的,JBiCR算法是由预处理BiCR算法中嵌入几步Jacobi迭代自适应构造而成,进一步为了使这两种算法在分布式并行计算环境中能够高效求解,分别改造变预处理子SO...
【文章来源】：福建师范大学福建省
【文章页数】：60 页
【学位级别】：硕士
【部分图文】：
图２．１?Ｓ〇Ｒ－ＢｉＣＲ和ＳＯＲ－ＩＢｉＣＲ方法加速比对比???表２．３?ＳＯＲ－ＢｉＣＲ算法和ＳＯＲ－ＩＢｉＣＲ算法加速比对比
＇￣￣＾Ｓ＾＾＾￣￣１４０??图３．１?ＢｉＣＲ和ＪＢｉＣＲ方法求解矩阵ｐｄｅ９００残差收敛和迭代步数对比??图３．１和图３．２主要比较了?ＢｉＣＲ和ＪＢｉＣＲ算法的性能．给出了残差２－范数与??数值实验迭代数的一一对应．观察图３．１和图３．２，显然在求解某些矩阵时ＪＢｉＣＲ??算法有着比ＢｉＣＲ算法更好的收敛效果和更快的收敛速度．??实验３．２通过数值实验给出了?ＣＧＳ，ＢｉＣＧＳＴＡＢ和ＪＢｉＣＲ三种算法的计算??收敛的迭代步数和算法收敛的残差值．算法终止条件是残差２－范数Ｓ?ｌｅ－８，其中??设?ｒ〇?＝?ｒ３，ｒ?＝?２．??分析和比较表３．２中的数据，在收敛精度相同的情况下，ＪＢｉＣＲ算法有着比ＣＧＳ??算法和ＢｉＣＧＳＴＡＢ算法更少的迭代步数．??图３．３和图３．４是ＣＧＳ，?ＢｉＣＧＳＴＡＢ和ＪＢｉＣＩｌ三种算法数值计算结果对比，其??３４??
?７．３６７５ｅ－０９??中４是ｐｄｅ２９６１和ｗａｔｔ丄给出了残差２－范数与数值实验迭代数的一一对应．对??比图３．３和图３．４，可以得到Ｊａｃｏｂｉ－ＢｉＣＲ算法在处理某一些类型矩阵有着比ＣＧＳ??算法和ＢｉＣＧＳＴＡＢ算法更好的收敛行为和更快的收敛速度．??实验３．３在上海大学自强４０００超级计算机，使用１２８个节点上进行数值实验，??比较ＪＢｉＣＲ算法和ＰＪＢｉＣＲ法的计算时间，性能改进比率⑷，和加速比比值（Ｃ），??数值实验中的矩阵Ａ取ｂａｒｒｉｅｄ－ｌＯ，数值实验终止条件是残差２－范数除以ｂ的??２－范数的值（｜丨ｒ？｜｜２／｜｜６｜｜２）?ｇ?ｌｅ?－?８，其中＜?＝ｒｏＪ?＝?２．表３．３是数值实验结果．??表３．３中性能改进率７；和加速比比值Ｃ分别对应着（３．３．４）和（３．３．５），两算法的??并行计算的时间为十次实验运行时间的平均值．从表中可以看出，随着处理机台数??的增加，Ｊａｃｏｂｉ－ＩＢｉＣＲ算法比Ｊａｃｏｂｉ－ＢｉＣＲ算法的性能改进比率在增加，有更快的??并行计算时间和更好的加速比
【参考文献】：
期刊论文
[1]一种自适应预处理的BiCRSTAB算法[J]. 张晋,李春光,景何仿. 纯粹数学与应用数学. 2014(02)
[2]适合于分布式并行计算的一种并行广义乘积型双共轭残差方法(英文)[J]. 左宪禹,谷同祥,莫则尧,刘兴平. 应用数学与计算数学学报. 2013(02)
[3]求解大型稀疏线性方程组的Krylov子空间方法的发展[J]. 李晓爱,陈玉花,张耘,王新苹. 科技导报. 2013(11)
[4]稀疏线性方程组的一种预处理并行算法[J]. 刘秀敏,吕全义,杜艳君. 纺织高校基础科学学报. 2012(02)
[5]变预处理子SOR-双共轭残量法[J]. 汪祥,聂永明,李乐波. 南昌大学学报(工科版). 2011(03)
[6]几种Krylov迭代法在潮流计算中的对比[J]. 郑锦辉,陆达. 计算机与现代化. 2011(04)
[7]稀疏线性方程组求解中的预处理技术综述[J]. 骆志刚,仲妍,吴枫. 计算机工程与科学. 2010(12)
[8]浅谈SMP机群上的并行计算[J]. 许崇芳. 硅谷. 2010(02)
[9]Krylov子空间方法及其并行计算[J]. 李晓梅,吴建平. 计算机科学. 2005(01)
博士论文
[1]大型稀疏线性代数方程组的并行非定常迭代方法[D]. 谷同祥.中国工程物理研究院 2001
硕士论文
[1]高性能计算在图像匹配中的应用研究[D]. 李金龙.西安建筑科技大学 2012
[2]大规模稀疏线性方程组的预条件迭代法的研究[D]. 李乐波.南昌大学 2011
本文编号：3361734
【文章来源】：福建师范大学福建省
【文章页数】：60 页
【学位级别】：硕士
【部分图文】：
图２．１?Ｓ〇Ｒ－ＢｉＣＲ和ＳＯＲ－ＩＢｉＣＲ方法加速比对比???表２．３?ＳＯＲ－ＢｉＣＲ算法和ＳＯＲ－ＩＢｉＣＲ算法加速比对比
＇￣￣＾Ｓ＾＾＾￣￣１４０??图３．１?ＢｉＣＲ和ＪＢｉＣＲ方法求解矩阵ｐｄｅ９００残差收敛和迭代步数对比??图３．１和图３．２主要比较了?ＢｉＣＲ和ＪＢｉＣＲ算法的性能．给出了残差２－范数与??数值实验迭代数的一一对应．观察图３．１和图３．２，显然在求解某些矩阵时ＪＢｉＣＲ??算法有着比ＢｉＣＲ算法更好的收敛效果和更快的收敛速度．??实验３．２通过数值实验给出了?ＣＧＳ，ＢｉＣＧＳＴＡＢ和ＪＢｉＣＲ三种算法的计算??收敛的迭代步数和算法收敛的残差值．算法终止条件是残差２－范数Ｓ?ｌｅ－８，其中??设?ｒ〇?＝?ｒ３，ｒ?＝?２．??分析和比较表３．２中的数据，在收敛精度相同的情况下，ＪＢｉＣＲ算法有着比ＣＧＳ??算法和ＢｉＣＧＳＴＡＢ算法更少的迭代步数．??图３．３和图３．４是ＣＧＳ，?ＢｉＣＧＳＴＡＢ和ＪＢｉＣＩｌ三种算法数值计算结果对比，其??３４??
?７．３６７５ｅ－０９??中４是ｐｄｅ２９６１和ｗａｔｔ丄给出了残差２－范数与数值实验迭代数的一一对应．对??比图３．３和图３．４，可以得到Ｊａｃｏｂｉ－ＢｉＣＲ算法在处理某一些类型矩阵有着比ＣＧＳ??算法和ＢｉＣＧＳＴＡＢ算法更好的收敛行为和更快的收敛速度．??实验３．３在上海大学自强４０００超级计算机，使用１２８个节点上进行数值实验，??比较ＪＢｉＣＲ算法和ＰＪＢｉＣＲ法的计算时间，性能改进比率⑷，和加速比比值（Ｃ），??数值实验中的矩阵Ａ取ｂａｒｒｉｅｄ－ｌＯ，数值实验终止条件是残差２－范数除以ｂ的??２－范数的值（｜丨ｒ？｜｜２／｜｜６｜｜２）?ｇ?ｌｅ?－?８，其中＜?＝ｒｏＪ?＝?２．表３．３是数值实验结果．??表３．３中性能改进率７；和加速比比值Ｃ分别对应着（３．３．４）和（３．３．５），两算法的??并行计算的时间为十次实验运行时间的平均值．从表中可以看出，随着处理机台数??的增加，Ｊａｃｏｂｉ－ＩＢｉＣＲ算法比Ｊａｃｏｂｉ－ＢｉＣＲ算法的性能改进比率在增加，有更快的??并行计算时间和更好的加速比
【参考文献】：
期刊论文
[1]一种自适应预处理的BiCRSTAB算法[J]. 张晋,李春光,景何仿. 纯粹数学与应用数学. 2014(02)
[2]适合于分布式并行计算的一种并行广义乘积型双共轭残差方法(英文)[J]. 左宪禹,谷同祥,莫则尧,刘兴平. 应用数学与计算数学学报. 2013(02)
[3]求解大型稀疏线性方程组的Krylov子空间方法的发展[J]. 李晓爱,陈玉花,张耘,王新苹. 科技导报. 2013(11)
[4]稀疏线性方程组的一种预处理并行算法[J]. 刘秀敏,吕全义,杜艳君. 纺织高校基础科学学报. 2012(02)
[5]变预处理子SOR-双共轭残量法[J]. 汪祥,聂永明,李乐波. 南昌大学学报(工科版). 2011(03)
[6]几种Krylov迭代法在潮流计算中的对比[J]. 郑锦辉,陆达. 计算机与现代化. 2011(04)
[7]稀疏线性方程组求解中的预处理技术综述[J]. 骆志刚,仲妍,吴枫. 计算机工程与科学. 2010(12)
[8]浅谈SMP机群上的并行计算[J]. 许崇芳. 硅谷. 2010(02)
[9]Krylov子空间方法及其并行计算[J]. 李晓梅,吴建平. 计算机科学. 2005(01)
博士论文
[1]大型稀疏线性代数方程组的并行非定常迭代方法[D]. 谷同祥.中国工程物理研究院 2001
硕士论文
[1]高性能计算在图像匹配中的应用研究[D]. 李金龙.西安建筑科技大学 2012
[2]大规模稀疏线性方程组的预条件迭代法的研究[D]. 李乐波.南昌大学 2011
本文编号：3361734
本文链接：https://www.wllwen.com/kejilunwen/yysx/3361734.html
