Elsevier

Journal of Computational Physics

Volume 274, 1 October 2014, Pages 550-561
Journal of Computational Physics

A multigrid method for eigenvalue problem

https://doi.org/10.1016/j.jcp.2014.06.030Get rights and content

Abstract

A multigrid method is proposed to solve the eigenvalue problem by the finite element method based on the combination of the multilevel correction scheme for the eigenvalue problem and the multigrid method for the boundary value problem. In this scheme, solving eigenvalue problem is transformed to a series of solutions of boundary value problems by the multigrid method on multilevel meshes and a series of solutions of eigenvalue problems on the coarsest finite element space. Besides the multigrid scheme, all other efficient iteration methods can also serve as the linear algebraic solver for the associated boundary value problems. The total computational work of this scheme can reach the optimal order as same as solving the corresponding boundary value problem. Therefore, this type of iteration scheme improves the overall efficiency of the eigenvalue problem solving. Some numerical experiments are presented to validate the efficiency of the method.

Introduction

Solving large scale eigenvalue problems becomes a fundamental problem in modern science and engineering society. However, it is always a very difficult task to solve high-dimensional eigenvalue problems which come from physical and chemical sciences. For example, it is usually required to solve Kohn–Sham equations in modern electronic structure computations since the Kohn–Sham equation is an important model in modern physics, quantum chemistry and materials science [11], [12], [13], [18], [21], [23], [26]. The main part for solving the Kohn–Sham equation is solving linear eigenvalue problems repeatedly. Always many eigenpairs are desired and the self-consistent field iteration is not so easy to converge and it often takes several tens of steps in the worst situations. Consequently, how to improve the accuracy and reduce the computational cost in solving linear eigenvalue problems at each iteration step is very important for solving Kohn–Sham equations. Thus, the highly efficient linear eigenvalue computation scheme has the essential benefits for simulating large systems (see, e.g., [11], [12], [13] and the references cited therein). Although many efficient algorithms, such as multigrid method and many other precondition techniques [8], [28] for solving boundary value problems, have been developed, there is few efficient numerical method to solve eigenvalue problems with optimal computation work [7], [9], [15], [16], [25].

The multigrid method and other efficient preconditioners provide an optimal order algorithm for solving boundary value problems. The error bounds of the approximate solution obtained from these efficient numerical algorithms are comparable to the theoretical bounds determined by the finite element discretization. But the amount of computational work involved is only proportional to the number of unknowns in the discretized equations. For more details of the multigrid and multilevel methods, please read the papers: Bank and Dupont [3], Bramble and Pasciak [5], Bramble and Zhang [6], Xu [28], Scott and Zhang [24] and books: Brenner and Scott [8], Hackbusch [16], McCormick [22], Bramble [4] and the references cited therein.

About the solution of eigenvalue problems, [7], [15], [16], [25], [33] and the references cited therein give some types of multigrid schemes which couples the multigrid iteration and the algebraic eigenvalue problem solving. The convergence and complexity analysis are also provided (see, e.g., [25]). These methods are always designed based on the inverse power or Rayleigh quotient iterations for the eigenvalue problem and the choice of the eigenvalue problem solving method is required to be coupled with the boundary value problem solving and is not free. Always, the singular linear problems are needed to be solved in these iterations. These disadvantages leads to the restriction of their application and make the convergence and complexity analysis become complicated. Under some assumptions, [9] propose another type of subspace correction multi-level method to find the smallest several eigenvalues and the corresponding eigenfunctions of the elliptic eigenvalue problem based on the optimization method. The convergence analysis has been given only for the smallest eigenvalue case under some assumptions. In another way, [31] introduce a type of two-grid discretization method to improve the efficiency of the eigenvalue problem solving. By the two-grid method, the solution of the eigenvalue problem on a fine mesh is reduced to a solution of the eigenvalue problem on a coarse mesh and a solution of the corresponding boundary value problem on the fine mesh [17], [32], [33], [35]. This idea of the two-grid method comes from its applications in nonsymmetric or indefinite problems [29] and nonlinear elliptic equations [30]. So far, there exist many works based on this type of two-grid correction method. Recently, we propose a new type of multilevel correction method to solve eigenvalue problems which can be implemented on multilevel grids [19]. In the multilevel correction scheme, the solution of eigenvalue problem on a fine mesh can be reduced to a series of solutions of the eigenvalue problem on a very coarse mesh and a series of solutions of the boundary value problems on the multilevel meshes. The multilevel correction method gives a way to construct a type of multigrid scheme for the eigenvalue problem which is the topic of the present paper.

The aim of this paper is to present a new type of multigrid scheme which can obtain both simple and multiple eigenvalues of the eigenvalue problems based on the combination of the multilevel correction method [19] and the multigrid method for boundary value problems. In this scheme, solving eigenvalue problem will not be more difficult than the solution of the corresponding boundary value problem and a series of solutions of eigenvalue problems on the coarsest finite element space. The multigrid method for the eigenvalue problem is based on a series of finite element spaces with different levels of accuracy which can be built with the same way as the multilevel method for boundary value problems [28]. It is worth to pointing out that, besides the multigrid method, other types of numerical algorithms such as BPX multilevel [28] and hierarchical preconditioners [34], algebraic multigrid method and domain decomposition preconditioners [8] can also been adopted as the linear algebraic solvers for the multigrid method of the eigenvalue problem. So far, the fundamental theory for eigenvalue problems by the standard Galerkin finite element method has been extensively investigated, e.g. Babuška and Osborn [1], [2], Chatelin [10] and references cited therein. For the analysis in this paper, we will adopt some basic results in these books and papers. The corresponding error and computational work estimates of the proposed multigrid scheme for the eigenvalue problem will be analyzed. Based on the analysis, the new method can arrive the optimal efficiency.

An outline of the paper goes as follows. In Section 2, the finite element method for the eigenvalue problem is introduced and the corresponding basic error estimates are also given. A type of one correction step is presented in Section 3. In Section 4, we propose a type of multigrid algorithm to solve the eigenvalue problem by the finite element method. The estimate of the computational work for the eigenvalue multigrid method is given in Section 5. In Section 6, two numerical examples are presented to validate our theoretical analysis. Some concluding remarks are given in the last section.

Section snippets

Discretization by finite element method

This section is devoted to introducing some notation and error estimates of the finite element approximation for the eigenvalue problem. Through this paper, the letters C and c (with or without subscripts) denote generic positive constants which may be different at its different occurrences. In order to simplify the notation, we will use the symbols ≲, ≳ and ≈ in this paper. That x1y1, x2y2 and x3y3, mean that x1C1y1, x2c2y2 and c3x3y3C3x3 for some constants C1,c2,c3 and C3 that are

One correction step with multigrid method

In this section, we introduce a type of one correction step to improve the accuracy of the given eigenvalue and eigenfunction approximations. This correction method consist of solving some auxiliary source problems in the finer finite element space and an eigenvalue problem on a coarse finite element space. For more discussion about the one correction step, please refer to [19].

In order to do multigrid scheme, we first generate a coarse mesh TH with the mesh size H and the coarse linear finite

Multigrid scheme for the eigenvalue problem

In this section, we introduce a multigrid scheme based on Algorithm 3.1. This type of multigrid method can obtain the optimal accuracy as same as solving the eigenvalue problem directly in the finest finite element space.

First, the sequence of finite element spaces Vh1Vh2Vhn (defined in Section 3) and the finite element space VH have the following relation of approximation accuracy holdsδhk+1(λi)1βδhk(λi),δhk(λi)C6βδhk+1(λi),k=1,,n1, where the constant C6 is independent of k and n.

Remark 4.1

The

Computational work estimate of eigenvalue multigrid scheme

In this section, we turn our attention to the estimate of computational work for Algorithm 4.1. We will show that Algorithm 4.1 makes solving the eigenvalue problem need almost the same work as solving the corresponding boundary value problem.

First, we define the dimension of each level linear finite element space as Nk:=dimVhk. Then we haveNk(1β)d(nk)Nn,k=1,2,,n.

Theorem 5.1

Assume the eigenvalue problem solved in the coarse spaces VH and Vh1 need work O(MH) and O(Mh1), respectively, and the work of

Numerical results

In this section, two numerical examples are presented to illustrate the efficiency of the multigrid scheme proposed in this paper. We solve the model eigenvalue problem{Δu=λu,in Ω,u=0,on Ω,Ωu2dΩ=1, on the unit square Ω=(0,1)×(0,1) and unit cube Ω=(0,1)×(0,1)×(0,1).

From the error estimate of the finite element methods (cf. [8], [14]) and the definitions (2.7) and (2.16), ηa(H) and δhn(λi) has the following estimatesηa(H)H,δhn(λi)hn. Then Theorem 4.1 tells us the following error estimates

Concluding remarks

In this paper, we give a type of multigrid scheme to solve the eigenvalue problems. The idea here is to use the multilevel correction method to transform the solution of the eigenvalue problem to a series of solutions of the corresponding boundary value problems which can be solved by the multigrid method and a series of solutions of eigenvalue problems on the coarsest finite element space.

We can replace the multigrid method by other types of efficient iteration schemes such as algebraic

Acknowledgements

We would like to show our thanks for the reviewers here. Their suggestions make the paper more clearly.

References (35)

  • I. Babuška et al.

    Eigenvalue problems

  • J.H. Bramble et al.

    The analysis of multigrid methods

  • H. Chen et al.

    Finite element approximations of nonlinear eigenvalue problems in quantum physics

    Comput. Methods Appl. Mech. Eng.

    (2011)
  • I. Babuška et al.

    Finite element – Galerkin approximation of the eigenvalues and eigenvectors of selfadjoint problems

    Math. Comput.

    (1989)
  • R.E. Bank et al.

    An optimal order process for solving finite element equations

    Math. Comput.

    (1981)
  • J.H. Bramble

    Multigrid Methods

    (1993)
  • J.H. Bramble et al.

    New convergence estimates for multigrid algorithms

    Math. Comput.

    (1987)
  • A. Brandt et al.

    Multigrid methods for differential eigenproblems

    SIAM J. Sci. Stat. Comput.

    (1983)
  • S. Brenner et al.

    The Mathematical Theory of Finite Element Methods

    (1994)
  • T.F. Chan et al.

    Subspace correction multi-level methods for elliptic eigenvalue problems

    Numer. Linear Algebra Appl.

    (2002)
  • F. Chatelin

    Spectral Approximation of Linear Operators

    (1983)
  • H. Chen et al.

    Numerical analysis of finite dimensional approximations of Kohn–Sham models

    Adv. Comput. Math.

    (2013)
  • H. Chen et al.

    Numerical approximations of a nonlinear eigenvalue problem and applications to a density functional model

    Math. Methods Appl. Sci.

    (2010)
  • P.G. Ciarlet

    The Finite Element Method for Elliptic Problems

    (1978)
  • W. Hackbusch

    On the computation of approximate eigenvalues and eigenfunctions of elliptic operators by means of a multi-grid method

    SIAM J. Numer. Anal.

    (1979)
  • W. Hackbusch

    Multi-grid Methods and Applications

    (1985)
  • X. Hu et al.

    Acceleration of a two-grid method for eigenvalue problems

    Math. Comput.

    (2011)
  • Cited by (0)

    This work is supported in part by the National Science Foundation of China (NSFC 91330202, 11371026, 11001259, 11031006, 2011CB309703), the National Center for Mathematics and Interdisciplinary Science, CAS and the President Foundation of AMSS-CAS.

    View full text