Multigrid Method for Nonlinear Eigenvalue Problems Based on Newton Iteration | Journal of Scientific Computing Skip to main content
Springer Nature Link
Log in

Multigrid Method for Nonlinear Eigenvalue Problems Based on Newton Iteration

  • Published:
Journal of Scientific Computing Aims and scope Submit manuscript

Abstract

In this paper, a novel multigrid method based on Newton iteration is proposed to solve nonlinear eigenvalue problems. Instead of handling the eigenvalue \(\lambda \) and eigenfunction u separately, we treat the eigenpair \((\lambda , u)\) as one element in a product space \({\mathbb {R}} \times H_0^1(\Omega )\). Then in the presented multigrid method, only one discrete linear boundary value problem needs to be solved for each level of the multigrid sequence. Because we avoid solving large-scale nonlinear eigenvalue problems directly, the overall efficiency is significantly improved. The optimal error estimate and linear computational complexity can be derived simultaneously. In addition, we also provide an improved multigrid method coupled with a mixing scheme to further guarantee the convergence and stability of the iteration scheme. More importantly, we prove convergence for the residuals after each iteration step. For nonlinear eigenvalue problems, such theoretical analysis is missing from the existing literatures on the mixing iteration scheme.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

References

  1. Adams, R.A.: Sobolev Spaces. Academic Press, New York (1975)

    MATH  Google Scholar 

  2. Anderson, D.G.: Iterative procedures for nonlinear integral equations. J. Assoc. Comput. Mach. 12, 547–560 (1965)

  3. Bao, G., Hu, G., Liu, D.: An h-adaptive finite element solver for the calculations of the electronic structures. J. Comput. Phys. 231(14), 4967–4979 (2012)

    Article  MATH  Google Scholar 

  4. Bao, W., Du, Q.: Computing the ground state solution of Bose–Einstein condensates by a normalized gradient flow. SIAM J. Sci. Comput. 25, 1674–1697 (2004)

    Article  MATH  Google Scholar 

  5. Benzi, M., Golub, G.H., Liesen, J.: Numerical solution of saddle point problems. Acta Numer 14, 1–137 (2005)

    Article  MATH  Google Scholar 

  6. Brandt, A.: Multi-level adaptive solutions to boundary-value problems. Math. Comput. 31, 333–390 (1977)

    Article  MATH  Google Scholar 

  7. Brezzi, F., Fortin, F.: Mixed and Hybrid Finite Element Methods. Springer, New York (1991)

    Book  MATH  Google Scholar 

  8. Brenner, S., Scott, L.: The Mathematical Theory of Finite Element Methods. Springer, New York (1994)

    Book  MATH  Google Scholar 

  9. Cai, Y., Zhang, L., Bai, Z., Li, R.: On an eigenvector-dependent nonlinear eigenvalue problem. SIAM J. Matrix Anal. Appl. 39(3), 1360–1382 (2018)

    Article  MATH  Google Scholar 

  10. Cancès, E., Chakir, R., Maday, Y.: Numerical analysis of nonlinear eigenvalue problems. J. Sci. Comput. 45(1–3), 90–117 (2010)

    Article  MATH  Google Scholar 

  11. Cancès, E., Chakir, R., Maday, Y.: Numerical analysis of the planewave discretization of some orbital-free and Kohn-Sham models. ESAIM Math. Model. Numer. Anal. 46, 341–388 (2012)

    Article  MATH  Google Scholar 

  12. Chen, H., He, L., Zhou, A.: Finite element approximations of nonlinear eigenvalue problems in quantum physics. Comput. Methods Appl. Mech. Engrg. 200(21), 1846–1865 (2011)

    Article  MATH  Google Scholar 

  13. Chen, H., Liu, F., Zhou, A.: A two-scale higher-order finite element discretization for Schrödinger equation. J. Comput. Math. 27, 315–337 (2009)

    MATH  Google Scholar 

  14. Chen, H., Xie, H., Xu, F.: A full multigrid method for eigenvalue problems. J. Comput. Phys. 322, 747–759 (2016)

    Article  MATH  Google Scholar 

  15. Ciarlet, P.G., Lions, J.L. (eds.): Finite Element Methods, Handbook of Numerical Analysis, vol. II. North Holland, Amsterdam (1991)

    Google Scholar 

  16. Fang, H., Saad, Y.: Two classes of multisecant methods for nonlinear acceleration. Numer. Linear Algebra Appl. 16(3), 197–221 (2009)

    Article  MATH  Google Scholar 

  17. Fedorenko, R.P.: A relaxation method for solving elliptic difference equations. USSR Comput. Math. Math. Phys. 1(4), 1092–1096 (1961)

    Article  MATH  Google Scholar 

  18. Hackbusch, W.: Multi-grid Methods and Applications. Springer, Berlin (1985)

    Book  MATH  Google Scholar 

  19. Harrison, R., Moroz, I., Tod, K.P.: A numerical study of the Schrödinger–Newton equations. Nonlinearity 16, 101–122 (2003)

    Article  MATH  Google Scholar 

  20. Hu, G., Xie, H., Xu, F.: A multilevel correction adaptive finite element method for Kohn–Sham equation. J. Comput. Phys. 355, 436–449 (2018)

    Article  MATH  Google Scholar 

  21. Jia, S., Xie, H., Xie, M., Xu, F.: A full multigrid method for nonlinear eigenvalue problems. Sci China Math 59, 2037–2048 (2016)

    Article  MATH  Google Scholar 

  22. Kohn, W., Sham, L.: Self-consistent equations including exchange and correlation effects. Phys. Rev. A 140, 1133–1138 (1965)

    Article  Google Scholar 

  23. Lieb, E.H.: Thomas-Fermi and related theories of atoms and molecules. Rev. Mod. Phys. 53, 603–641 (1981)

    Article  MATH  Google Scholar 

  24. Lin, L., Yang, C.: Elliptic preconditioner for accelerating the self-consistent field iteration in Kohn-Sham density functional theory. SIAM J. Sci. Comput. 35(5), S277–S298 (2013)

    Article  MATH  Google Scholar 

  25. Lott, P.A., Walker, H.F., Woodward, C.S., Yang, U.M.: An accelerated Picard method for nonlinear systems related to variably saturated flow. Adv. Water Resour. 38, 92–101 (2012)

    Article  Google Scholar 

  26. Motamarri, P., Iyer, M., Knap, J., Gavini, V.: Higher-order adaptive finite-element methods for orbital-free density functional theory. J. Comput. Phys. 231, 6596–6621 (2012)

    Article  MATH  Google Scholar 

  27. Pollock, S., Rebholz, L., Xiao, M.: Anderson-accelerated convergence of picard iterations for incompressible Navier-Stokes equations. SIAM J. Numer. Anal. 57(2), 615–637 (2019)

    Article  MATH  Google Scholar 

  28. Stasiak, P., Matsen, M.W.: Efficiency of pseudo-spectral algorithms with anderson mixing for the SCFT of periodic block-copolymer phases. Eur. Phys. J. E 34(110), 1–9 (2011)

    Google Scholar 

  29. Shaidurov, V.V.: Multigrid Methods for Finite Element. Kluwer Academic Publics, Netherlands (1995)

    Book  MATH  Google Scholar 

  30. Toth, A., Kelley, C.T.: Convergence analysis for Anderson acceleration. SIAM J. Numer. Anal. 53(2), 805–819 (2015)

    Article  MATH  Google Scholar 

  31. Xu, J.: Iterative methods by space decomposition and subspace correction. SIAM Rev. 34, 581–613 (1992)

    Article  MATH  Google Scholar 

  32. Xu, J., Zhou, A.: A two-grid discretization scheme for eigenvalue problems. Math. Comp. 70, 17–25 (2001)

    Article  MATH  Google Scholar 

  33. Yserentant, H.: On the regularity of the electronic Schrödinger equation in Hilbert spaces of mixed derivatives. Numer. Math. 98(4), 731–759 (2004)

    Article  MATH  Google Scholar 

  34. Zhou, A.: An analysis of finite-dimensional approximations for the ground state solution of Bose-Einstein condensates. Nonlinearity 17, 541–550 (2004)

    Article  MATH  Google Scholar 

  35. Zhou, A.: Finite dimensional approximations for the electronic ground state solution of a molecular system. Math. Methods Appl. Sci. 30, 429–447 (2007)

    Article  MATH  Google Scholar 

Download references

Funding

The first author (F. Xu) was supported in part by General projects of science and technology plan of Beijing Municipal Education Commission (Grant No. KM202110005011), National Natural Science Foundation of China (Grant No. 11801021). The second author (M. Xie) was supported in part by the National Natural Science Foundation of China (Nos. 12001402, 12271400) and Natural Science Foundation of Tianjin (20JCQNJC01440). The third author (M. Yue) was supported in part by the National Natural Science Foundation of China (No. 12201017).

Author information

Authors and Affiliations

  1. Institute of Computational Mathematics, Department of Mathematics, Faculty of Science, Beijing University of Technology, Beijing, 100124, China

    Fei Xu

  2. Center for Applied Mathematics, Tianjin University, Tianjin, 300072, China

    Manting Xie

  3. School of Mathematics and Statistics, Beijing Technology and Business University, Beijing, 100048, China

    Meiling Yue

Authors
  1. Fei Xu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Manting Xie
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Meiling Yue
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Fei Xu.

Ethics declarations

Conflict of interest

The authors declare that they have no conflicts of interest/competing interests.

Code availability

The custom codes generated during the current study are available from the corresponding author on reasonable request.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Xu, F., Xie, M. & Yue, M. Multigrid Method for Nonlinear Eigenvalue Problems Based on Newton Iteration. J Sci Comput 94, 42 (2023). https://doi.org/10.1007/s10915-022-02070-9

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s10915-022-02070-9

Keywords

Search

Navigation