A multigrid method for eigenvalue problem☆
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 , and , mean that , and for some constants and 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 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 (defined in Section 3) and the finite element space have the following relation of approximation accuracy holds where the constant 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 . Then we have Theorem 5.1 Assume the eigenvalue problem solved in the coarse spaces and need work and , 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 on the unit square and unit cube .
From the error estimate of the finite element methods (cf. [8], [14]) and the definitions (2.7) and (2.16), and has the following estimates 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)
- et al.
Eigenvalue problems
- et al.
The analysis of multigrid methods
- et al.
Finite element approximations of nonlinear eigenvalue problems in quantum physics
Comput. Methods Appl. Mech. Eng.
(2011) - et al.
Finite element – Galerkin approximation of the eigenvalues and eigenvectors of selfadjoint problems
Math. Comput.
(1989) - et al.
An optimal order process for solving finite element equations
Math. Comput.
(1981) Multigrid Methods
(1993)- et al.
New convergence estimates for multigrid algorithms
Math. Comput.
(1987) - et al.
Multigrid methods for differential eigenproblems
SIAM J. Sci. Stat. Comput.
(1983) - et al.
The Mathematical Theory of Finite Element Methods
(1994) - et al.
Subspace correction multi-level methods for elliptic eigenvalue problems
Numer. Linear Algebra Appl.
(2002)