• 论文 •    下一篇

求解稀疏连续线性系统的自适应SGCRO-DR 算法

徐达强1, 荆燕飞1, 胡少亮2,3, 徐小文2,3   

  1. 1. 数学科学学院/计算科学研究所, 电子科技大学, 成都 611731;
    2. 北京应用物理与计算数学研究所, 计算物理重点实验室, 北京 100094;
    3. 中物院高性能数值模拟软件中心, 北京 100088
  • 收稿日期:2021-10-12 发布日期:2022-06-10
  • 通讯作者: 荆燕飞,Email:yanfeijing@uestc.edu.cn or 00jyfvictory@163.com.
  • 基金资助:
    科学挑战专题(TZ2016002),国家自然科学基金项目(12071062,61772003),电子科技大学理科实力提升计划资助

徐达强, 荆燕飞, 胡少亮, 徐小文. 求解稀疏连续线性系统的自适应SGCRO-DR 算法[J]. 数值计算与计算机应用, 2022, 43(2): 125-141.

Xu Daqiang, Jing Yanfei, Hu Shaoliang, Xu Xiaowen. ADAPTIVE SGCRO-DR ALGORITHM FOR SOLVING SPARSE SEQUENCES OF LINEAR SYSTEMS[J]. Journal on Numerica Methods and Computer Applications, 2022, 43(2): 125-141.

ADAPTIVE SGCRO-DR ALGORITHM FOR SOLVING SPARSE SEQUENCES OF LINEAR SYSTEMS

Xu Daqiang1, Jing Yanfei1, Hu Shaoliang2,3, Xu Xiaowen2,3   

  1. School of Mathematical Sciences/Institute of Computational Science, University of Electronic Science and Technology of China, Chengdu 611731, China;
    2. Institute of Applied Physics and Computational Mathematics, Beijing 100094, China;
    3. CAEP Software Center for High Performance Numerical Simulation, Beijing, 100088, China
  • Received:2021-10-12 Published:2022-06-10
GCRO-DR方法是求解一系列连续线性系统常用迭代方法.本文首先提出了~simpler GCRO-DR方法,在单个循环中它的计算成本比GCRO-DR更少.本文为了避免算法的不稳定性问题和内存溢出问题,并提高~simpler GGRO-DR算法的收敛性,引入了重启参数自适应策略.另外,在用该方法求解大型连续线性系统需要多次重启次数情形以及相邻系数矩阵之间谱信息相关情形,本文利用重启参数自适应策略提供的学习样本,通过强化学习来选取一个比较好的重启参数.最后,数值实验证明了所提三类算法的有效性.
The GCRO-DR method is considered as a frequently-used iterative solver for solving a series of linear systems given in sequence. In this paper, a simpler variant of GCRO-DR is firstly proposed, which takes less computational cost within one cycle than GCRO-DR. Furthermore, an adaptive strategy for setting restart parameters is introduced in order to overcome the non-stability problem and out-of-memory problem of the proposed simpler GGRO-DR method, as well as to improve its convergence. Moreover, in both circumstances that many restart numbers are required by such method for solving large linear systems given in sequence, and neighbouring coefficient matrices share relevant spectral information, a better restart parameter is determined by reinforcement learning based on the learning samples provided by the adaptive strategy for setting restart parameters. Finally, numerical experiments demonstrate the efficiency of the proposed three types of algorithms.

MR(2010)主题分类: 

()
[1] Parks M L, de Sturler E, Mackey G, Johnson D, Maiti S. Recycling Krylov subspaces for sequences of linear systems[J]. SIAM J. Sci. Comput., 2006, 28:1651-1674.
[2] 徐小文,莫则尧,安恒斌.[求解大规模稀疏线性代数方程组序列的自适应AMG预条件策略[J]].中国科学:信息科学, 2016, 46:1411-1420.
[3] Xu X W, Mo Z Y, Yue X Q, An H B, Shu S,[$\alpha$Setup-AMG:an adaptive-setup-based parallel AMG solver for sequence of sparse linear systems[J]]. CCF Trans. HPC., 2020, 2:98-110.
[4] 胡少亮,徐小文,郑宇腾,赵振国,王卫杰,徐然,安恒斌,莫则尧.[系统级封装应用中时谐Maxwell方程大规模计算的求解算法:现状与挑战[J]].计算物理, 2021, 38(02):131-145.
[5] 赵冉,胡俊,魏翔,江明.[用积分方程区域分解方法和GCRO-DR方法求解电大目标电磁散射[C]]. 2013年全国微波毫米波会议论文集, 2013, 116-119.
[6] Peng Z, Stephanson M B, Lee J F. Fast computation of angular responses of large-scale threedimensional electromagnetic wave scattering[J]. IEEE Trans. on Antenn. Propag, 2010, 58(9):3004-3012.
[7] Morgan R B, GMRES with deflated restarting[J]. SIAM J. Sci. Comput., 2002, 24:20-37.
[8] Morgan R B, A restarted GMRES method augmented with eigenvectors[J]. SIAM J. Matrix Anal. Appl., 1995, 16:1154-1171.
[9] Morgan R B, Implicitly restarted GMRES and arnoldi methods for nonsymmetric systems of equations[J]. SIAM J. Matrix Anal. Appl., 2000, 21:1112-1135.
[10] de Sturler E, Nested Krylov methods based on GCR[J]. J. Comput. Appl. Math., 1996, 67:15-41.
[11] Carvalho L M, Gratton S, Lago R, Vasseur X, A flexible generalized conjugate residual method with inner orthogonalization and deflated restarting[J]. SIAM J. Matrix Anal. Appl., 2011, 32:1212-1235.
[12] Niu Q, Lu L Z, Liu G. Accelerated GCRO-DR method for solving sequences of systems of linear equations[J]. J. Comput. Appl. Math., 2013, 253:131-141.
[13] Parks M L, Soodhalter K M, Block GCRO-DR. in Belos package of the Trilinos C++Library, 2011.
[14] Parks M L, Soodhalter K M, Szyld D B. A block recycled GMRES method with investigations into aspects of solver performance. http://arxiv.org/abs/1604.01713, 2016.
[15] Meng J, Li H B, Jing Y F. A new deflated block GCROT (m, k) method for the solution of linear systems with multiple right-hand sides[J]. J. Comput. Appl. Math., 2014, 300:155-171.
[16] Giraud L, Jing Y F, Xiang Y F. A block minimum residual norm subspace solver with partial convergence management for sequences of linear systems[J]. SIAM J. Matrix Anal. Appl., 2022, 43:710-739.
[17] Saad Y. Iterative Methods for Sparse Linear Systerms[M]. 2nd ed., SIAM, Philadelphia, 2003.
[18] Saad Y, Schultz M H. GMRES:A generalized minimal residual algorithm for solving nonsymmetric linear systems[J]. SIAM J. Sci. Stat. Comput., 1986, 7:856-869.
[19] Walker H F, Zhou L. A simpler GMRES[J]. Numer Linear Algebra Appl., 1994, 1:571-581.
[20] Baker A H, On improving the performance of the linear solver restarted GMRES[D]. Ph.D. thesis, University of Colorado at Boulder, Boulder, CO, USA, 2003.
[21] Jiránek P, Rozloznik M, Gutknecht M H. How to make simpler GMRES and GCR more stable[J]. SIAM J. Matrix Anal. Appl., 2008, 30:1483-1499.
[22] Jing Y F, Yuan P, Huang T Z. A simpler GMRES and its adaptive variant for shifted linear systems[J]. Numer. Linear Algebra Appl., 2017, 24:e2076.
[23] Yang Z, Jing Y F, Niu Q. Restarted simpler GMRES augmented with harmonic Ritz vectors and approximate errors[J]. J. Comput. Appl. Math., 2019, 368:112565.
[24] Lin Y, Liang B, Wu Q. Simpler GMRES with deflated restarting[J]. Math.&Comput. Simu., 2012, 82:2238-2252.
[25] Embree M. The tortoise and the hare restart GMRES[J]. SIAM Review., 2003, 45:259-266.
[26] Baker A H, Jessup E R, Kolev T V. A simple strategy for varying the restart parameter in GMRES (m)[J]. J. Comput. Appl. Math., 2009, 230:751-761.
[27] Peairs L, Chen T Y. Using reinforcement learning to vary the m in GMRES (m)[J]. Procedia Computer Science., 2011, 4:2257-2266.
[28] Baker A H, Jessup E R, Manteuffel T. A technique for accelerating the convergence of restarted GMRES[J]. SIAM J. Matrix Anal. Appl., 2005, 26:962-984.
[29] Davis T A and Hu Y F. The University of Florida sparse matrix collection[J]. ACM Trans. Math. Software., 2011, 38:1-25.
[1] 张晨松. 油藏数值模拟中的线性解法器[J]. 数值计算与计算机应用, 2022, 43(1): 1-26.
[2] 谢亚君, 马昌凤. 求解Einstein-积张量方程的混合贪婪随机坐标下降法[J]. 数值计算与计算机应用, 2021, 42(4): 323-336.
[3] 秦子康, 安恒斌, 王新玉. 两类向量序列加速收敛方法比较[J]. 数值计算与计算机应用, 2021, 42(4): 379-394.
[4] 王丽. 三类新的求解广义最小二乘问题的预处理GAOR方法[J]. 数值计算与计算机应用, 2020, 41(4): 282-296.
[5] 陈世军, 卢民荣. 单变量矩阵方程子矩阵约束下牛顿-MCG算法[J]. 数值计算与计算机应用, 2020, 41(4): 306-314.
[6] 徐小文. 并行代数多重网格算法:大规模计算应用现状与挑战[J]. 数值计算与计算机应用, 2019, 40(4): 243-260.
[7] 刘芳芳, 陈道琨, 杨超, 赵玉文. 面向磁流体动力学方程组的异构众核全隐求解器研究[J]. 数值计算与计算机应用, 2019, 40(1): 34-50.
[8] 陈星玎, 李思雨. 求解PageRank的多步幂法修正的广义二级分裂迭代法[J]. 数值计算与计算机应用, 2018, 39(4): 243-252.
[9] 卢晴, 舒适, 彭洁. 一种变系数扩散问题有限体积格式的高效预条件子[J]. 数值计算与计算机应用, 2018, 39(2): 150-160.
[10] 吴长茂, 杨超, 尹亮, 刘芳芳, 孙乔, 李力刚. 基于CPU-MIC异构众核环境的行星流体动力学数值模拟[J]. 数值计算与计算机应用, 2017, 38(3): 197-214.
[11] 廖平. Hermitian鞍点矩阵的特征值估计[J]. 数值计算与计算机应用, 2017, 38(2): 123-129.
[12] 李琴. Stokes方程的一种预处理方法[J]. 数值计算与计算机应用, 2017, 38(2): 81-90.
[13] 梁志艳, 张凯院, 耿小姣. Riccati方程子矩阵约束对称解的非精确Newton-MCG算法[J]. 数值计算与计算机应用, 2015, 36(4): 288-296.
[14] 张凯院, 宁倩芝. 实矩阵两类广义逆的迭代算法[J]. 数值计算与计算机应用, 2015, 36(2): 81-90.
[15] 李玲, 徐仲, 陆全. 非奇H-矩阵的一组迭代判别法[J]. 数值计算与计算机应用, 2015, 36(2): 91-99.
阅读次数
全文


摘要