On the convergence of a two-level preconditioned Jacobi–Davidson method for eigenvalue problems

Wang, Wei; Xu, Xuejun

doi:10.1090/mcom/3403

On the convergence of a two-level preconditioned Jacobi–Davidson method for eigenvalue problems
HTML articles powered by AMS MathViewer

by Wei Wang and Xuejun Xu;

Math. Comp. 88 (2019), 2295-2324

DOI: https://doi.org/10.1090/mcom/3403

Published electronically: December 20, 2018

HTML | PDF | Request permission

Abstract:

In this paper, we shall give a rigorous theoretical analysis of the two-level preconditioned Jacobi–Davidson method for solving the large scale discrete elliptic eigenvalue problems, which was essentially proposed by Zhao, Hwang, and Cai in 2016. Focusing on eliminating the error components in the orthogonal complement space of the target eigenspace, we find that the method could be extended to the case of the $2m$th order elliptic operator ($m=1,2$). By choosing a suitable coarse space, we prove that the method holds a good scalability and we obtain the error reduction $\gamma =c(1-C\frac {\delta ^{2m-1}}{H^{2m-1}})$ in each iteration, where $C$ is a constant independent of the mesh size $h$ and the diameter of subdomains $H$, $\delta$ is the overlapping size among the subdomains, and $c\rightarrow 1$ decreasingly as $H\rightarrow 0$. Moreover, the method does not need any assumption between $H$ and $h$. Numerical results supporting our theory are given.

References

I. Babuška and J. E. Osborn, Finite element-Galerkin approximation of the eigenvalues and eigenvectors of selfadjoint problems, Math. Comp. 52 (1989), no. 186, 275–297. MR 962210, DOI 10.1090/S0025-5718-1989-0962210-8
I. Babuška and J. Osborn, Eigenvalue problems, Handbook of numerical analysis, Vol. II, Handb. Numer. Anal., II, North-Holland, Amsterdam, 1991, pp. 641–787. MR 1115240
P. E. Bjørstad and B. P. Tjøstheim, High precision solutions of two fourth order eigenvalue problems, Computing 63 (1999), no. 2, 97–107. MR 1736662, DOI 10.1007/s006070050053
H. Blum and R. Rannacher, On the boundary value problem of the biharmonic operator on domains with angular corners, Math. Methods Appl. Sci. 2 (1980), no. 4, 556–581. MR 595625, DOI 10.1002/mma.1670020416
James H. Bramble, Multigrid methods, Pitman Research Notes in Mathematics Series, vol. 294, Longman Scientific & Technical, Harlow; copublished in the United States with John Wiley & Sons, Inc., New York, 1993. MR 1247694
Susanne C. Brenner, A two-level additive Schwarz preconditioner for nonconforming plate elements, Numer. Math. 72 (1996), no. 4, 419–447. MR 1376107, DOI 10.1007/s002110050176
Xiao-Chuan Cai and Marcus Sarkis, A restricted additive Schwarz preconditioner for general sparse linear systems, SIAM J. Sci. Comput. 21 (1999), no. 2, 792–797. MR 1718707, DOI 10.1137/S106482759732678X
Zhiqiang Cai, Jan Mandel, and Steve McCormick, Multigrid methods for nearly singular linear equations and eigenvalue problems, SIAM J. Numer. Anal. 34 (1997), no. 1, 178–200. MR 1445734, DOI 10.1137/S1064827594261139
Tony F. Chan and Ilya Sharapov, Subspace correction multi-level methods for elliptic eigenvalue problems, Numer. Linear Algebra Appl. 9 (2002), no. 1, 1–20. MR 1874780, DOI 10.1002/nla.238
Françoise Chatelin, Spectral approximation of linear operators, Classics in Applied Mathematics, vol. 65, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2011. With a foreword by P. Henrici; With solutions to exercises by Mario Ahués; Reprint of the 1983 original [ MR0716134]. MR 3405533, DOI 10.1137/1.9781611970678.ch1
E. D’yakonov and A. Knyazev, Group iterative method for finding low-order eigenvalues, Moscow Univ. Comput. Math. Cybern. (1982), no. 2, 32–40.
Lawrence C. Evans, Partial differential equations, Graduate Studies in Mathematics, vol. 19, American Mathematical Society, Providence, RI, 1998. MR 1625845, DOI 10.1090/gsm/019
Gerard L. G. Sleijpen and Henk A. Van der Vorst, A Jacobi-Davidson iteration method for linear eigenvalue problems, SIAM Rev. 42 (2000), no. 2, 267–293. MR 1778354, DOI 10.1137/S0036144599363084
Wolfgang Hackbusch, Multigrid methods and applications, Springer Series in Computational Mathematics, vol. 4, Springer-Verlag, Berlin, 1985. MR 814495, DOI 10.1007/978-3-662-02427-0
Jun Hu and Zhong-Ci Shi, The best $L^2$ norm error estimate of lower order finite element methods for the fourth order problem, J. Comput. Math. 30 (2012), no. 5, 449–460. MR 2988473, DOI 10.4208/jcm.1203-m3855
Feng-Nan Hwang, Zih-Hao Wei, Tsung-Ming Huang, and Weichung Wang, A parallel additive Schwarz preconditioned Jacobi-Davidson algorithm for polynomial eigenvalue problems in quantum dot simulation, J. Comput. Phys. 229 (2010), no. 8, 2932–2947. MR 2595802, DOI 10.1016/j.jcp.2009.12.024
Andrew V. Knyazev, Preconditioned eigensolvers—an oxymoron?, Electron. Trans. Numer. Anal. 7 (1998), 104–123. Large scale eigenvalue problems (Argonne, IL, 1997). MR 1667642
S. H. Lui, Domain decomposition methods for eigenvalue problems, J. Comput. Appl. Math. 117 (2000), no. 1, 17–34. MR 1752860, DOI 10.1016/S0377-0427(99)00326-X
S. Yu. Maliassov, On the Schwarz alternating method for eigenvalue problems, Russian J. Numer. Anal. Math. Modelling 13 (1998), no. 1, 45–56. MR 1611642, DOI 10.1515/rnam.1998.13.1.45
Stephen F. McCormick, Multilevel projection methods for partial differential equations, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 62, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992. MR 1146209, DOI 10.1137/1.9781611970098
Beresford N. Parlett, The symmetric eigenvalue problem, Prentice-Hall Series in Computational Mathematics, Prentice-Hall, Inc., Englewood Cliffs, NJ, 1980. MR 570116
Xue-Cheng Tai and Magne Espedal, Applications of a space decomposition method to linear and nonlinear elliptic problems, Numer. Methods Partial Differential Equations 14 (1998), no. 6, 717–737. MR 1653334, DOI 10.1002/(SICI)1098-2426(199811)14:6<717::AID-NUM2>3.3.CO;2-B
Xue-Cheng Tai and Magne Espedal, Rate of convergence of some space decomposition methods for linear and nonlinear problems, SIAM J. Numer. Anal. 35 (1998), no. 4, 1558–1570. MR 1626026, DOI 10.1137/S0036142996297461
Andrea Toselli and Olof Widlund, Domain decomposition methods—algorithms and theory, Springer Series in Computational Mathematics, vol. 34, Springer-Verlag, Berlin, 2005. MR 2104179, DOI 10.1007/b137868
Wei Wang and Xuejun Xu, A two-level overlapping hybrid domain decomposition method for eigenvalue problems, SIAM J. Numer. Anal. 56 (2018), no. 1, 344–368. MR 3749389, DOI 10.1137/16M1088302
C. Wieners, Bounds for the $N$ lowest eigenvalues of fourth-order boundary value problems, Computing 59 (1997), no. 1, 29–41. MR 1465309, DOI 10.1007/BF02684402
J. H. Wilkinson, Inverse iteration in theory and in practice, Symposia Mathematica, Vol. X (Convegno di Geometria Differenziale, INDAM, Rome, 1971 & Convegno di Analisi Numerica, INDAM, Rome, 1972) Academic Press, London-New York, 1972, pp. 361–379. MR 366017
Jinchao Xu and Aihui Zhou, A two-grid discretization scheme for eigenvalue problems, Math. Comp. 70 (2001), no. 233, 17–25. MR 1677419, DOI 10.1090/S0025-5718-99-01180-1
Yidu Yang and Hai Bi, Two-grid finite element discretization schemes based on shifted-inverse power method for elliptic eigenvalue problems, SIAM J. Numer. Anal. 49 (2011), no. 4, 1602–1624. MR 2831063, DOI 10.1137/100810241
Xuejun Zhang, Studies in domain decomposition: Multilevel methods and the biharmonic Dirichlet problem, ProQuest LLC, Ann Arbor, MI, 1991. Thesis (Ph.D.)–New York University. MR 2687221
Tao Zhao, Feng-Nan Hwang, and Xiao-Chuan Cai, Parallel two-level domain decomposition based Jacobi-Davidson algorithms for pyramidal quantum dot simulation, Comput. Phys. Commun. 204 (2016), 74–81. MR 3499456, DOI 10.1016/j.cpc.2016.03.009