SCIENTIA SINICA Informationis, Volume 46 , Issue 10 : 1411-1420(2016) https://doi.org/10.1360/N112016-00074

An adaptive AMG preconditioning strategy for solving large-scale sparse linear systems

More info
  • ReceivedMar 20, 2016
  • AcceptedJul 7, 2016
  • PublishedOct 25, 2016


A series of sparse linear systems must be solved in applications that are based on the implicit solution of time-dependent partial differential equations (PDEs). Preconditioned iterative methods are usually employed to solve such sparse linear systems. AMG is one of the most popular preconditioners in real applications. However, it results in poor parallel scalability, owing to its setup phase. In this paper, by utilizing the differences and similarities in property among the systems in series, an adaptive AMG preconditioning strategy is presented to improve the parallel scalability. The results obtained for a radiation hydrodynamics computation within an ICF simulation demonstrate the efficiency and improvement of the adaptive strategy. For a typical model, the new strategy improves the parallel efficiency from 47\% to 61\%, and reduces the CPU time from 19.7 h to 14.5 h.

Funded by







[1] Brandt A, McCormick S, Ruge J. Algebraic multigrid for sparse matrix equations. In: Sparsity and its Application. Cambridge: Cambridge University Press, 1984. 257-284. Google Scholar

[2] Ruge J W, Stueben K. Algebraic multigrid. In: Multigrid Methods. Philadelphia: SIAM, 1987. 73-130. Google Scholar

[3] Stueben K. Algebraic Multigrid (AMG): An Introduction With Applications. Sankt Augustin: GMD-Forschungszentrum Informationstechnik, 1999. Google Scholar

[4] Yang U M. Parallel algebraic multigrid methods-high performance preconditioners. In: Numerical Solution of Partial Differential Equations on Parallel Computers. Berlin: Springer-Verlag, 2006. 209-236. Google Scholar

[5] Xu X W, Mo Z Y. Scalability analysis for parallel algebraic multigrid algorithms. Chinese J Comput Phys, 2007, 24: 387-394 [徐小文, 莫则尧. 并行代数多重网格算法可扩展性能分析. 计算物理, 2007, 24: 387-394]. Google Scholar

[6] Mo Z Y, Xu X W. Relaxed RS0 or CLJP coarsening strategy for parallel AMG methods. Parall Comput, 2007, 33: 174-185 CrossRef Google Scholar

[7] Baker A H, Gamblin T, Schulz M, et al. Challenges of scaling AMG across modern multicore architectures. In: Proceedings of the 25th IEEE International Symposium on Parallel and Distributed Processing (IPDPS), Anchorage, 2011. 275-286. Google Scholar

[8] Baker A H, Falgout R D, Gamblin T, et al. Scaling AMG solvers: on the road to Exascale. In: Proceedings of International Conference on Competence in High Performance Computing, Schwetzingen, 2010. 215-226. Google Scholar

[9] Baker A H, Falgout R D, Gahvari H, et al. Preparing Algebraic Multigrid for Exascale. LLNL Technical Report LLNL-TR-533076. 2012. Google Scholar

[10] Falgout R, Schroder J. Non-Galerkin coarse grids for algebraic multigrid. SIAM J Sci Comput, 2014, 36: 309-334 CrossRef Google Scholar

[11] Park J, Smelyanskiy M, Yang U M, et al. High-performance algebraic multigrid solver optimized for multi-core based distributed parallel systems. In: Proceedings of International Conference for High Performance Computing, Networking, Storage and Analysis (SC'15). New York: ACM, 2015. 54. Google Scholar

[12] Benzi M. Preconditioning techniques for large linear systems: a survey. J Comput Phys, 2002, 182: 418-477 CrossRef Google Scholar

[13] Gu T X, Xu X W, Liu X P, et al. Iterative Methods and Preconditioning Techniques. Beijing: Science Press, 2015 [谷同祥, 徐小文, 刘兴平, 等. 迭代方法和预处理技术(下册). 北京: 科学出版社, 2015]. Google Scholar

[14] Saad Y. Iterative Methods for Sparse Linear Systems. 2nd ed. Philadelphia: Society for Industry and Applied Mathematics, 2003. Google Scholar

[15] Meijerink J A, van der Vorst H A. An iterative solution method for linear systems of which the coefficient matrix is a symmetric M-matrix. Math Comput, 1977, 31: 148-162. Google Scholar

[16] Trottenberg U, Oosterlee C W, Schuller A. Multigrid. London: Academic Press, 2001. Google Scholar

[17] Toselli A, Widlund O. Domain Decomposition Methods: Algorithms and Theory. Philadelphia: Society for Industry and Applied Mathematics, 2004. Google Scholar

[18] Mo Z Y, Zhang A Q, Cao X L, et al. JASMIN: a parallel software infrastructure for scientific computing. Front Comput Sci China, 2010, 4: 480-488 CrossRef Google Scholar

[19] Pei W B. The construction of simulation algorithm for laser fusion. Commun Comput Phys, 2007, 2: 255-270. Google Scholar

[20] Pei W B, Zhu S P. Scientific computing for laser fusion. Physics, 2009, 38: 559-568 [裴文兵, 朱少平. 激光聚变中的科学计算. 物理, 2009, 38: 559-568]. Google Scholar

[21] An H B, Mo Z Y, Xu X W, et al. On choosing a nonlinear initial iterate for solving the 2-D 3-T heat conduction equations. J Comput Phys, 2009, 228: 3268-3287 CrossRef Google Scholar

[22] Baldwin C, Brown P, Falgout R, et al. Iterative linear solvers in 2D radiation-hydrodynamics code: methods and performance. J Comput Phys, 1999, 154: 1-40 CrossRef Google Scholar

[23] Xu X W, Mo Z Y, An H B. Algebraic two-level iterative method for 2D-3T radiation diffusion equations. Chinese J Comput Phys, 2009, 26: 1-8 [徐小文, 莫则尧, 安恒斌. 求解二维三温辐射扩散方程组的一种代数两层网 格迭代方法. 计算物理, 2009, 26: 1-8]. Google Scholar

[24] Zhou Z Y, Xu X W, Shu S, et al. An adaptive two-level preconditioner for 2D-3T radiation diffusion equations. Chinese J Comput Phys, 2012, 29: 475-483 [周志阳, 徐小文, 舒适, 等. 二维三温辐射扩散方程两层预条件子的自适应求解. 计算物理, 2012, 29: 475-483]. Google Scholar

[25] Yue X Q, Shu S, Xu X W, et al. An adaptive combined preconditioner with applications in radiation diffusion equations. Commun Comput Phys, 2015, 18: 1313-1335 CrossRef Google Scholar

[26] Fan Z F, Xu X W, Sun W J, et al. Radiation hydrodynamic instabilities simulation code LARED-S. In: Proceedings of the 16th National Conference on Numeical Methods for Hydrodynamic, Kunming, 2013. 25-26 [范征锋, 徐小文, 孙文俊, 等. 辐射流体界面不稳定性模拟程序LARED-S. 见: 第十六届全国流体力学数值方法研讨会论文集, 昆明, 2013. 25-26]. Google Scholar

[27] Zhang W Y, Ye W H, Wu J F, et al. Hydrodynamic instabilities of laser indirect-drive inertial-confinement-fusion implosion. Sci Sin-Phys Mech Astron, 2014, 44: 1-23 [张维岩, 叶文华, 吴俊峰, 等. 激光间接驱动聚变內爆流体不稳定性研究. 中国科学: 物理学 力学 天文学, 2014, 44: 1-23]. Google Scholar

[28] Fan Z F, Zhu S P, Pei W B, et al. Numerical inverstigation on the stabilization of the deceleration phase Rayleigh-Taylor instability due to alpha particle heating in ignition target. Euro Phys Lett, 2012, 99: 5003. Google Scholar

[29] Henson V E, Yang U M. BoomerAMG: a parallel algebraic multigrid solver and preconditioner. Appl Numer Math, 2002, 41: 155-177 CrossRef Google Scholar

[30] Xu X W, Mo Z Y, Wu L P. Analysis of communication-to-computation based on asymptotic size for iterative methods. Chinese J Comput, 2013, 36: 782-789 [徐小文, 莫则尧, 武林平. 迭代方法中基于渐近规模的通信与计算比分析. 计算机学报, 2013, 36: 782-789]. Google Scholar