• 论文 • 上一篇    

有限元特征值计算中的子空间二次解耦算法

孙家昶   

  1. 中国科学院软件研究所计算科学与并行软件研究室, 北京 100080
  • 收稿日期:2021-02-23 发布日期:2021-06-03
  • 基金资助:
    国家重点研发计划高性能计算重点专项(2016YFB0200601)资助.

孙家昶. 有限元特征值计算中的子空间二次解耦算法[J]. 数值计算与计算机应用, 2021, 42(2): 104-125.

Sun Jiachang. ALGORITHMS OF DOUBLE-DECOUPLING SUBSPACES FOR SOLVING FEM EIGEN-PROBLEMS[J]. Journal on Numerica Methods and Computer Applications, 2021, 42(2): 104-125.

ALGORITHMS OF DOUBLE-DECOUPLING SUBSPACES FOR SOLVING FEM EIGEN-PROBLEMS

Sun Jiachang   

  1. Institute of Software, Chinese Academy of Sciences, Beijing 100080, China
  • Received:2021-02-23 Published:2021-06-03
解线性方程组预条件子算法已在求解偏微分方程(PDE)的离散代数系统的高性能计算中取得巨大成功. 相比之下, PDE 特征值问题本身的高效快速并行的潜力目前远未发挥.根据代数基本定理可知, 通过因式分解, 任意一个一元 n 次实特征多项式可分解为若干个低次实多项式(如二次)或一次实多项式的乘积, 因此, 利用PDE方程的特征变换(如Fourier变换等)作预变换 有可能把离散的高阶广义特征值问题直接解耦分解为一批低阶广义矩阵特征值的并行计算. 本文以三次 Hermite 插值有限元为例, 提出求解一类离散椭圆PDE 广义特征值的二次解耦算法。新算法不但 降低了常规算法 (先把广义特征值问题化为普通特征值问题, 再分解为 n 个一次多项式乘积)的计算复杂度, 性能提升明显, 而且能有效判别与防止伪特征值的出现(Spurious free无伪解).
By using so-called preconditioning algorithms, it has been successful to solve PDE discrete algebraic systems in high performance computations. However, the potential of PDE eigen-problem solver is still far from expected. It is well-known that from the fundamental algebraic theorem, any n?degree polynomial can be decomposed into a product with several lower degree, such as quadratic polynomials, and linear terms. Therefore, by using some characteristic transforms, such as discrete Fourier, it is possible to decouple the original high order eigen-problem into some lower eigen-problems in parallel. In this paper, we take a cubic Hermite-interpolation as an example, an algorithm of Double-Decoupling Subspaces for Solving FEM Eigen-problems is proposed for solving a class of discrete elliptic generalized eigen-problems. Performance has been raised obviously, comparing with the traditional algorithm: turn to ordinary eigen-problem first, then do diagonalization at once. Moreover, the new algorithm can judge spurious-free and prevent from spurious eigenvalues.

MR(2010)主题分类: 

()
[1] Strang G. An analysis of the finite element method[J]. Prentice-Hall, 1973.
[2] 孙家昶. 有关PDE本征问题数学模型与新型计算模式的设想[R]. 国家973“新型计算模式”项目组第一次全体会议大会特邀报告2011.8.20莫干山.
[3] Chandra. PhD Thesis[D]. Yale University, 1978.
[4] Eisenstat S C, Elman H C and Schultz M H. Variation aliterative methods for nonsymmetric systems of linear equations[J]. Society for Industrial and Applied Mathematics, 1983, 20(2): 345– 357.
[5] Sun Jiachang, Cao Jianwen. Large scale petroleum reservoir simulation and parallel preconditioning algorithms reserch[J]. Science in China Ser. A, 2004, 47: 32–40.
[6] Sun Jiachang and Li Huiyuan. Generalized Fourier transform on an arbitrary tirangular domain[J]. Advances in Computational Mathematics, 2005, 22: 223–248.
[7] Sun J C, Multi-Neighboring Grids Schemes for solving PDE eigen-problems[J]. Sci China Math, 2013, 56: 2677–2700.
[8] Sun J C, New schemes with fractal error compensation for PDE eigenvalue computations[J]. Sci China Math, 2014, 57: 221–244.
[9] 孙家昶, 曹建文, 张娅. 偏微分方程特征值计算的上下界分析与高精度格式构造[J]. 中国科学: 数学, 2015, 45(8): 1169–1191.
[10] Daniele Boffi, Franco Brezzi and Lucia Gastaldi. On the problem of Spurious eigenvalues in the approximation of linear elliptic preblems in mixed form[J]. Mathematics Of Computation, 1999, 69(220): 121–140.
[11] Auckenthaler T, Bungartz H J, Huckle T, Kramer L, Lang B, Willems P. Developing algorithms and software for the parallel solution of the symmetric eigenvalue problem[J]. Journal of Computational Science, 2011, 2: 272–278.
[12] Auckenthaler T et al. Parallel solution of partial symmetric eigenvalue problem from electronic structure calculations[J]. Parallel Computing, 2011, 27(12): 783–794. doi:10,1016/j.jocs. 2011.05.002
[13] Johanni R et al. Scaling of Eigenvalue Solver Dominated Similations. In Technical Report F ZJ -JSCIB2011-02, 2011, 27–30.
[14] Buffa A and Perugia I. Discontinuous Galeikin Approximation of the Maxwell Eigenproblem[J]. SIAM Numer. Anal., 2006, 44: 2198–2226
[15] Caorsi S, Fernandes P and Raffetto M. On the convergence of Galerkin finite element approximations of eletromagneic eigenproblems[J]. SIAM Numer. Anal., 2000, 38: 580–607.
[16] Ahmed N, Natarajan T and Rao K R. Discrete Cosine Transform[J]. IEEE Transsactions on Computers, 1974, 90–93.
[17] Britanak V, Yip P C and Rao K R. Discrete Cosine and Sine Transforms General properties, Fast Algorithms and Integer Approximations[M]. Academic Press, 2007.
[1] 王丽. 三类新的求解广义最小二乘问题的预处理GAOR方法[J]. 数值计算与计算机应用, 2020, 41(4): 282-296.
[2] 谢和虎. 子空间扩展算法及其应用[J]. 数值计算与计算机应用, 2020, 41(3): 169-191.
[3] 陈星玎, 李思雨. 求解PageRank的多步幂法修正的广义二级分裂迭代法[J]. 数值计算与计算机应用, 2018, 39(4): 243-252.
[4] 龚方徽, 孙玉泉, 杨柳. 二次正交Arnoldi方法的隐式重启算法[J]. 数值计算与计算机应用, 2017, 38(4): 256-270.
[5] 单炜琨, 李会元. 任意三角形Laplace特征值问题谱方法的数值对比研究[J]. 数值计算与计算机应用, 2015, 36(2): 113-131.
[6] 梁觊, 戴华. 求解对称特征值问题的块Chebyshev-Davidson方法[J]. 数值计算与计算机应用, 2011, 32(3): 209-219.
[7] 杨志明. Z-矩阵最小特征值界的估计[J]. 数值计算与计算机应用, 2011, 32(2): 81-88.
[8] 王顺绪, 戴华. 二次特征值问题的并行Jacobi-Davidson方法及其应用[J]. 数值计算与计算机应用, 2008, 29(4): 313-320.
阅读次数
全文


摘要