• 青年评述 •    下一篇

子空间扩展算法及其应用

谢和虎1,2   

  1. 1 中国科学院数学与系统科学研究院, 计算数学研究所, 国家数学与交叉科学中心, 科学与工程计算国家重点实验室, 北京 100190;
    2 中国科学院大学数学科学学院, 北京 100049
  • 收稿日期:2020-03-02 出版日期:2020-09-15 发布日期:2020-09-15
  • 作者简介:谢和虎,中国科学院数学与系统科学研究院研究员.2003年毕业于北京大学,2008年在中国科学院数学与系统科学研究院获博士学位,博士毕业后进入中国科学院数学与系统科学研究院工作至今,期间于2009-2010年在德国马格德堡大学从事博士后研究,2011-2012年在香港浸会大学任Croucher基金学者.主要从事偏微分方程数值算法、特征值问题算法及其应用、积微分方程数值算法等,提出和发展了求解非线性问题和特征值问题的多水平校正算法.曾获中国科学院数学与系统科学研究院"陈景润未来之星"称号,《Science China:Mathematics》优秀论文奖.
  • 基金资助:

    国家重点研发计划项目(2019YFA0709601),科学挑战计划(TZ2016002)和国家自然科学基金(11771434,91730302)资助.

谢和虎. 子空间扩展算法及其应用[J]. 数值计算与计算机应用, 2020, 41(3): 169-191.

Xie Hehu. AN AUGMENTED SUBSPACE METHOD AND ITS APPLICATIONS[J]. Journal on Numerica Methods and Computer Applications, 2020, 41(3): 169-191.

AN AUGMENTED SUBSPACE METHOD AND ITS APPLICATIONS

Xie Hehu1,2   

  1. 1 LSEC, NCMIS, Institute of Computational Mathematics, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China;
    2 School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing 100049, China
  • Received:2020-03-02 Online:2020-09-15 Published:2020-09-15
科学研究与工程实际中存在着大量的非线性偏微分方程,这使得非线性方程的求解变得越来越重要.本综述论文利用定义在粗网格上的有限元空间来重建任意有限元函数的Aubin-Nitsche技巧的误差估计.然后介绍如何利用这种对Aubin-Nitsche技巧的新视角来设计求解半线性椭圆方程和特征值问题的扩展子空间算法,同时给出相应的收敛性分析和计算量估计.特别地,当求解多项式形式的非线性方程和特征值问题的时候,扩展子空间算法的渐进计算量可以达到最优.本文的论述表明扩展子空间算法是一种用来设计求解非线性方程快速算法的框架,可以应用于更广泛的非线性方程的求解,同时也可以结合各种高效的线性解法器来提高非线性方程的求解效率.
There exist plenty of nonlinear partial differential equations in scientific research and practical engineer, which leads to the importance of numerical methods for nonlinear problems. This review paper introduces a method to build the Aubin-Nitsche estimate based on a low dimensional finite element space defined on a coarse mesh. Based on this new understanding of Aubin-Nitsche technique, an augmented subspace method is designed for semilienar elliptic equations and eigenvalue problems. The corresponding convergence analysis and estimates of computational work are provided to validate the efficiency of the presented method. Especially, the augmented subspace method gives absolutely and nonlinear independently optimal computational work for polynomial types of nonlinear partial differential equations and eigenvalue problems. This paper also shows that the augmented subspace method provides a framework to design efficient nonlinear solvers for general nonlinear equations.

MR(2010)主题分类: 

()
[1] Adams R A. Sobolev Spaces[M]. Academic Press, New York, 1975.

[2] Babuška I and Osborn J. Finite element-Galerkin approximation of the eigenvalues and eigenvectors of selfadjoint problems[J]. Math. Comp., 1989, 52:275-297.

[3] Bank R E, Dupont T. An optimal order process for solving finite element equations[J]. Math. Comp., 1981, 36:35-51.

[4] Bramble J H. Multigrid Methods. Pitman Research Notes in Mathematics, Vol. 294, John Wiley and Sons, 1993.

[5] Bramble J H and Pasciak J E. New convergence estimates for multigrid algorithms[J]. Math. Comp., 1987, 49:311-329.

[6] Bramble J H and Zhang X. The Analysis of Multigrid Methods[J]. Handbook of Numerical Analysis, 2000, 173-415.

[7] Brandt A, McCormick S and Ruge J. Multigrid methods for differential eigenproblems[J]. SIAM J. Sci. Stat. Comput., 1983, 4(2):244-260.

[8] Brenner S and Scott L. The Mathematical Theory of Finite Element Methods[M]. New York, Springer-Verlag, 1994.

[9] Cai Z, Mandel J and McCormick S. Multigrid methods for nearly singular equations and eigenvalue problems[J]. SIAM J. Numer. Anal., 1997, 34(1):178-200.

[10] Chatelin F. Spectral Approximation of Linear Operators[M]. Academic Press Inc, New York, 1983.

[11] Chen H, He Y, Li Y and Xie H. A multigrid method for eigenvalue problems based on shiftedinverse power technique[J]. European Journal of Mathematics, 2015, 1(1):207-228.

[12] Chen H, Xie H and Xu F. A full multigrid method for eigenvalue problems[J]. J. Comput. Phys., 2016, 322:747-759.

[13] Ciarlet P G. The Finite Element Method for Elliptic Problem. North-Holland Amsterdam, 1978.

[14] Gong W, Xie H and Yan N. A multilevel correction method for optimal controls of elliptic equation[J]. SIAM J. Sci. Comput., 2015, 37(5):A2198-2221.

[15] Gong W, Xie H and Yan N. Adaptive multilevel correction method for finite element approximations of elliptic optimal control problems[J]. J. Sci. Comput., 2017, 72:820-841.

[16] Hackbusch W. On the computation of approximate eigenvalues and eigenfunctions of elliptic operators by means of a multi-grid method[J]. SIAM J. Numer. Anal., 1979, 16(2):201-215.

[17] Hackbusch W. Multi-grid Methods and Applications[M]. Springer-Verlag, Berlin, 1985.

[18] Han J, Yang Y and Bi H. A new multigrid finite element method for the transmission eigenvalue problems[J]. Appl. Math. Comput., 2017, 292(1):96-106.

[19] Han X, Li Y and Xie H. A multilevel correction method for Steklov eigenvalue problem by nonconforming finite element methods[J]. Numer. Math. Theory Methods Appl., 2015, 8(03):383-405.

[20] Han X, Li Y, Xie H and You C. Local and parallel finite element algorithm based on multilevel discretization for eigenvalue problems[J]. Int. J. Numer. Anal. Model, 2016, 13(1):73-89.

[21] Han X, Xie H and Xu F. A cascadic multigrid method for eigenvalue problem[J]. J. Comput. Math., 2017, 35(1):75-91.

[22] He Y, Li Y, Xie H, You C and Zhang N. A multilevel Newton's method for eigenvalue problems[J]. Appl. Math., 2018, 63(3):281-303.

[23] He Y and Xie H. Convergence analysis of shift-inverse method with Richardson iteration for eigenvalue problem. arXiv:1804.01936, 2018.

[24] Hu G, Xie H and Xu F. A multilevel correction adaptive finite element method for Kohn-Sham equation[J]. J. Comput. Phys., 2018, 355(15):436-449.

[25] Hu X and Cheng X. Acceleration of a two-grid method for eigenvalue problems[J]. Math. Comp., 2011, 80(275):1287-1301.

[26] Huang Y, Shi X, Tang T and Xue W. A multilevel successive iteration method for nonlinear elliptic problem[J]. Math. Comp., 2004, 73:525-539.

[27] Ji X, Sun J and Xie H. A multigrid method for Helmholtz transmission eigenvalue problems[J].J. Sci. Comput., 2014, 60(2):276-294.

[28] Jia S, Xie H, Xie M and Xu F. A full multigrid method for nonlinear eigenvalue problems[J]. Sci. China Math., 2016, 59:2037-2048.

[29] 林群. 算子方程近似解的一些问题[J]. 数学学报, 1979, 22(2):219-230.

[30] Lin q. Deferred corrections for equations of the second kind[J]. J. Aust. Math. Soc, 1980/81, 22:452-455.

[31] Lin Q. Iterative refinement of finite element approximations for elliptic problems[J]. RAIRO Anal. Numér., 1982, 16(1):39-47.

[32] 林群, 谢干权. 本征值问题的有限元方法的加速[J]. 科学通报, 1981, 26:449-452.

[33] 林群, 谢和虎. 有限元Aubin-Nitsche技巧新认识及其应用[J]. 数学的实践与认识, 2011, 41(17):247-258.

[34] Lin Q and Xie H. A multilevel correction type of adaptive finite element method for Steklov eigenvalue problems. Proceedings of the International Conference:Application of Mathematics, 2012, 134-143.

[35] Lin Q and Xie H. A multi-level correction scheme for eigenvalue problems[J]. Math. Comp., 2015, 84(291):71-88.

[36] Lin Q, Xie H and Xu F. Multilevel correction adaptive finite element method for semilinear elliptic equation[J]. Appl. Math., 2015, 60(5):527-550.

[37] Peng Z, Bi H, Li H and Yang Y. A multilevel correction method for convection-diffusion eigenvalue problems. Mathematical Problems in Engineering, 10(2015), doi:10. 1155/2015/904347.

[38] Saad Y. Numerical Methods for Large Eigenvalue Problems. Society for Industral and Applied Mathematics, 2011.

[39] Scott L and Zhang S. Higher dimensional non-nested multigrid methods[J]. Math. Comp., 1992, 58:457-466.

[40] Toselli A and Widlund O. Domain Decomposition Methods:Algorithm and Theory. SpringerVerlag, Berlin Heidelberg, 2005.

[41] Shaidurov V V. Multigrid Methods for Finite Elements. Kluwer Academic Publics, Netherlands, 1995.

[42] Xi Y, Ji X and Zhang S. A multi-level mixed element scheme of the two-dimensional Helmholtz transmission eigenvalue problem. IMA J. Numer. Anal., 2020, 40(1):686-707.

[43] Xie H. A type of multilevel method for the Steklov eigenvalue problem[J]. IMA J. Numer. Anal., 2014, 34:592-608.

[44] Xie H. A multigrid method for eigenvalue problem[J]. J. Comput. Phys., 2014, 274:550-561.

[45] Xie H.非线性特征值问题的多重网格算法[J]. 中国科学:数学, 2015, 45(8):1193-1204.

[46] Xie H. A type of multi-level correction scheme for eigenvalue problems by nonconforming finite element methods[J]. BIT Numerical Mathematics, 2015, 55(4):1243-1266.

[47] Xie H and Wu X. A multilevel correction method for interior transmission eigenvalue problem[J]. J. Sci. Comput., 2017, 72:586-604.

[48] Xie H and Xie M. A multigrid method for the ground state solution of Bose-Einstein condensates. Commun. Comput. Phys., 2016, 19(3):648-662.

[49] 谢和虎, 谢满庭, 张宁. 一种求解半线性椭圆问题的快速多重网格法[J]. 数值计算与计算机应用, 2019, 40(2):143-160.

[50] Xie H, Zhang L and Owhadi H. Fast eigenvalue computation with operator adapted wavelets and hierarchical subspace correction[J]. SIAM J. Numer. Anal, 2019, 57(6):2519-2550.

[51] Xie H and Zhou T. A multilevel finite element method for Fredholm integral eigenvalue problems[J]. J. Comput. Phys., 2015, 303:173-184.

[52] Xu F and Xie H. A full multigrid method for semilinear elliptic equation[J]. Appl. Math., 2017, 62(3):225-241.

[53] Xu F, Xie H and Zhang N. An eigenwise parallel augmented subspace method for eigenvalue problems. arXiv:1908.10251, 2019.

[54] Xu J. Iterative methods by space decomposition and subspace correction[J]. SIAM Review, 1992, 34(4):581-613.

[55] Xu J. A new class of iterative methods for nonselfadjoint or indefinite problems[J]. SIAM J. Numer. Anal., 1992, 29(2):303-319.

[56] Xu J. A novel two-grid method for semilinear elliptic equations[J]. SIAM J. Sci. Comput., 1994, 15(1):231-237.

[57] Xu J. Two-grid discretization techniques for linear and nonlinear PDEs[J]. SIAM J. Numer. Anal., 1996, 33(5):1759-1777.

[58] Xu J and Zhou A. A two-grid finite element discretization for eigenvalue problems. Math. Comput., 2001, 70:17-25.

[59] Xu J and Zhou A. Local and parallel finite element algorithms based on two-grid discretizations. Math. Comput, 2000, 69:881-909.

[60] Xu J and Zikatanov L. Algebraic multigrid methods[J]. Acta Numerica, 2017, 26:591-721.

[61] 徐小文. 并行代数多重网格算法:大规模计算应用现状与挑战[J]. 数值计算与计算机应用, 2019, 40(4):243-260.

[62] Yang Q, Zhou Y and Yang Y. An extension of Yuan's lemma to fourth-order tensor system. J. Optim. Theory Appl., 2019, 180(3):803-810.

[63] Yang Y and Bi H. Two-grid finite element discretization schemes based on shifted-inverse power method for elliptic eigenvalue problems[J]. SIAM J. Numer. Anal., 2011, 49(4):1602-1624.

[64] Yue M, Xie H and Xie M. A cascadic multigrid method for nonsymmetric eigenvalue problem[J]. Appl. Numer. Math., 2019, 146:55-72.

[65] Zhang N, Han X, He Y, Xie H and You C. An algebraic multigrid method for eigenvalue problems in some different cases. arXiv:submit/3065628, 2015.

[66] Zhang N, Xu F and Xie H. An efficient multigrid method for ground state solution of Bose-Einstein condensates[J]. Int. J. Numer. Anal. Model., 2019, 16(5):789-803.

[67] Zhang S, Xi Y and Ji X. A multi-level mixed element method for the eigenvalue problem of biharmonic equation[J]. J. Sci. Comput., 2018, 75:1415-1444.

[68] Zhou A. Multi-level adaptive corrections in finite dimensional approximations[J]. J. Comp. Math., 2010, 28(1):45-54.
[1] 王芹, 马召灿, 白石阳, 张林波, 卢本卓, 李鸿亮. 三维半导体器件漂移扩散模型的并行有限元方法研究[J]. 数值计算与计算机应用, 2020, 41(2): 85-104.
[2] 葛志昊, 李婷婷, 王慧芳. 双资产欧式期权定价问题的特征有限元方法[J]. 数值计算与计算机应用, 2020, 41(1): 27-41.
[3] 李瑜, 谢和虎. 基于特征线法的群体平衡系统的数值模拟[J]. 数值计算与计算机应用, 2019, 40(4): 261-278.
[4] 谢和虎, 谢满庭, 张宁. 一种求解半线性问题的快速多重网格法[J]. 数值计算与计算机应用, 2019, 40(2): 143-160.
[5] 邓维山, 徐进. 一种泊松-玻尔兹曼方程稳定算法的高效有限元并行实现[J]. 数值计算与计算机应用, 2018, 39(2): 91-110.
[6] 余涛, 张镭. 线性弹性问题的局部正交分解方法[J]. 数值计算与计算机应用, 2018, 39(1): 10-19.
[7] 龚方徽, 孙玉泉, 杨柳. 二次正交Arnoldi方法的隐式重启算法[J]. 数值计算与计算机应用, 2017, 38(4): 256-270.
[8] 杨建宏. 定常Navier-Stokes问题低次等阶稳定有限体积元算法研究[J]. 数值计算与计算机应用, 2017, 38(2): 91-104.
[9] 周宇, 李秋齐. 基于降基多尺度有限元的PGD方法及其在含参数椭圆方程中的应用[J]. 数值计算与计算机应用, 2017, 38(2): 105-122.
[10] 曹济伟, 葛志昊, 刘鸣放. Stokes方程基于多尺度函数的稳定化有限元方法[J]. 数值计算与计算机应用, 2017, 38(1): 68-80.
[11] 张慧荣, 曹建文, 孙家昶. 不等距网格上求解ODE特征值问题若干高精度格式的计算与分析[J]. 数值计算与计算机应用, 2014, 35(2): 131-152.
[12] 周志强, 吴红英. 分数阶对流-弥散方程的移动网格有限元方法[J]. 数值计算与计算机应用, 2014, 35(1): 1-7.
[13] 秦佩华. 非光滑区域上椭圆型特征值问题的间断有限元方法应用[J]. 数值计算与计算机应用, 2012, 33(4): 293-300.
[14] 杨建宏. 定常Navier-Stokes方程的三种两层稳定有限元算法计算效率分析[J]. 数值计算与计算机应用, 2011, 32(2): 117-124.
[15] 程俊霞, 任健. 含曲率的水平集方程在非结构四边形网格上的数值离散方法[J]. 数值计算与计算机应用, 2011, 32(1): 33-40.
阅读次数
全文


摘要