求解多尺度稀疏矩阵的代数界面优先AMG光滑子

doi:10.12288/szjs.s2022-0822

光滑子是影响代数多重网格算法（AMG）求解效率的重要组件之一.本文考虑实际应用中普遍出现的一类多尺度稀疏矩阵，由于多尺度性质的影响，现有AMG光滑子的光滑效果不理想，从而影响AMG算法求解该类方程的效率.借助代数界面的概念，本文分析了代数界面对松弛型光滑子的影响，并通过扩展代数界面的内涵，设计了一种代数界面优先的光滑子（AI-Smoother）.以Gauss-Seidel （GS）光滑子为例，通过三维模型问题和实际问题测试了该光滑子（AI-GS）的有效性.测试表明，与自然序GS光滑子相比，AI-GS有效改善了AMG算法的收敛速度.对于三维随机系数扩散方程百万自由度算例，AI-GS可获得28.2%的加速，对于激光聚变应用中的三温方程百万自由度算例，AI-GS可获得28.8%的加速.

关键词： 代数多重网格算法(AMG), 光滑子, 多尺度稀疏矩阵, 代数界面

The smoother is one of the important components that affects the solution efficiency of the Algebraic Multigrid Algorithm (AMG). This paper considers a class of multi-scale sparse matrices that commonly appear in practical applications. Due to the influence of multi-scale properties, the smoothing effect of the existing AMG smoothers is not work well, which affects the efficiency of the AMG algorithm for solving multi-scale sparse matrices. Using the concept of algebraic interface, this paper analyzes the influence of algebraic interface on relaxation smoothers, and by extending the concept of algebraic interface, an algebraic interface-prior smoother (AI-Smoother) is designed. Taking Gauss-Seidel (GS) smoother as an example, the effectiveness of the AI-porior smoother (AI-GS) is tested through 3D model problems and practical problems. Numerical results show that, compared with the original GS smoother,AI-GS effectively improves the convergence speed of the AMG algorithm. AI-GS can achieve a 28.2% speedup for the three-dimensional random coefficient diffusion equation with one million degrees of freedom. For the three-temperature equation in laser fusion applications, AI-GS can achieve a 28.8% speedup.

Key words: Algebraic multigrid(AMG), Smoother, Multi-scale sparse matrice, Algebraic Interface

MR(2010)主题分类:

分享此文:

[1] Ruge J W, Stüben K. Algebraic multigrid[C]. In Multigrid methods, SIAM, 1987, 73-130.
[2] 徐小文. 可扩展并行代数多重网格算法研究[D]. PhD thesis, 博士论文, 北京:中国工程物理研究院研究生部, 2007.
[3] 徐小文, 莫则尧, 刘旭. 基于局部松驰和粗化策略的代数多重网格方法[J]. 数值计算与计算机应用,2009, (2):81-91.
[4] Sterck H D, Yang U M, Heys J J. Reducing complexity in parallel algebraic multigrid preconditioners[J]. SIAM Journal on Matrix Analysis and Applications, 2006, 27(4):1019-1039.
[5] Oliveira S, Deng Y. Preconditioned Krylov subspace methods for transport equations[J]. Progress in Nuclear Energy, 1998, 33(1-2):155-174.
[6] Erlangga Y A, Nabben R. Algebraic multilevel Krylov methods[J]. SIAM Journal on Scientific Computing, 2009, 31(5):3417-3437.
[7] Elman H, Howle V E, Shadid J, Shuttleworth R, Tuminaro R. A taxonomy and comparison of parallel block multi-level preconditioners for the incompressible Navier-Stokes equations[J]. Journal of Computational Physics, 2008, 227(3):1790-1808.
[8] Brandt A. General highly accurate algebraic coarsening[J]. Electronic Transactions on Numerical Analysis, 2000, 10(1):21.
[9] der Vorst H A V. Bi-CGSTAB:A fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems[J]. SIAM Journal on scientific and Statistical Computing, 1992, 13(2):631-644.
[10] Saad Y. Iterative methods for sparse linear systems[M]. SIAM, 2003.
[11] Saad Y, Schultz M H. GMRES:A generalized minimal residual algorithm for solving nonsymmetric linear systems[J]. SIAM Journal on scientific and statistical computing, 1986, 7(3):856-869.
[12] Kettler R. Analysis and comparison of relaxation schemes in robust multigrid and preconditioned conjugate gradient methods[G]. In Multigrid methods, Springer, 1982, 502-534.
[13] Brannick J J, Falgout R D. Compatible relaxation and coarsening in algebraic multigrid[J]. SIAM Journal on Scientific Computing, 2010, 32(3):1393-1416.
[14] Mo Z, Xu X. Relaxed RS0 or CLJP coarsening strategy for parallel AMG[J]. Parallel Computing, 2007, 33(3):174-185.
[15] Sterck H D, Yang U M. Coarsening and interpolation in algebraic multigrid:a balancing act[C]. In Presentation at the 9th Copper Mountain Conference on Multigrid Methods, 2004.
[16] Livne O E. Coarsening by compatible relaxation[J]. Numerical linear algebra with applications, 2004, 11(2-3):205-227.
[17] Ron D, Safro I, Brandt A. Relaxation-based coarsening and multiscale graph organization[J]. Multiscale Modeling & Simulation, 2011, 9(1):407-423.
[18] Grauschopf T, Griebel M, Regler H. Additive multilevel preconditioners based on bilinear interpolation, matrix-dependent geometric coarsening and algebraic multigrid coarsening for second-order elliptic PDEs[J]. Applied Numerical Mathematics, 1997, 23(1):63-95.
[19] Brannick J, Brezina M, MacLachlan S, Manteuffel T, McCormick S, Ruge J. An energy-based AMG coarsening strategy[J]. Numerical linear algebra with applications, 2006, 13(2-3):133-148.
[20] Wittum G. On the robustness of ILU smoothing[J]. SIAM journal on scientific and statistical computing, 1989, 10(4):699-717.
[21] Thomas S, Carr A, Świrydowicz K, Day M. ILUT Smoothers for Hybrid C-AMG with Scaled Triangular Factors[J]. arXiv preprint arXiv:2111.09512, 2021.
[22] Tang W P, Wan W L. Sparse approximate inverse smoother for multigrid[J]. SIAM Journal on Matrix Analysis and Applications, 2000, 21(4):1236-1252.
[23] Luo P, Rodrigo C, Gaspar F J, Oosterlee C. On an Uzawa smoother in multigrid for poroelasticity equations[J]. Numerical Linear Algebra with Applications, 2017, 24(1):e2074.
[24] Oosterlee C W. A GMRES-based plane smoother in multigrid to solve 3D anisotropic fluid flow problems[J]. Journal of Computational Physics, 1997, 130(1):41-53.
[25] Swanson R, Turkel E, Yaniv S. Analysis of a RK/implicit smoother for multigrid[G]. In Computational Fluid Dynamics 2010, pages 409-417. Springer, 2011.
[26] Evans D J, Yousif W. The Explicit Block Relaxation method as a grid smoother in the Multigrid V-cycle scheme[J]. International journal of computer mathematics, 1990, 34(1-2):71-78.
[27] Kashi A, Vangara S, Nadarajah S, Castonguay P. Asynchronous fine-grain parallel implicit smoother in multigrid solvers for compressible flow[J]. Computers & Fluids, 2020, 198:104255.
[28] Zeeuw P D. Incomplete line LU as smoother and as preconditioner[G]. In Incomplete Decomposition (ILU)-Algorithms, Theory, and Applications, Springer, 1993, 215-224.
[29] Ghysels P, K losiewicz P, Vanroose W. Improving the arithmetic intensity of multigrid with the help of polynomial smoothers[J]. Numerical Linear Algebra with Applications, 2012, 19(2):253-267.
[30] Kawai M, Iwashita T, Nakashima H, Marques O. Parallel smoother based on block red-black ordering for multigrid poisson solver[C]. In International Conference on High Performance Computing for Computational Science, pages 292-299. Springer, 2012.
[31] Yang U M. Parallel algebraic multigrid methods-high performance preconditioners[G]. In Numerical solution of partial differential equations on parallel computers, pages 209-236. Springer, 2006.
[32] Falgout R D, Vassilevski P S, Zikatanov L T. On two-grid convergence estimates[J]. Numerical linear algebra with applcations, 2005, 12(5-6):471-494.
[33] Bank R E, Douglas C C. Sharp estimates for multigrid rates of convergence with general smoothing and acceleration[J]. SIAM journal on numerical analysis, 1985, 22(4):617-633.
[34] Baker A H, Falgout R D, Kolev T V, Yang U M. Multigrid smoothers for ultraparallel computing[J]. SIAM Journal on Scientific Computing, 2011, 33(5):2864-2887.
[35] Yang U M. On the use of relaxation parameters in hybrid smoothers[J]. Numerical Linear Algebra with Applications, 2004, 11(2-3):155-172.
[36] Adams M, Brezina M, Hu J, Tuminaro R. Parallel multigrid smoothing:polynomial versus Gauss-Seidel[J]. Journal of Computational Physics, 2003, 188(2):593-610.
[37] Bröker O, Grote M J, Mayer C, Reusken A. Robust parallel smoothing for multigrid via sparse approximate inverses[J]. SIAM Journal on Scientific Computing, 2001, 23(4):1396-1417.
[38] Falgout R, Cleary A, Jones J, Chow E, Henson V, Baldwin C, Brown P, Vassilevski P, Yang U. Hypre User's Manual, Version 2.7[J]. Center for Applied Scientific Computing (CASC), Lawrence Livermore National Laboratory, Livermore, CA, 2010.
[39] Xu X, Yue X, Mao R, Deng Y, Huang S, et al, JXPAMG:A Parallel Algebraic Multigrid Solver for Extreme-scale Numerical Simulations[C]. CCF Trans. HPC, 2022. https://doi.org/10.1007/s42514-022-00125-9
[40] Aage N, Andreassen E, Lazarov B S. Topology optimization using PETSc:An easy-to-use, fully parallel, open source topology optimization framework[J]. Structural and Multidisciplinary Optimization, 2015, 51(3):565-572.
[41] Xu X, Mo Z. Algebraic interface-based coarsening AMG preconditioner for multi-scale sparse matrices with applications to radiation hydrodynamics computation[J]. Numerical Linear Algebra with Applications, 2017, 24(2):e2078.
[42] https://www.solver-conference.cn/solverchallenge21/
[43] 裴文兵, 朱少平. 激光聚变中的科学计算[J]. 物理, 2009, 38(08):559-568.
[44] 徐小文. 并行代数多重网格算法:大规模计算应用现状与挑战[J]. 数值计算与计算机应用,2019, 40(4):243-260.

[1]	李旭, 李瑞丰. 求解一类复对称线性系统的广义AOR迭代法[J]. 数值计算与计算机应用, 2022, 43(3): 295-306.
[2]	徐达强, 荆燕飞, 胡少亮, 徐小文. 求解稀疏连续线性系统的自适应SGCRO-DR 算法[J]. 数值计算与计算机应用, 2022, 43(2): 125-141.
[3]	张晨松. 油藏数值模拟中的线性解法器[J]. 数值计算与计算机应用, 2022, 43(1): 1-26.
[4]	谢亚君, 马昌凤. 求解Einstein-积张量方程的混合贪婪随机坐标下降法[J]. 数值计算与计算机应用, 2021, 42(4): 323-336.
[5]	秦子康, 安恒斌, 王新玉. 两类向量序列加速收敛方法比较[J]. 数值计算与计算机应用, 2021, 42(4): 379-394.
[6]	王丽. 三类新的求解广义最小二乘问题的预处理GAOR方法[J]. 数值计算与计算机应用, 2020, 41(4): 282-296.
[7]	陈世军, 卢民荣. 单变量矩阵方程子矩阵约束下牛顿-MCG算法[J]. 数值计算与计算机应用, 2020, 41(4): 306-314.
[8]	徐小文. 并行代数多重网格算法:大规模计算应用现状与挑战[J]. 数值计算与计算机应用, 2019, 40(4): 243-260.
[9]	刘芳芳, 陈道琨, 杨超, 赵玉文. 面向磁流体动力学方程组的异构众核全隐求解器研究[J]. 数值计算与计算机应用, 2019, 40(1): 34-50.
[10]	陈星玎, 李思雨. 求解PageRank的多步幂法修正的广义二级分裂迭代法[J]. 数值计算与计算机应用, 2018, 39(4): 243-252.
[11]	卢晴, 舒适, 彭洁. 一种变系数扩散问题有限体积格式的高效预条件子[J]. 数值计算与计算机应用, 2018, 39(2): 150-160.
[12]	吴长茂, 杨超, 尹亮, 刘芳芳, 孙乔, 李力刚. 基于CPU-MIC异构众核环境的行星流体动力学数值模拟[J]. 数值计算与计算机应用, 2017, 38(3): 197-214.
[13]	廖平. Hermitian鞍点矩阵的特征值估计[J]. 数值计算与计算机应用, 2017, 38(2): 123-129.
[14]	李琴. Stokes方程的一种预处理方法[J]. 数值计算与计算机应用, 2017, 38(2): 81-90.
[15]	梁志艳, 张凯院, 耿小姣. Riccati方程子矩阵约束对称解的非精确Newton-MCG算法[J]. 数值计算与计算机应用, 2015, 36(4): 288-296.

阅读次数

全文

摘要

求解多尺度稀疏矩阵的代数界面优先AMG光滑子

AN AMG SMOOTHER BASED ON ALGEBRAIC INTERFACE-PRIOR FOR SOLVING MULTL-SCALE SPARSE MATRICES

扫码分享