带状线性方程组的含参交替方向并行算法

计算机科学 ›› 2014, Vol. 41 ›› Issue (2): 249-252.

带状线性方程组的含参交替方向并行算法

马欣荣,刘三阳,段治健

西安电子科技大学理学院应用数学系西安710071;西安电子科技大学理学院应用数学系西安710071;咸阳师范学院数学与信息科学学院咸阳712000

出版日期:2018-11-14 发布日期:2018-11-14
基金资助:
本文受国家自然基金项目(11002117),咸阳师范学院科研基金项目(09XSYK204,09XSYK209)资助

Parallel Alternating Direction Algorithm with Parameters for Solving Banded Linear Systems

MA Xin-rong,LIU San-yang and DUAN Zhi-jian

Online:2018-11-14 Published:2018-11-14

摘要/Abstract

摘要： 在MIMD分布式存储环境下针对系数矩阵为带状或块三对角矩阵的线性方程组提出了含三参数交替方向迭代并行算法。通过引入三参数调整,并适当分裂系数矩阵得到新算法,给出了系数矩阵为若干特殊矩阵时算法的收敛条件。在HP rx2600集群系统上实现了算法,针对不同的算例将其与多分裂方法、BSOR方法和PEk内迭代方法进行了比较。并行计算结果表明,所提算法具有较高的加速比和并行效率,明显优于多分裂方法和PEk方法,能合理分配内存,从而有效节省计算时间。针对算例1,加速比和计算效率略优于BSOR方法；而算例2的结果明显优于PEk内迭代方法。

关键词: 线性方程组,HP rx2600集群,并行效率,加速比中图法分类号TP301文献标识码A

Abstract: This paper focused on parallel iterative method with parameters for solving banded or block tridiagonal linear systems on distributed-memory cluster．By splitting the coefficient matrix and using parameters,we proposed a new algorithm and gave some convergence theories for some special coefficient matrices．Furthermore,we implemented the algorithm on HP rx2600cluster and compared it with multisplitting method,BSOR method and PEk inner iterative me-thod for different examples．The numerical experiments indicate that acceleration rates and efficiency of our algorithm are higher than the multi-splitting one．The algorithm saves computational time by allocating memory properly．As to Example 1,the acceleration rates and efficiency of our algorithm are better than the BSOR one slightly．And the results for Example 2are better than PEk inner iterative one significantly.

Key words: Linear systems,HP rx2600cluster,Parallel efficiency,Acceleration rates

马欣荣,刘三阳,段治健. 带状线性方程组的含参交替方向并行算法[J]. 计算机科学, 2014, 41(2): 249-252. https://doi.org/

MA Xin-rong,LIU San-yang and DUAN Zhi-jian. Parallel Alternating Direction Algorithm with Parameters for Solving Banded Linear Systems[J]. Computer Science, 2014, 41(2): 249-252. https://doi.org/

参考文献

[1] 吕全义,叶天麒．系数矩阵为块三对角的线性方程组的并行算法[J]．西北工业大学学报,1996,14(2):314-317
[2] 段治健,等．求解带状线性方程组的一种并行算法[J]．计算机科学,2010,37(3):242-244
[3] 张波,谷同祥,莫则尧．数值并行计算原理与方法[M]．北京:国防工业出版社,1999
[4] 吴建平等．块三对角线性方程组的一类二维区域分解并行不完全分解预条件[J]．计算物理,2009,26(2):191-199
[5] 樊艳红．具有典型结构的大规模线性方程组的并行算法[D]．西安:西北工业大学,2009
[6] 谷同祥,刘兴平.并行二级多分裂迭代方法[J]．计算数学,1998,20:153-166
[7] EI-Sayed S M．A direct method for solving circulant tridiagonal block systems of linear equations[J]．Applied Mathematics and Computation,2005(165):23-30
[8] Cui Xi-ning,Lü Quan-yi．A parallel algorithm for block-tridiagonal linear systems[J]．Applied Mathematics and Computation,2006,3:1107-1114
[9] 骆志刚,李晓梅．块三对角线性方程组的一种分布式并行算法[J]．计算机学报,2000,23(10):1028-1034
[10] 盛跃宾,宋晓秋,刘德贵．带状线性方程组的一种有效分布式并行算法[J]．系统工程与电子技术,2004,26(7):967-969
[11] Varga R S．Matrix Iterative Analysis[M]．Prentice-Hall,Englewood Cliffs,N.J．1962
[12] Lv Quan-yi,Xiao Man-yu,Zhou Min.A parallel algorithm based on Galerkin theory for block-tridiagonal linear systems[J]．Applied Mathematics and Communication,2007,187(2):1277-1285
[13] Garey L E,Shaw R E．A parallel algorithm for solving Toeplitz linear systems[J]．Applied Mathematics and Communication,1999,0(2):241-247
[14] Frommer A,Szyld D B．Weighted max norms,splitting,and overlapping additive Schwarz iterations[J]．Numerische Ma-thematik,1999,83:259-278
[15] 程云鹏．矩阵论[M]．西安:西北工业大学出版社,2002

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed