Feature-modified Algorithm Framework for Parallel Preconditioning in Sparse Linear Solvers

doi:10.19596/j.cnki.1001-246x.8787

Abstract

Abstract:

To address the high computational complexity of sparse linear solvers caused by complex physical characteristics in practical applications, this paper presents a unified framework for feature-modified preconditioning algorithms. By refining the algebraic features affecting the efficiency from physical characteristics and combining multilevel feature analysis, we construct feature-modified components. The effectiveness of this framework is demonstrated through several typical feature-modified preconditioning algorithms and their application results.

Key words: sparse linear algebraic equations, feature-modified, iterative methods, preconditioning algorithms, parallel algorithms

CLC Number:

O246

Xiaowen XU, Zeyao MO, Shaoliang HU, Hengbin AN. Feature-modified Algorithm Framework for Parallel Preconditioning in Sparse Linear Solvers[J]. Chinese Journal of Computational Physics, 2024, 41(1): 64-74.

Figures/Tables 9

References 28

1	莫则尧, 张爱清, 曹小林, 等. 多介质辐射流体力学数值模拟中的并行计算研究[J]. 自然科学进展, 2006, 16 (3): 287- 292. DOI
2	ANG J, EVANS K, GEIST A, et al. Report on the workshop on extreme-scale solvers: Transition to future architectures[R]. Washington, D. C: Office of Advanced Scientific Computing Research, U.S. Department of Energy, 2012: 8-9.
3	ANZT H , BOMAN E , FALGOUT R , et al. Preparing sparse solvers for exascale computing[J]. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 2020, 378 (2166): 20190053. DOI
4	SAAD Y . Iterative methods for sparse linear systems[M]. 2nd ed Philadelphia: SIAM.
5	FALGOUT R D, YANG U M. hypre: A library of high performance preconditioners[C]//Computational Science-ICCS 2002. Amsterdam, The Netherlands: Springer, 2002: 632-641.
6	BALAY S , ABHYANKAR S , ADAMS M , et al. PETSc users manual[M]. Argonne, IL: Argonne National Laboratory, 2019.
7	HEROUX M A , BARTLETT R A , HOWLE V E , et al. An overview of the Trilinos project[J]. ACM Transactions on Mathematical Software, 2005, 31 (3): 397- 423. DOI
8	XU Xiaowen , YUE Xiaoqiang , MAO Runzhang , et al. JXPAMG: A parallel algebraic multigrid solver for extreme-scale numerical simulations[J]. CCF Transactions on High Performance Computing, 2023, 5 (1): 72- 83. DOI
9	胡少亮, 徐小文, 安恒斌, 等. 应用特征驱动的并行数值代数解法器JPSOL[J]. 计算物理, 2024, 41 (1): 110- 121. DOI
10	TROTTENBERG U , OOSTERLEE C W , SCHULLER A . Multigrid[M]. San Diego: Academic Press, 2000.
11	徐小文. 并行代数多重网格算法: 大规模计算应用现状与挑战[J]. 数值计算与计算机应用, 2019, 40 (4): 243- 260.
12	XU Xiaowen , MO Zeyao . 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. DOI
13	刘笑, 徐小文. 求解多尺度稀疏矩阵的代数界面优先AMG光滑子[J]. 数值计算与计算机应用, 2023, 44 (1): 1- 11.
14	胡少亮, 徐小文, 郑宇腾, 等. 系统级封装应用中时谐Maxwell方程大规模计算的求解算法: 现状与挑战[J]. 计算物理, 2021, 38 (2): 131- 145. DOI
15	AN Hengbin , MO Zeyao , WANG Jingtao , et al. Shear decoupled parallel scalable preconditioners for nonlinear Thermo-Mechanical coupled contact applications[J]. Journal of Scientific Computing, 2022, 90, 4. DOI
16	徐小文, 莫则尧, 安恒斌. 求解二维三温辐射扩散方程组的一种代数两层迭代方法[J]. 计算物理, 2009, 26 (1): 1- 8.
17	徐小文, 莫则尧, 安恒斌. 求解大规模稀疏线性代数方程组序列的自适应AMG预条件策略[J]. 中国科学(信息科学), 2016, 46 (10): 1411- 1420.
18	XU Xiaowen , MO Zeyao , YUE Xiaoqiang , et al. αSetup-AMG: an adaptive-setup-based parallel AMG solver for sequence of sparse linear systems[J]. CCF Transactions on High Performance Computing, 2020, 2 (2): 98- 110. DOI
19	HUANG Silu , YUE Xiaoqiang , XU Xiaowen . αSetup-PCTL: An adaptive setup-based two-level preconditioner for sequence of linear systems of three-temperature energy equations[J]. Communications in Computational Physics, 2022, 32 (5): 1287- 1309. DOI
20	胡少亮, 许开龙, 徐然, 等. 求解压力Poisson方程的混合粗化代数多重网格算法[J]. 计算物理, 2023, 40 (5): 527- 534. DOI
21	舒适, 岳孝强, 何剑萌, 等. 多群辐射扩散问题特征驱动的并行AMG法[J]. 计算物理, 2024, 41 (1): 87- 97. DOI
22	冯春生, 李仕哲, 刘生豪, 等. 面向渗流力学应用特征的预条件方法[J]. 计算物理, 2024, 41 (1): 98- 109. DOI
23	安恒斌, 莫则尧. 辐射扩散方程的非线性迭代方法[J]. 计算物理, 2024, 41 (1): 75- 86. DOI
24	郝悦, 黄思路, 徐小文. 三温能量方程离散线性系统的两层迭代算法收敛因子估计及特征分析[J]. 计算物理, 2024, 41 (1): 122- 130. DOI
25	徐小文. 可扩展并行预条件迭代方法研究验收报告: 2017YFB0202103[R]. [S. l.:s. n.], 2021.
26	TIAN Rong , ZHOU Mozhen , WANG Jingtao , et al. A challenging dam structural analysis: large-scale implicit thermo-mechanical coupled contact simulation on Tianhe-Ⅱ[J]. Computational Mechanics, 2019, 63 (1): 99- 119.
27	邹海峰. 基于图神经网络的稀疏线性代数方程组智能迭代算法研究[D]. 北京: 中国工程物理研究院研究生院, 2023.
28	ZOU Haifeng, XU Xiaowen, ZHANG Chensong, et al. AutoAMG(θ): An auto-tuned AMG method based on deep learning for strong threshold[EB/OL]. (2023-08-16)[2023-06-10]. https://doi.org/10.48550/arXiv.2307.09879.

代数特征	内涵	特征来源	典型应用场景
代数特征	内涵	特征来源	领域	示例
分区多尺度性	是指线性方程组的系数矩阵具有多尺度性，即：矩阵非对角元素在数值上相差几个、甚至十几个数量级，且多尺度点把整体区域划分为不同尺度的子区域	该特征主要由多介质、大变形、多物理耦合与非线性效应等物理特征综合影响所致	激光聚变结构力学电子学系统	左：多尺度点的非对角线元素(S1-S6)相差6个量级；右：颜色所示的多尺度点将区域划分为不同尺度的子区域
周期非正定性	是指电子学系统仿真中时谐Maxwell方程的周期性导致离散线性方程组具有非正定性质	该特征由电磁波传播的周期性所致	电子学系统	非正定性时谐Maxwell方程：
接触非对称性	是指结构力学分析中热-力-接触多物理耦合导致离散线性方程组具有非对称性质	该特征由工程力学设计中接触耦合所致	结构力学	非对称性热-力-接触耦合方程：
耦合块结构	是指由于多物理耦合导致矩阵特有的块结构	该特征由辐射传输中辐射与电子、离子特有的耦合关系所致	激光聚变	辐射与电子、离子耦合块矩阵：$\boldsymbol{A}=\left[\begin{array}{ccc}\boldsymbol{A}_{\mathrm{r}} & \boldsymbol{D}_{\mathrm{re}} & 0 \\ \boldsymbol{D}_{\mathrm{er}} & \boldsymbol{A}_{\mathrm{e}} & \boldsymbol{D}_{\mathrm{ei}} \\ 0 & \boldsymbol{D}_{\mathrm{ie}} & \boldsymbol{A}_{\mathrm{i}}\end{array}\right]$
贯序动态变化	是指一次完整模拟需要求解由批量线性方程组构成的方程组序列，且方程组性质动态变化	该特征主要由长时间积分和非线性迭代等因素所致	激光聚变结构力学	典型多物理应用：数万时间步，每个时间步求解多个非线性系统且需近10次非线性迭代，共需要求解数十万个线性方程组：{A_ix_i=b_i, i=1, …, n_eq}，且A_i的性质动态变化

代数特征	内涵	特征来源	典型应用场景
代数特征	内涵	特征来源	领域	示例
分区多尺度性	是指线性方程组的系数矩阵具有多尺度性，即：矩阵非对角元素在数值上相差几个、甚至十几个数量级，且多尺度点把整体区域划分为不同尺度的子区域	该特征主要由多介质、大变形、多物理耦合与非线性效应等物理特征综合影响所致	激光聚变结构力学电子学系统	左：多尺度点的非对角线元素(S1-S6)相差6个量级；右：颜色所示的多尺度点将区域划分为不同尺度的子区域
周期非正定性	是指电子学系统仿真中时谐Maxwell方程的周期性导致离散线性方程组具有非正定性质	该特征由电磁波传播的周期性所致	电子学系统	非正定性时谐Maxwell方程：
接触非对称性	是指结构力学分析中热-力-接触多物理耦合导致离散线性方程组具有非对称性质	该特征由工程力学设计中接触耦合所致	结构力学	非对称性热-力-接触耦合方程：
耦合块结构	是指由于多物理耦合导致矩阵特有的块结构	该特征由辐射传输中辐射与电子、离子特有的耦合关系所致	激光聚变	辐射与电子、离子耦合块矩阵：$\boldsymbol{A}=\left[\begin{array}{ccc}\boldsymbol{A}_{\mathrm{r}} & \boldsymbol{D}_{\mathrm{re}} & 0 \\ \boldsymbol{D}_{\mathrm{er}} & \boldsymbol{A}_{\mathrm{e}} & \boldsymbol{D}_{\mathrm{ei}} \\ 0 & \boldsymbol{D}_{\mathrm{ie}} & \boldsymbol{A}_{\mathrm{i}}\end{array}\right]$
贯序动态变化	是指一次完整模拟需要求解由批量线性方程组构成的方程组序列，且方程组性质动态变化	该特征主要由长时间积分和非线性迭代等因素所致	激光聚变结构力学	典型多物理应用：数万时间步，每个时间步求解多个非线性系统且需近10次非线性迭代，共需要求解数十万个线性方程组：{A_ix_i=b_i, i=1, …, n_eq}，且A_i的性质动态变化

代数特征	具体影响	影响程度
分区多尺度性	相对于单尺度系统，该特征导致传统AMG的光滑和粗化等组件质量下降，收敛速度严重退化	算法组件算法参数
接触非对称性	传统AMG算法机理难以适应非对称问题	算法机理
周期非正定性	传统AMG算法机理难以适应非正定问题	算法机理
耦合块结构	块结构蕴含的耦合关系导致传统AMG的光滑、粗化、插值等组件质量下降，收敛速度退化	算法组件算法参数
贯序动态变化	不存在单一算法对所有系统都是线性扩展的，传统AMG算法流程限制了方程组序列动态变化的调优空间	算法流程

代数特征	具体影响	影响程度
分区多尺度性	相对于单尺度系统，该特征导致传统AMG的光滑和粗化等组件质量下降，收敛速度严重退化	算法组件算法参数
接触非对称性	传统AMG算法机理难以适应非对称问题	算法机理
周期非正定性	传统AMG算法机理难以适应非正定问题	算法机理
耦合块结构	块结构蕴含的耦合关系导致传统AMG的光滑、粗化、插值等组件质量下降，收敛速度退化	算法组件算法参数
贯序动态变化	不存在单一算法对所有系统都是线性扩展的，传统AMG算法流程限制了方程组序列动态变化的调优空间	算法流程

序号	特征修正组件	内涵
1	代数界面提取(AI)	识别并提取多尺度矩阵的关键特征，为解决分区多尺度性导致AMG算法收敛速度变慢的问题提供工具
2	正定预处理(PD)	构造具有正定性质的预条件矩阵，解决周期非正定性导致AMG算法的组件难以构造的问题
3	对称预处理(Sym)	构造具有对称性质的预条件矩阵，解决接触非对称性导致AMG算法的组件难以构造的问题
4	物理量粗化(PCTL)	基于特殊粗化解耦块结构系统，解决耦合块结构导致AMG算法收敛速度变慢的问题
5	自适应启动(aSetup)	设置算法空间及自适应切换条件，解决贯序动态变化特征导致AMG算法静态策略可扩展性瓶颈