数学物理方程离散特征值问题的几何网格因式分解算法

doi:10.12286/jssx.j2022-0969

计算数学 ›› 2022, Vol. 44 ›› Issue (4): 433-465.DOI: 10.12286/jssx.j2022-0969

• 论文 • 下一篇

数学物理方程离散特征值问题的几何网格因式分解算法

孙家昶

中国科学院软件研究所并行软件与计算科学实验室, 北京 100080

收稿日期:2022-06-27 出版日期:2022-11-14 发布日期:2022-11-08
基金资助:
国家重点研发计划高性能计算重点专项（2016YFB0200601），中国科学院软件研究所基础研究项目资助.

PDF ( 152 ) 引用

孙家昶. 数学物理方程离散特征值问题的几何网格因式分解算法[J]. 计算数学, 2022, 44(4): 433-465.

Sun Jiachang. ON FACTORIZATION ALGORITHM WITH GEOMETRIC PREPROCESSING FOR DISCRETE EIGEN-PROBLEMS IN MATHEMATICAL-PHYSICS[J]. Mathematica Numerica Sinica, 2022, 44(4): 433-465.

ON FACTORIZATION ALGORITHM WITH GEOMETRIC PREPROCESSING FOR DISCRETE EIGEN-PROBLEMS IN MATHEMATICAL-PHYSICS

Sun Jiachang

Laboratory of Parallel Software and Computational Science, Institute of Software, Chinese Academy of Sciences, Beijing 100080, China

Received:2022-06-27 Online:2022-11-14 Published:2022-11-08

本文提出求解数学物理方程大型离散特征值问题的几何网格预变换块因式分解算法(简称GPA算法).
通过长期研究我们发现:结构化网格矩阵$G$满足幂等方程$G^m=I_N,(m\ll N={\rm dim}(G))$,故可在实数域或复数范围内进行因式分解;且$G$与有限元刚度矩阵$A$之间乘法存在互易性:$A\cdot G=G\cdot A$,利用$G$的几何不变性可把$N$阶大型矩阵$A$正交分解为$m-$块对角块矩阵异步并行是我们算法的计算数学基础.
本文以正三角形、方形、平行六边形及正十七边形等结构化网格为例,特别是详细分析了六边形上的离散特征值异步并行算法及程序实现细节.文后附有若干2-3万阶量级离散矩阵特征值的桌面电脑数值计算例子(正三角形与方形网格,串行加速比分别为3-4倍),符合本文算法分析得出的"几何网格预处理的并行度与正多边形边数成正比"的结论.这类几何网格因式分解算法原则上可推广到三维乃至高维数学物理方程离散特征值计算问题，也可用于大型线性方程组的高效并行求解.

关键词： 数理方程离散特征值, 互易算子, 几何块预处理子, 特征值问题因式分解, 异步并行算法

A geometric asynchronous parallel algorithm for solving large-scale discrete mathematical-physical system with structured mesh is presented. By using the intrinsic geometry symmetry, geometric matrix $G$ and the stiff matrix $A$ satisfies reciprocal operator $A\cdot G=G \cdot A$, which $G$ satisfies $G^m=I$, large scale system solvers can be replaced to block-solver as a pretreatment. In this paper, we restrict ourselves to arbitrarily regular polygon mesh, such as triangle, square, hexagon, as well as heptadecagon.

Key words: Mathematical-physical discrete eigenvalue problems, Reciprocal operator, Geometry pre-processing, Factorization, Parallel algorithm

MR(2010)主题分类:

分享此文:

[1] 孙家昶, 有关PDE本征问题数学模型与新型计算模式的设想[R]. 国家973"新型计算模式"项目组第一次全体会议大会特邀报告, 莫干山:2011, 8, 20.
[2] Chandra. Conjugate Gradient Methods for Partial Differential Equations[M]. PhD Thesis, Yale University, 1978.
[3] Eisenstat S C, Elman H C and Schultz M H. Variational alternative methods for nonsymmetric systems of linear equations[J]. SIAM Journal on Numerical Analysis, 1983, 20(2):345-357.
[4] Sun Jiachang, Cao Jianwen. Large scale petroleum reservoir simulation and parallel preconditioning algorithms research[J]. Science in China Series A:Mathematics, 2004, 47:32-40.
[5] Sun J C. Multi-Neighboring Grids Schemes for solving PDE eigen-problems[J]. Sci China Math, 2013, 56:2677-2700.
[6] Sun J C. New schemes with fractal error compensation for PDE eigenvalue computations[J]. Sci China Math, 2014, 57:221-244.
[7] 孙家昶, 曹建文, 张娅. 偏微分方程特征值计算的上下界分析与高精度格式构造[J]. 中国科学:数学, 2015, 45(8):1169-1191.
[8] Daniele Boffi, Franco Brezzi and Lucia Gastaldi. On the problem of spurious eigenvalues in the approximation of linear elliptic problems in mixed form[J]. Math. Comp., 1999, 69(229):121-140.
[9] Auckenthaler T, Blum V, Bungartz H J, et al. Parallel solution of partial symmetric eigenvalue problem from electronic structure calculations[J]. Parallel Computing, 2011, 37(12):783-794.
[10] Johanni R, Marek A, Lederer H and Blum V. Scaling of eigenvalue solver dominated simulations, in:Juelich Blue Gene/P Extreme Scaling Workshop 2011, Eds:B. Mohr, W. Frings, Technical Report FZJ-JSC-IB-2011-02, April (2011), 27-30.
[11] Buffa A and Perugia I. Discontinuous Galerkin approximation of the Maxwell eigenproblem[J]. SIAM Journal on Numerical Analysis, 2006, 44(5):2198-2226.
[12] Caorsi S, Fernandes P, and Raffetto M. On the convergence of Galerkin finite element approximation of electromagnetic eigenproblems[J]. SIAM Journal on Numerical Analysis, 2000, 38(2):580-607.
[13] Hou Thomas Y, Huang De, Lam Ka Chun and Zhang Pengchuan. An adaptive fast solver for a general class of positive definite matrices via energy decomposition[J]. Multiscale Model & Simulation, 2018, 16(2):615-678.
[14] Hou Thomas Y, Huang De, Lam Ka Chun and Zhang Ziyun. A fast hierarchically preconditioned eigensolver based on multiresolution matrix decomposition[J]. Multiscale Model & Simulation, 2019, 17(1):260-306.
[15] 孙家昶. 非传统区域Fourier变换与正交多项式[M]. 中国科学技术大学出版社, 2009.
[16] Chan T, E Weinan and Sun J C. Domain decomposition interface preconditioners for fourth-order elliptic problems[J]. Applied Numerical Mathematics, 1991, 8(4-5):317-331.
[17] 孙家昶. 有限元特征值计算中的子空间二次解耦算法[J]. 数值计算与计算机应用, 2021, 42(2):104-125.
[18] 孙家昶. 特征值问题的预变换方法(I):杨辉三角阵变换与二阶PDE特征多项式[J]. 中国科学:数学, 2011, 41(8):701-725.
[19] 孙家昶. 特征值的预变换方法(II):任意三角形域Laplace特征值的计算分析[J]. 计算数学, 2012, 34(1):1-24.
[20] 孙家昶. 矩阵特征值分离度的下界[J]. 计算数学, 1985, 7(3):309-317.

[1]	缪树鑫. 关于“求解加权线性最小二乘问题的一类预处理GAOR方法”一文的注记[J]. 计算数学, 2022, 44(1): 89-96.
[2]	何军, 刘衍民, 许光俊. 四阶不完全对称张量M-特征值的新包含域及应用[J]. 计算数学, 2021, 43(4): 457-470.
[3]	王艺宏, 李耀堂. 一类特征值反问题(IEP)的基于矩阵方程的Ulm型算法[J]. 计算数学, 2021, 43(4): 444-456.
[4]	王丽, 罗玉花, 王广彬. 求解加权线性最小二乘问题的一类预处理GAOR方法[J]. 计算数学, 2020, 42(1): 63-79.
[5]	罗刚, 杨庆之. 一类张量特征值互补问题[J]. 计算数学, 2019, 41(4): 406-418.
[6]	孟纯军, 杨泽昱, 李晗. 双倍维Jacobi矩阵逆问题的改进算法[J]. 计算数学, 2019, 41(3): 335-342.
[7]	孙家昶, 张娅. 二维等谱问题研究的计算数学框架[J]. 计算数学, 2017, 39(3): 229-286.
[8]	单炜琨, 李会元. 双调和算子特征值问题的混合三角谱元方法[J]. 计算数学, 2017, 39(1): 81-97.
[9]	潘春平. 关于Katz指标的二级分裂迭代方法[J]. 计算数学, 2015, 37(4): 390-400.
[10]	曹阳, 戴华. 非线性特征值问题的二次近似方法[J]. 计算数学, 2014, 36(4): 381-392.
[11]	潘春平 . 关于PageRank的广义二级分裂迭代方法[J]. 计算数学, 2014, 36(4): 427-436.
[12]	任志茹. 三阶线性常微分方程Sinc方程组的结构预处理方法[J]. 计算数学, 2013, 35(3): 305-322.
[13]	周星月, 戴华. 陀螺系统特征值问题的收缩Jacobi-Davidson方法[J]. 计算数学, 2012, 34(4): 341-350.
[14]	刘仲云, 刘成志, 张育林. 对称正定Toeplitz方程组的多级迭代求解[J]. 计算数学, 2012, 34(4): 397-404.
[15]	秦晓伟, 刘新国, 赵娜. 关于解极大相关问题问题P-SOR算法的收敛性[J]. 计算数学, 2011, 33(4): 345-356.

阅读次数

全文

摘要

数学物理方程离散特征值问题的几何网格因式分解算法

ON FACTORIZATION ALGORITHM WITH GEOMETRIC PREPROCESSING FOR DISCRETE EIGEN-PROBLEMS IN MATHEMATICAL-PHYSICS

扫码分享