## 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
**HTML**| PDF - Math. Comp.
**88**(2019), 2295-2324 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** - 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, N.J., 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 Analisi Numerica, INDAM, Rome, 1972) Academic Press, London, 1972, pp. 361–379. MR**0366017** - 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

## Additional Information

**Wei Wang**- Affiliation: Beijing Computational Science Research Center, Beijing 100193, People’s Republic of China; and LSEC, Institute of Computational Mathematics, Academy of Mathematics and System Sciences, Chinese Academy of Sciences, P.O. Box 2719, Beijing 100190, People’s Republic of China
- Email: ww@csrc.ac.cn
**Xuejun Xu**- Affiliation: School of Mathematical Sciences, Tongji University, Shanghai 200442, People’s Republic of China; and LSEC, Institute of Computational Mathematics, Academy of Mathematics and System Sciences, Chinese Academy of Sciences, P.O. Box 2719, Beijing 100190, People’s Republic of China
- MR Author ID: 365400
- Email: xxj@lsec.cc.ac.cn
- Received by editor(s): May 8, 2018
- Received by editor(s) in revised form: August 25, 2018, and September 5, 2018
- Published electronically: December 20, 2018
- Additional Notes: The work of the first author was supported by the National Natural Science Foundation of China (Grant No. U1530401).

The work of the second author was supported by the National Natural Science Foundation of China (Grant No. 11671302). - © Copyright 2018 American Mathematical Society
- Journal: Math. Comp.
**88**(2019), 2295-2324 - MSC (2010): Primary 65N30, 65N55
- DOI: https://doi.org/10.1090/mcom/3403
- MathSciNet review: 3957894