A Full Multigrid Method for Eigenvalue Problems\footnote{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.
Hehu Xie\footnote{LSEC
NCMIS
Institute of Computational Mathematics
Academy of Mathematics and Systems Science
Chinese Academy of Sciences
Beijing 100190
China(hhxie@lsec.cc.ac.cn)
In this paper, a full (nested) multigrid scheme is proposed to solve eigenvalue problems. The idea here is to use the multilevel correction method to transform the solution of eigenvalue problem to a series of solutions of the corresponding boundary value problems and eigenvalue problems defined on the coarsest finite element space. The boundary value problems which are define on a sequence of multilevel finite element space can be solved by some multigrid iteration steps. Besides the multigrid iteration, all other efficient iteration methods for solving boundary value problems can serve as linear problem solver. The computational work of this new scheme can reach optimal order the same as solving the corresponding source problem. Therefore, this type of iteration scheme improves the efficiency of eigenvalue problem solving. %Some numerical experiments are presented to validate the efficiency of the new method. \vskip0.3cm {Keywords. Eigenvalue problem, full multigrid method, multilevel correction, finite element method. \vskip0.2cm {AMS subject classifications. 65N30, 65N25, 65L15, 65B99.
True_Multigrid.tex
\documentclass[12pt,a4paper]{article}
\usepackage{mathrsfs}
\usepackage{epsfig, graphicx}
\usepackage{latexsym,amsfonts,amsbsy,amssymb}
\usepackage{amsmath,amsthm}
%\usepackage[russian]{babel}
 \textwidth=15cm \textheight=22cm \topmargin 0 cm
\oddsidemargin 0in
 \evensidemargin 0in \baselineskip= 12pt
\parindent=12pt
\parskip=3pt
\overfullrule=0pt
\bibliographystyle{plain}
\makeatletter % '@' is now a normal "letter" for TeX
%\renewcommand{\baselinestretch}{2}
\renewcommand\theequation{\thesection.\arabic{equation}}
\@addtoreset{equation}{section}
\makeatother % '@' is restored as a "non-letter" character for TeX
%\renewcommand\theequation{\arabic{section}.\arabic{equation}}
\allowdisplaybreaks % For long formula


\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}{Lemma}[section]
\newtheorem{corollary}{Corollary}[section]
\newtheorem{remark}{Remark}[section]
\newtheorem{algorithm}{Algorithm}[section]
\newtheorem{definition}{Definition}[section]
\newtheorem{proposition}{Proposition}[section]

%--------------------------------------------------------------------------------
\begin{document}
\title{A Full Multigrid Method for Eigenvalue Problems\footnote{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.}}
\author{Hehu Xie\footnote{LSEC, NCMIS, Institute
of Computational Mathematics, Academy of Mathematics and Systems
Science, Chinese Academy of Sciences, Beijing 100190,
China(hhxie@lsec.cc.ac.cn)} }
\date{}
\maketitle
\begin{abstract}
In this paper, a full (nested) multigrid scheme is proposed
to solve eigenvalue problems. The idea here is to use the multilevel correction method
to transform the solution of eigenvalue problem to a series of solutions of the corresponding
boundary value problems and eigenvalue problems defined on the coarsest finite element space.
The boundary value problems which are define on a sequence of multilevel finite element space
can be solved by some multigrid iteration steps.
Besides the multigrid iteration, all other efficient iteration methods for solving boundary value
problems can serve as linear problem solver. The computational work of this new scheme can reach
optimal order the same as solving the corresponding source problem.
Therefore, this type of iteration scheme improves the efficiency of eigenvalue problem solving.
%Some numerical experiments are presented to validate the efficiency of the new method.

\vskip0.3cm {\bf Keywords.} Eigenvalue problem, full multigrid method, multilevel correction,
finite element method.

\vskip0.2cm {\bf AMS subject classifications.} 65N30, 65N25, 65L15,
65B99.
\end{abstract}

%-----------------------------------------------------------------------------------------
\section{Introduction}

It is well known there have existed many efficient algorithms, such as multigrid method
 and many other precondition techniques \cite{BrennerScott,Shaidurov,Xu},
 for solving boundary value problems. %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 refer to \cite{BankDupont,Bramble,BramblePasciak,BrambleZhang,BrennerScott,
Hackbusch,Hackbusch_Book,McCormick,ScottZhang,Shaidurov,Xu,Xu_Two_Grid} and the references cited therein.

But there is no many efficient numerical methods for solving eigenvalue problems with optimal
complexity. Solving large scale eigenvalue problems is one of  fundamental problems 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 chemistry sciences.
Recently, a type of multilevel correction method is proposed for solving
eigenvalue problems in \cite{LinXie_MultiLevel,Xie_IMA,Xie_JCP}. In this multilevel
correction scheme, the solution of eigenvalue problem on the final level
mesh can be reduced to a series of solutions of boundary value problems on
the multilevel meshes and a series of solutions of the eigenvalue problem
 on the coarsest mesh. The multilevel correction method gives a way to construct
the multigrid method for eigenvalue problems \cite{Xie_IMA,Xie_JCP}.


The aim of this paper is to present a full multigrid method
for solving eigenvalue problems based on the combination of the multilevel correction
method \cite{Xie_IMA,Xie_JCP} and the multigrid iteration for
boundary value problems. Comparing with the method in \cite{LinXie_MultiLevel,Xie_IMA,Xie_JCP},
the difference is that we do not solve the linear boundary value problem
exactly in each correction step with the multigrid method. We only
get an approximate solution with some multigrid iteration steps. In this new version of
multigrid method,  solving eigenvalue
problem will not be much more difficult than the multigrid scheme for the
corresponding boundary value problems.
%The multigrid method for eigenvalue
%problem is based on a series of finite element spaces with different
%approximation properties which can be built with the same way as the
%multilevel method (cf. \cite{Xu}).
It is worth to noting that besides the multigrid method here,
other types of numerical algorithms such as BPX multilevel preconditioners \cite{Xu},
algebraic multigrid method and domain decomposition
preconditioners (cf. \cite{BrennerScott,ToselliWidlund})
can also act as the linear algebraic solvers for boundary value problems.

%The full eigenvalue multigrid procedure can be described as follows: (1)\
%solve the eigenvalue problem in the coarsest finite element space;
%(2)\ construct an linear boundary value problem with the previous
%obtained eigenvalue multiplying the corresponding
%eigenfunction as the load vector and then do some
%multigrid iteration steps for this linear equation
%to get a new eigenfunction approximation; (3)\ solve eigenvalue problem
%again on the finite element space which is constructed by combining
%the coarsest finite element space with the obtained eigenfunction
%approximation in step (2). Then go to step (2) for next loop until stop.
%In this method, we replace solving eigenvalue problem on the finest
%finite element space by solving a series of boundary value problems with multigrid scheme
%in the corresponding series of finite element spaces and a series of
%eigenvalue problems in the coarsest finite element space. So this multigrid method
%can improve the efficiency of solving eigenvalue problems as it does
%for boundary value problems.
%The corresponding error and computational work estimates of the type
%of multigrid scheme for eigenvalue problem will be analyzed.
%Based on the analysis, the new method can obtain optimal errors with an optimal
%computational work.


An outline of the paper goes as follows. In Section 2, we introduce the
finite element method for eigenvalue problem and the corresponding basic
error estimates. A type of full multigrid
algorithm for solving eigenvalue problem by finite element method
 is given in Section 3.
Two numerical examples are presented to validate our
theoretical analysis in section 4.
Some concluding remarks are given in the last section.

%======================================================================================
\section{Finite element method for eigenvalue problem}\label{sec;preliminary}
This section is devoted to introducing some notation and the finite element
method for eigenvalue problem. In this paper, we shall use the standard notation
for Sobolev spaces $W^{s,p}(\Omega)$ and their
associated norms and semi-norms (cf. \cite{Adams}). For $p=2$, we denote
$H^s(\Omega)=W^{s,2}(\Omega)$ and
$H_0^1(\Omega)=\{v\in H^1(\Omega):\ v|_{\partial\Omega}=0\}$,
where $v|_{\Omega}=0$ is in the sense of trace,
$\|\cdot\|_{s,\Omega}=\|\cdot\|_{s,2,\Omega}$.
%In some places, $\|\cdot\|_{s,2,\Omega}$ should be viewed as piecewise
%defined if it is necessary.
The letter $C$ (with or without subscripts) denotes a generic
positive constant which may be different at its different occurrences
 through the paper.


For simplicity, we consider the following model problem to illustrate the main idea:
Find $(\lambda, u)$ such that
\begin{equation}\label{LaplaceEigenProblem}
\left\{
\begin{array}{rcl}
-\nabla\cdot(\mathcal{A}\nabla u)+\phi u&=&\lambda u, \quad {\rm in} \  \Omega,\\
u&=&0, \ \  \quad {\rm on}\  \partial\Omega,
\end{array}
\right.
\end{equation}
where $\mathcal{A}$ is a symmetric and positive definite matrix with suitable
regularity, $\phi$ is a nonnegative function,  $\Omega\subset\mathcal{R}^d$ $(d=2,3)$
 is a bounded domain with
Lipschitz boundary $\partial\Omega$ and $\nabla$, $\nabla\cdot$
denote the gradient, divergence operators, respectively.


In order to use the finite element method to solve
the eigenvalue problem (\ref{LaplaceEigenProblem}), we need to define
the corresponding variational form as follows:
Find $(\lambda, u )\in \mathcal{R}\times V$ such that $b(u,u)=1$ and
\begin{eqnarray}\label{weak_eigenvalue_problem}
a(u,v)&=&\lambda b(u,v),\quad \forall v\in V,
\end{eqnarray}
where $V:=H_0^1(\Omega)$ and
\begin{equation}\label{inner_product_a_b}
a(u,v)=\int_{\Omega}\big(\nabla u\cdot\mathcal{A}\nabla v +\phi uv\big)d\Omega,
 \ \ \ \  \ \ b(u,v) = \int_{\Omega}uv d\Omega.
\end{equation}
The norms $\|\cdot\|_a$ and $\|\cdot\|_b$ are defined by
\begin{eqnarray*}
\|v\|_a=a(v,v)^{1/2}\ \ \ \ \ {\rm and}\ \ \ \ \ \|v\|_b=b(v,v)^{1/2}.
\end{eqnarray*}
  It is well known that the eigenvalue problem (\ref{weak_eigenvalue_problem})
  has an eigenvalue sequence $\{\lambda_j \}$ (cf. \cite{BabuskaOsborn_Book,Chatelin}):
$$0<\lambda_1\leq \lambda_2\leq\cdots\leq\lambda_k\leq\cdots,\ \ \
\lim_{k\rightarrow\infty}\lambda_k=\infty,$$ and associated
eigenfunctions
$$u_1, u_2, \cdots, u_k, \cdots,$$
where $b(u_i,u_j)=\delta_{ij}$ ($\delta_{ij}$ denotes the Kronecker function).
In the sequence $\{\lambda_j\}$, the $\lambda_j$ are repeated according to their
geometric multiplicity.

%-----------------------------------------------------------------------------------------
Now, let us define the finite element approximations of the problem
(\ref{weak_eigenvalue_problem}). First we generate a shape-regular
decomposition of the computing domain $\Omega\subset \mathcal{R}^d\
(d=2,3)$ into triangles or rectangles for $d=2$ (tetrahedrons or
hexahedrons for $d=3$) (cf. \cite{BrennerScott,Ciarlet}).
The diameter of a cell $K\in\mathcal{T}_h$ is denoted by $h_K$ and
the mesh size $h$ describes  the maximum diameter of all cells
$K\in\mathcal{T}_h$. Based on the mesh $\mathcal{T}_h$, we can
construct a finite element space denoted by $V_h \subset V$.
For simplicity, we set $V_h$ as the linear finite element space
which is defined as follows
\begin{equation}\label{linear_fe_space}
V_h = \big\{ v_h \in C(\Omega)\ \big|\ v_h|_{K} \in \mathcal{P}_1,
\ \ \forall K \in \mathcal{T}_h\big\},
\end{equation}
where $\mathcal{P}_1$ denotes the linear function space.
%consists of all the polynomials of degree not greater than one.

%���������P_h�Ķ��壬�����δֱ�����ã���ע�͡�
%For the error analysis, it is helpful to introduce the
%finite element projection operator
%$P_h:\ V\rightarrow V_h$ by
%\begin{eqnarray}\label{Projection_Problem}
%a(w-P_hw,v_j)=0,\ \ \ \ \forall v_h\in V_h
%\end{eqnarray}
%and apparently
%\begin{eqnarray}\label{Projection_Inequality}
%\|P_hw\|_{a}\le \|w\|_{a},\ \ \ \forall w\in V.
%\end{eqnarray}
%P_h�Ķ��壬ע�ͽ���



%��ż��֤��Babuska����������ΪҪ�� u_h�� P_hu ���Ƚϡ����ﲻ��Ҫ��
% Then we have the following estimates (see \cite{Babuska1}).
%\begin{lemma}[Duality Argument]\label{Bound_Global_Err_Lem}
%\begin{eqnarray}
%\|(I-P_h)Tf\|_{a}&\lesssim&\eta_{a}(h)\|f\|_{b},\ \ \ \forall f\in L^2(\Omega),\\
%\|u-P_hu\|_{b}&\lesssim&\eta_{a}(h)\|u-P_hu\|_{a},\ \ \ \forall u\in H_0^1(\Omega).
%\end{eqnarray}
%\end{lemma}
%��ż��֤ע�ͽ���

The standard finite element scheme for eigenvalue
 problem (\ref{weak_eigenvalue_problem}) is:
Find $(\bar{\lambda}_h, \bar{u}_h)\in \mathcal{R}\times V_h$
such that $b(\bar{u}_h,\bar{u}_h)=1$ and
\begin{eqnarray}\label{Weak_Eigenvalue_Discrete}
a(\bar{u}_h,v_h)
&=&\bar{\lambda}_h b(\bar{u}_h,v_h),\quad\ \  \ \forall v_h\in V_h.
\end{eqnarray}
From \cite{BabuskaOsborn_1989,BabuskaOsborn_Book,Chatelin}, %we have the following
%Rayleigh quotient expression for $\bar{\lambda}_h$:
%\begin{eqnarray}\label{Rayleigh_Quotient_Discrete}
%\bar{\lambda}_h &=&\frac{a(\bar{u}_h,\bar{u}_h)}{b(\bar{u}_h,\bar{u}_h)},
%\end{eqnarray}
%and
the discrete eigenvalue problem (\ref{Weak_Eigenvalue_Discrete}) has eigenvalues:
$$0<\bar{\lambda}_{1,h}\leq \bar{\lambda}_{2,h}\leq\cdots\leq \bar{\lambda}_{k,h}
\leq\cdots\leq \bar{\lambda}_{N_h,h},$$
and corresponding eigenfunctions
$$\bar{u}_{1,h}, \bar{u}_{2,h},\cdots, \bar{u}_{k,h}, \cdots, \bar{u}_{N_h,h},$$
where $b(\bar{u}_{i,h},\bar{u}_{j,h})=\delta_{ij}, 1\leq i,j\leq N_h$ ($N_h$ is
the dimension of the finite element space $V_h$).


Let $M(\lambda_i)$ denote the eigenspace corresponding to the
eigenvalue $\lambda_i$ which is defined by
\begin{eqnarray}
M(\lambda_i)&=&\big\{w\in H_0^1(\Omega): w\ {\rm is\ an\ eigenvalue\ of\
(\ref{weak_eigenvalue_problem})} \nonumber\\
&&\ \ \ \ \ \ \ \ \ \ \ \ \  {\rm corresponding\ to}\ \lambda_i\  {\rm and}\ b(w,w)=1\big\},
\end{eqnarray}
%{\color{red} %����һ���ú�ɫ��ʾ
%Let $E=E(\lambda_i)$ be the orthogonal projection of $V$ onto $M(\lambda_i)$ and
% let $E_h=E_h(\lambda_i)$ be the orthogonal projection of $V$ onto
%\begin{equation}\label{M_h_def}
%  M_h=M_h(\lambda_i)= \text{\rm the span of the eigenvectors of
%  (\ref{Weak_Eigenvalue_Discrete}) corresponding to}\ \lambda_{i,h}.
%\end{equation}
%}%��ɫ��ʾ����
and define
\begin{eqnarray}
\delta_h(\lambda_i)=\sup_{w\in M(\lambda_i)}\inf_{v_h\in
V_h}\|w-v_h\|_{a}.
\end{eqnarray}

Let us define the following quantity:
\begin{eqnarray}
\eta_{a}(h)&=&\sup_{f\in L^2(\Omega),\|f\|_b=1}\inf_{v_h\in V_h}\|Tf-v_h\|_{a},\label{eta_a_h_Def}
\end{eqnarray}
where $T:L^2(\Omega)\rightarrow V$ is defined as
\begin{equation}\label{laplace_source_operator}
  a(Tf,v) = b(f,v), \ \ \ \ \  \forall f \in L^2(\Omega) \ \ \  {\rm and}\  \ \ \forall v\in V.
\end{equation}
Then the error estimates for the eigenpair approximations by the finite
element method can be described as follows.
\begin{lemma}(\cite[Lemma 3.6, Theorem 4.4]{BabuskaOsborn_1989} and \cite{Chatelin})
\label{Err_Eigen_Global_Lem}
For any eigenpair approximation
$(\bar{\lambda}_{i,h},\bar{u}_{i,h})$ $(i = 1, 2, \cdots, N_h)$ of
(\ref{Weak_Eigenvalue_Discrete}),
 there exists an exact eigenpair  $(\lambda_i, u_i)$ of
(\ref{weak_eigenvalue_problem})
such that $b(u_i, u_i) = 1$ and
\begin{eqnarray}
\|u_i-\bar{u}_{i,h}\|_{a}
&\leq& \big(1+C_i\eta_a(h)\big)\delta_h(\lambda_i),\label{Err_Eigenfunction_Global_1_Norm} \\
\|u_i-\bar{u}_{i,h}\|_{b}
&\leq& C_i\eta_{a}(h)\|u_i - u_{i,h}\|_{a},\label{Err_Eigenfunction_Global_0_Norm}\\
|\lambda_i-\bar{\lambda}_{i,h}|
&\leq&C_i\|u_i-\bar{u}_{i,h}\|_{a}^2. \label{Estimate_Eigenvalue}
\end{eqnarray}
Here and hereafter $C_i$ is some constant depending on $i$ but independent of  the mesh size $h$.
\end{lemma}

%The following Rayleigh quotient expansion of the eigenvalue error is the tool
%to obtain the error estimates of the eigenvalue approximations.
%\begin{lemma}(\cite{BabuskaOsborn_1989})\label{Rayleigh_quotient_expansion_lem}
%Assume $(\lambda,u)$ is an eigenpair of the eigenvalue problem
%(\ref{weak_eigenvalue_problem}). Then for any $w \in H_0^1(\Omega)\backslash\{0\}$,
%the following expansion holds:
%\begin{equation}\label{Rayleigh_quotient_expansion}
%\frac{a(w,w)}{b(w,w)} - \lambda = \frac{a(w-u,w-u)}{b(w,w)} - \lambda\frac{(w-u,w-u)}{b(w,w)}.
%\end{equation}
%\end{lemma}

%================================================================================================
\section{Full multigrid algorithm for eigenvalue problem}
Recently, a multilevel correction scheme is introduced
in \cite{LinXie_MultiLevel,Xie_IMA,Xie_JCP} for
solving eigenvalue problems. Based on the idea of multilevel correction scheme,
we propose a type of full multigrid method for
eigenvalue problems here. The main idea in this method is to approximate
 the underlying boundary value
problems on each level by some multigrid smoothing iteration steps.
In order to describe the full multigrid method, we first introduce
 the sequence of finite element
spaces. % and the smoothing properties of appropriate smoothers.
We generate a coarse mesh $\mathcal{T}_H$
with the mesh size $H$ and the coarse linear finite element space $V_H$ is
defined on the mesh $\mathcal{T}_H$. Then we define a sequence of
 triangulations $\mathcal{T}_{h_k}$
of $\Omega\subset \mathcal{R}^d$ determined as follows.
Suppose $\mathcal{T}_{h_1}$ (produced from $\mathcal{T}_H$ by
regular refinements) is given and let $\mathcal{T}_{h_k}$ be obtained
from $\mathcal{T}_{h_{k-1}}$ via one regular refinement step
(produce $\beta^d$ subelements) such that
\begin{eqnarray}\label{mesh_size_recur}
h_k=\frac{1}{\beta}h_{k-1},\ \ \ \ k=2,\cdots,n,
\end{eqnarray}
where the positive number $\beta$ denotes the refinement index
 and larger than $1$ (always equals $2$).
Based on this sequence of meshes, we construct the corresponding
 nested linear finite element spaces such that
\begin{eqnarray}\label{FEM_Space_Series}
V_{H}\subseteq V_{h_1}\subset V_{h_2}\subset\cdots\subset V_{h_n}.
\end{eqnarray}
The sequence of finite element spaces
$V_{h_1}\subset V_{h_2}\subset\cdots\subset V_{h_n}$
 and the finite element space $V_H$ have  the following relations
of approximation accuracy
\begin{eqnarray}\label{delta_recur_relation}
\eta_a(H)\gtrsim\delta_{h_1}(\lambda_i),\ \ \ \
\delta_{h_k}(\lambda_i)=\frac{1}{\beta}\delta_{h_{k-1}}(\lambda_i),\ \ \ k=2,\cdots,n.
\end{eqnarray}
%\begin{remark}
%The relation (\ref{delta_recur_relation}) is reasonable since we can choose
%$\delta_{h_k}(\lambda_i)=h_k\ (k=1,\cdots,n)$. Always the upper bound of
%the estimate $\delta_{h_k}(\lambda_i)\lesssim h_k$ holds. Recently, we also obtain the
%lower bound result $\delta_{h_k}(\lambda_i)\gtrsim h_k$ (cf. \cite{LinXieXu}).
%\end{remark}


\subsection{One correction step}
In order to design the full multigrid method, we introduce an one correction step in this subsection.

Assume we have obtained an eigenpair approximation
$(\lambda_{\ell,h_k},u_{\ell,h_k})\in \mathcal{R}\times V_{h_k}$.
Now we introduce a type of iteration step to improve the accuracy of the
current eigenpair approximation $(\lambda_{\ell,h_k},u_{\ell,h_k})$.

\begin{algorithm}\label{Multigrid_Smoothing_Step} One Correction Step
\begin{enumerate}
\item Define the following auxiliary source problem:
Find $\widehat{u}_{\ell+1,h_k}\in V_{h_k}$ such that
\begin{eqnarray}\label{aux_problem}
a(\widehat{u}_{\ell+1,h_k},v_{h_k})&=&\lambda_{\ell,h_k}
b(u_{\ell,h_k},v_{h_k}),\ \
\ \forall v_{h_k}\in V_{h_k}.
\end{eqnarray}
Perform $m$ multigrid iteration steps with the initial value $u_{\ell,h_k}$
to obtain a new eigenfunction approximation
$\widetilde{u}_{\ell+1,h_k}\in V_{h_k}$ by
\begin{eqnarray}\label{Multigrid_Iteration_Step}
\widetilde{u}_{\ell+1,h_k} = MG(V_{h_k},\lambda_{\ell,h_k}u_{\ell,h_k},u_{\ell,h_k},m),
\end{eqnarray}
where $V_{h_k}$ denotes the working space for the multigrid iteration,
$\lambda_{\ell,h_k}u_{\ell,h_k}$ is the right hand side term of the linear equation,
$u_{\ell,h_k}$ denotes  the initial guess and $m$ is the number of multigrid iteration times.
\item  Define a new finite element
space $V_{H,h_k}=V_H+{\rm span}\{\widetilde{u}_{\ell+1,h_k}\}$ and solve
the following eigenvalue problem:
Find $(\lambda_{\ell+1,h_k},u_{\ell+1,h_k})\in\mathcal{R}\times V_{H,h_k}$ such
that $b(u_{\ell+1,h_k},u_{\ell+1,h_k})=1$ and
\begin{eqnarray}\label{Eigen_Augment_Problem}
a(u_{\ell+1,h_k},v_{H,h_k})&=&\lambda_{\ell+1,h_k} b(u_{\ell+1,h_k},v_{H,h_k}),\ \ \
\forall v_{H,h_k}\in V_{H,h_k}.
\end{eqnarray}
\end{enumerate}
In order to simplify the notation and summarize the above two steps, we define
\begin{eqnarray*}
(\lambda_{\ell+1,h_k},u_{\ell+1,h_k})=EigenMG(V_H,\lambda_{\ell,h_k}, u_{\ell,h_k},V_{h_k},m).
\end{eqnarray*}
\end{algorithm}
%--------------------------------------------------------------------------------------------
\begin{theorem}\label{Error_Estimate_One_Smoothing_Theorem}
Assume the multigrid iteration
 $\widetilde{u}_{\ell+1,h_k} = MG(V_{h_k},\lambda_{\ell,h_k}u_{\ell,h_k},u_{\ell,h_k},m)$
  has the following error reduction rate
\begin{eqnarray}\label{MG_Theta}
\|\widehat{u}_{\ell+1,h_k}-\widetilde{u}_{\ell+1,h_k}\|_a
\leq\theta \|\widehat{u}_{\ell+1,h_k}-u_{\ell,h_k}\|_a,
\end{eqnarray}
and $(\lambda_{\ell,h_k},u_{\ell,h_k})$ has the following properties
\begin{eqnarray}
\|\bar{u}_{h_k}-u_{\ell,h_k}\|_b&\leq&
C_i\eta_a(H)\|\bar{u}_{h_k}-u_{\ell,h_k}\|_a,\label{Estimate_h_k_b}\\
|\bar{\lambda}_{h_k}-\lambda_{\ell,h_k}|&\leq&
C_i\|\bar{u}_{h_k}-u_{\ell,h_k}\|_a^2.\label{Estimate_h_k_Eigenvalue}
\end{eqnarray}
After performing the one correction step defined in
Algorithm \ref{Multigrid_Smoothing_Step},
the resultant eigenpair approximation $(\lambda_{\ell+1,h_k},u_{\ell+1,h_k})\in\mathcal{R}\times V_{h_k}$ has the
following error estimates
\begin{eqnarray}
\|\bar{u}_{h_k}-u_{\ell+1,h_k}\|_a &\leq &
\gamma \|\bar{u}_{h_k}-u_{\ell,h_k}\|_a,\label{Estimate_h_k_1_a}\\
\|\bar{u}_{h_k}-u_{\ell+1,h_k}\|_b&\leq&
C_i\eta_a(H)\|\bar{u}_{h_k}-u_{\ell+1,h_k}\|_a,\label{Estimate_h_k_1_b}\\
|\bar{\lambda}_{h_k}-\lambda_{\ell+1,h_k}|&\leq&
C_i\|\bar{u}_{h_k}-u_{\ell+1,h_k}\|_a^2.\label{Estimate_h_k_1_Eigenvalue}
\end{eqnarray}
where
\begin{eqnarray}\label{Gamma_Definition}
\gamma=\theta+(1+2\theta)C_i\eta_a(H)+(1+\theta)C_i^2\eta_a^2(H).
\end{eqnarray}
\end{theorem}
%------------------------------------------------------------------------------------------------
\begin{proof}
From (\ref{Weak_Eigenvalue_Discrete}) and (\ref{aux_problem}), we have
\begin{eqnarray}\label{One_Correction_1}
a(\bar{u}_{h_k}-\widehat{u}_{\ell+1,h_k},v_{h_k})
=b(\bar{\lambda}_{h_k}\bar{u}_{h_k}-\lambda_{\ell,h_k}u_{\ell,h_k},v_{h_k}),
\ \ \ \ \forall v_{h_k}\in V_{h_k}.
\end{eqnarray}
It leads to the following estimates
\begin{eqnarray}\label{One_Correction_2}
\|\bar{u}_{h_k}-\widehat{u}_{\ell+1,h_k}\|_a &\leq&
\|\bar{\lambda}_{h_k}\bar{u}_{h_k}-\lambda_{\ell,h_k}u_{\ell,h_k}\|_b\nonumber\\
&\leq& |\bar{\lambda}_{h_k}-\lambda_{\ell,h_k}|+\|\bar{u}_{h_k}-u_{\ell,h_k}\|_b\nonumber\\
&\leq& C_i\eta_a(H)\|\bar{u}_{h_k}-u_{\ell,h_k}\|_a.
\end{eqnarray}
Combining (\ref{MG_Theta}) and (\ref{One_Correction_2}) leads to the following
linear solving error estimate for $\widetilde{u}_{\ell+1,h_k}$
\begin{eqnarray}\label{One_Correction_3}
\|\widehat{u}_{\ell+1,h_k}-\widetilde{u}_{\ell+1,h_k}\|_a&\leq&
\theta \|\widehat{u}_{\ell+1,h_k}-u_{\ell,h_k}\|_a\nonumber\\
&\leq&\theta \big(\|\widehat{u}_{\ell+1,h_k}-\bar{u}_{h_k}\|_a
 +\|\bar{u}_{h_k}-u_{\ell,h_k}\|_a\big)\nonumber\\
&\leq& \theta\big(1+C_i\eta_a(H)\big)\|\bar{u}_{h_k}-u_{\ell,h_k}\|_a.
\end{eqnarray}
Then from (\ref{One_Correction_2}) and (\ref{One_Correction_3}), we have the following inequalities
\begin{eqnarray}\label{One_Correction_4}
\|\bar{u}_{h_k}-\widetilde{u}_{\ell+1,h_k}\|_a&\leq& \|\bar{u}_{h_k}-\widehat{u}_{\ell+1,h_k}\|_a
+\|\widehat{u}_{\ell+1,h_k}-\widetilde{u}_{\ell+1,h_k}\|_a\nonumber\\
&\leq& \big(\theta+(1+\theta)C_i\eta_a(H)\big)\|\bar{u}_{h_k}-u_{\ell,h_k}\|_a.
\end{eqnarray}

The eigenvalue problem (\ref{Eigen_Augment_Problem})
 can be regarded  as a finite dimensional subspace approximation of the eigenvalue problem
  (\ref{Weak_Eigenvalue_Discrete}).
Similarly to Lemma \ref{Err_Eigen_Global_Lem} (see \cite[Theorem 4.4]{BabuskaOsborn_1989}),
from the second step in Algorithm \ref{Multigrid_Smoothing_Step} and (\ref{One_Correction_4}),
the following estimates hold
\begin{eqnarray}\label{Error_u_u_h_2}
\|\bar{u}_{h_k}-u_{\ell+1, h_k}\|_a&\leq&
\big(1+C_i\widetilde{\eta}_a(H)\big)\inf_{v_{H,h_k}\in V_{H,h_k}}\|\bar{u}_{h_k}-v_{H,h_k}\|_a\nonumber\\
&\leq& \big(1+C_i\eta_a(H)\big)\|\bar{u}_{h_k}-\widetilde{u}_{\ell+1,h_k}\|_a\nonumber\\
&\leq&\gamma \|\bar{u}_{h_k}-u_{\ell,h_k}\|_a
\end{eqnarray}
and
\begin{eqnarray}\label{Error_u_u_h_2_Negative}
\|\bar{u}_{h_k}-u_{\ell+1,h_k}\|_b&\leq&
C_i\widetilde{\eta}_a(H)\|\bar{u}_{h_k}-u_{\ell+1,h_k}\|_a\nonumber\\
&\leq& C_i\eta_a(H)\|\bar{u}_{h_k}-u_{\ell+1,h_k}\|_a,\\
|\bar{\lambda}_{h_k}-\lambda_{\ell+1,h_k}|&\leq&
C_i\|\bar{u}_{h_k}-u_{\ell+1,h_k}\|_a^2,
\end{eqnarray}
where
\begin{eqnarray}\label{Eta_a_h_2}
\widetilde{\eta}_a(H)&=&\sup_{f\in V,\|f\|_0=1}\inf_{v\in
V_{H,h_k}}\|Tf-v\|_a \leq \eta_a(H).
\end{eqnarray}
Then we obtained the desired results (\ref{Estimate_h_k_1_a})-(\ref{Estimate_h_k_1_Eigenvalue})
and complete the proof.
\end{proof}

%------------------------------------------------------------------------------------------------
\subsection{Full multigrid method for eigenvalue problem}
In this subsection, we introduce a full multigrid
scheme based on the {\it One Correction Step} defined in Algorithm
\ref{Multigrid_Smoothing_Step}. This type of full multigrid method can obtain
the optimal error estimate with the optimal computational work.

Since the multigrid method for the boundary value problem has the uniform
error reduction rate, we can choose suitable $m$ such that $\theta<1$ in (\ref{MG_Theta}).
From (\ref{Gamma_Definition}), we have $\gamma<1$ if $H$ is small enough.
From this observation, we can build the following full multigrid method for solving
eigenvalue problems.
\begin{algorithm}\label{Full_Multigrid}Full Multigrid Scheme
\begin{enumerate}
\item Solve the following eigenvalue problem in $V_{h_1}$:
Find $(\lambda_{h_1}, u_{h_1})\in \mathcal{R}\times V_{h_1}$ such that
\begin{equation*}
a(u_{h_1}, v_{h_1}) = \lambda_{h_1} b(u_{h_1}, v_{h_1}), \quad \forall v_{h_1}\in  V_{h_1}.
\end{equation*}
Solve this eigenvalue problem to get an eigenpair approximation $(\lambda_{h_1},u_{h_1})\in\mathcal{R}\times V_{h_1}$.
\item For $k=2,\cdots,n$, do the following iteration
\begin{itemize}
\item Set $u_{0,h_k} = u_{h_{k-1}}$.
\item Do the following multigrid iteration
\begin{eqnarray*}
(\lambda_{\ell+1,h_k}, u_{\ell+1,h_k})=EigenMG(V_H,\lambda_{\ell,h_k},u_{\ell,h_k},V_{h_k},m),
 \ \ \ \ {\rm for}\ \ell=0,\cdots, p-1.
\end{eqnarray*}
\item set $\lambda_{h_k}=\lambda_{p,h_k}$ and $u_{h_k}=u_{p,h_k}$.
\end{itemize}
end Do
\end{enumerate}
Finally, we obtain an eigenpair approximation
$(\lambda_{h_n},u_{h_n})\in \mathcal{R}\times V_{h_n}$.
\end{algorithm}
%------------------------------------------------------------------------------------------------------
\begin{theorem}
After implementing Algorithm \ref{Full_Multigrid}, the resultant
eigenpair approximation $(\lambda_{h_n},u_{h_n})$ has the following
error estimate
\begin{eqnarray}
\|\bar{u}_{h_n}-u_{h_n}\|_a &\leq&
C\frac{\gamma^p}{1-\beta\gamma^p}\delta_{h_n}(\lambda),\label{FM_Err_fun}\\
|\bar{\lambda}_{h_n}-\lambda_{h_n}|&\leq&C\delta_{h_n}^2(\lambda),\label{FM_Err_eigen}
\end{eqnarray}
under the condition $\beta\gamma^p<1$.
\end{theorem}
%--------------------------------------------------------------------------
\begin{proof}
Define $e_{k}:=\bar{u}_{h_k}-u_{h_k}$. Then from step 1
in Algorithm \ref{Full_Multigrid}, it is obvious $e_1=0$. For $k=2,\cdots,n$, we have
\begin{eqnarray}\label{FM_Estimate_1}
\|e_k\|_a&\leq& \gamma^p\|\bar{u}_{h_k}-u_{h_{k-1}}\|_a\nonumber\\
&\leq& \gamma^p\big(\|\bar{u}_{h_k}-\bar{u}_{h_{k-1}}\|_a
+\|\bar{u}_{h_{k-1}}-u_{h_{k-1}}\|_a\big)\nonumber\\
&\leq& \gamma^p \big(C\delta_{h_k}(\lambda)+\|e_{k-1}\|_a\big).
\end{eqnarray}
By iterating inequality (\ref{FM_Estimate_1}) and $\beta\gamma^p<1$, the following
inequalities hold
\begin{eqnarray}
\|e_n\|_a&\leq& C\gamma^p\delta_{h_n}(\lambda)+C\gamma^{2p}\delta_{h_{n-1}}(\lambda)+\cdots
+C\gamma^{(n-1)p}\delta_{h_2}(\lambda)\nonumber\\
&\leq& C\sum_{k=2}^n \gamma^{(n-k+1)p}\delta_{h_{\ell}}(\lambda)
=C\left(\sum_{k=2}^n \big(\beta\gamma^{p}\big)^{n-k}\right)\gamma^{p}\delta_{h_n}(\lambda)\nonumber\\
&\leq&C\frac{\gamma^p}{1-\beta\gamma^p}\delta_{h_n}(\lambda).
\end{eqnarray}
For such choice of $p$, we arrive the desired result (\ref{FM_Err_fun}) and
(\ref{FM_Err_eigen}) can be obtained by (\ref{Estimate_Eigenvalue}) and (\ref{FM_Err_fun}).
\end{proof}
%-------------------------------------------------------------------------------------------------
\begin{remark}
The good convergence rate of the multigrid method for boundary value problems leads to that
we do not need to choose large $m$ and $p$ \cite{BrennerScott,Hackbusch_Book,Shaidurov,Xu}.
\end{remark}
%-------------------------------------------------------------------------------------------------
%\section{Work estimates of eigenvalue multigrid scheme}
Now we turn our attention to the estimate of computational work
for {\it Full Multigrid Scheme \ref{Full_Multigrid}}. We will show that Algorithm \ref{Full_Multigrid}
makes solving eigenvalue problem need almost the same work as solving the corresponding
boundary value problem.

First, we define the dimension of each level
finite element space as $N_k:={\rm dim}V_{h_k}$. Then we have
\begin{eqnarray}\label{relation_dimension}
N_k=\Big(\frac{1}{\beta}\Big)^{d(n-k)}N_n,\ \ \ k=1,2,\cdots, n.
\end{eqnarray}
\begin{theorem}
Assume the eigenvalue problem solved in the coarse spaces $V_{H}$ and $V_{h_1}$ need work
$\mathcal{O}(M_H)$ and $\mathcal{O}(M_{h_1})$, respectively, and the work of the
multigrid solver $MG(V_{h_k},\lambda_{\ell,h_k}u_{\ell,h_k},u_{\ell,h_k},m)$
 in each level space $V_{h_k}$ is $\mathcal{O}(N_k)$ for $k=2,3,\cdots,n$. Then the work involved in the
Full Multigrid Scheme \ref{Full_Multigrid} is  $\mathcal{O}(N_n+M_H\log(N_n)+M_{h_1})$.
Furthermore, the complexity will be $\mathcal{O}(N_n)$ provided $M_H\ll N_k$ and $M_{h_1}\leq N_k$.
\end{theorem}
%---------------------------------------------------------------------------------------------------
\begin{proof}
Let $W_{k}$ denote the work in the correction step in the $k$-th finite element space $V_{h_{k}}$.
Then with the correction definition in Algorithm \ref{Multigrid_Smoothing_Step}, we have
\begin{eqnarray}\label{work_k}
W_{k}&=&\mathcal{O}(N_{k}+M_H), \ \ \ \  \ k=2,\cdots, n.
\end{eqnarray}
Iterating (\ref{work_k}) and using the fact (\ref{relation_dimension}), we obtain
\begin{eqnarray*}
{\rm Total\ work}&=&\sum_{k=1}^nW_k=\mathcal{O}\Big(M_{h_1}+\sum_{k=2}^n\big(N_{k}+M_H\big)\Big)\nonumber\\
&=&\mathcal{O}\Big(M_{h_1}+(n-1)M_H+\sum_{k=2}^n\big(\frac{1}{\beta}\big)^{d(n-k)}N_n\Big)\nonumber\\
&=&\mathcal{O}(N_n+M_H\log N_n+M_{h_1}).
\end{eqnarray*}
This is the desired result $\mathcal{O}(N_n+M_H\log N_n+M_{h_1})$ and the
one $\mathcal{O}(N_n)$  can be obtained by the conditions $M_H\ll N_n$ and $M_{h_1}\leq N_n$.
\end{proof}

%%---------------------------------------------------------------------------------------------------
\section{Numerical results}
In this section, two numerical examples are presented to illustrate the
efficiency of the full multigrid scheme proposed in this
paper.

\subsection{Model eigenvalue problem}
Here we give the numerical results of the full multigrid
scheme for the model eigenvalue problem:
Find $(\lambda,u)$ such that
\begin{equation}\label{problem}
\left\{
\begin{array}{rcl}
-\Delta u&=&\lambda u,\quad{\rm in}\ \Omega,\\
u&=&0,\quad\ \  {\rm on}\ \partial\Omega,\\
\int_{\Omega} u^2d\Omega&=&1,
\end{array}
\right.
\end{equation}
where $\Omega=(0,1)\times(0,1)$.


The sequence of finite element spaces are constructed by
using linear element on the series of meshes which are produced by
regular refinement with $\beta =2$ (connecting the midpoints of each edge).
In this example, we use two meshes which are generated by Delaunay method as the initial mesh
$\mathcal{T}_{h_1}$ and set $\mathcal{T}_H=\mathcal{T}_{h_1}$
to investigate the convergence behaviors.
Figure \ref{Initial_Mesh} shows the corresponding
initial meshes: one is coarse and the other is fine.


Algorithm \ref{Full_Multigrid} is applied to solve the eigenvalue problem. In this subsection, we choose
$m=2$ and $2$ conjugate gradient smoothing steps for the presmoothing and postsmoothing in each
multigrid iteration step in Algorithm \ref{Multigrid_Smoothing_Step}.  In each level of the
full multigrid scheme defined in Algorithm \ref{Full_Multigrid}, we only do $2$ multigrid
iteration steps ($p=2$) defined in Algorithm \ref{Multigrid_Smoothing_Step}. 
For comparison, we also solve the eigenvalue problem
by the direct method.
\begin{figure}[ht]
\centering
\includegraphics[width=5.5cm,height=5.5cm]{Initial_coarse_mesh.ps}
\includegraphics[width=5.5cm,height=5.5cm]{Initial_fine_mesh.ps}
\caption{\small\texttt The coarse and fine initial meshes
for the unit square} \label{Initial_Mesh}
\end{figure}
Figure \ref{numerical_multi_grid_Model}
gives the corresponding numerical results for the first eigenvalue
$\lambda_1=2\pi^2$ and the corresponding eigenfunction on the two
initial meshes illustrated in Figure \ref{Initial_Mesh}.
\begin{figure}[ht]
\centering
\includegraphics[width=7cm,height=6cm]{Error_Model_Problem_H_6.ps}
\includegraphics[width=7cm,height=6cm]{Error_Model_Problem_H_12.ps}
\caption{\small\texttt The errors of the full multigrid
algorithm for the first six eigenvalues on the unit square, where $u_h$
 and $\lambda_h$ denote the eigenfunction and eigenvalue approximations 
 by Algorithm \ref{Full_Multigrid}, and $u_h^{\rm dir}$ and
 $\lambda_h^{\rm dir}$ denote the eigenfunction
 and eigenvalue approximation by direct eigenvalue solving
 (The left figure corresponds to the left mesh in Figure \ref{Initial_Mesh} and
the right figure corresponds to the right mesh in Figure \ref{Initial_Mesh}) }
\label{numerical_multi_grid_Model}
\end{figure}

From Figure \ref{numerical_multi_grid_Model}, we find the full multigrid scheme can obtain
the optimal error estimates as same as the direct eigenvalue problem
solving for the eigenvalue and the corresponding eigenfunction approximations.

We also check the convergence behavior for multi eigenvalue approximations with
Algorithm \ref{Full_Multigrid}. Here the first six eigenvalues
$\lambda=2\pi^2, 5\pi^2, 5\pi^2, 8\pi^2,$ $10\pi^2, 10\pi^2$
are investigated. We adopt the meshes in Figure \ref{Initial_Mesh} as
the initial meshes and the corresponding numerical results are shown in Figure
\ref{numerical_multi_grid_Model_Multi} which also exhibits the optimal convergence
of the full multigrid scheme.
\begin{figure}[ht]
\centering
\includegraphics[width=7cm,height=6cm]{Error_Model_Problem_H_6_Multi.ps}
\includegraphics[width=7cm,height=6cm]{Error_Model_Problem_H_12_Multi.ps}
\caption{\small\texttt The errors of the full multigrid
algorithm for the first six eigenvalues on the unit square,
 $\lambda_h$ denotes the eigenvalue approximation
 by Algorithm \ref{Full_Multigrid},
 $\lambda_h^{\rm dir}$ denotes the eigenvalue approximation by direct eigenvalue solving
 (The left figure corresponds to the left mesh in Figure \ref{Initial_Mesh} and
the right figure corresponds to the right mesh in Figure \ref{Initial_Mesh}) }
 \label{numerical_multi_grid_Model_Multi}
\end{figure}


%-----------------------------------------------------------------------------------------------------
\subsection{More general eigenvalue problem}
Here we give numerical results of the full multigrid method
for solving a more general eigenvalue problem on the unit square
domain $\Omega=(0, 1)\times (0, 1)$: Find $(\lambda,u)$ such that
\begin{equation}\label{Example_2}
\left\{
\begin{array}{rcl}
-\nabla\cdot\mathcal{A}\nabla u+\phi u&=&\lambda\rho u,\quad{\rm in}\ \Omega,\\
u&=&0,\quad\ \ \ {\rm on}\ \partial\Omega,\\
\int_{\Omega}\rho u^2d\Omega&=&1,
\end{array}
\right.
\end{equation}
where
\begin{equation*}
\mathcal{A}=\left (
\begin{array}{cc}
$$1+(x_1-\frac{1}{2})^2$$&$$(x_1-\frac{1}{2})(x_2-\frac{1}{2})$$\\
$$(x_1-\frac{1}{2})(x_2-\frac{1}{2})$$&$$1+(x_2-\frac{1}{2})^2$$
\end{array}
\right),
\end{equation*}
$\phi=e^{(x_1-\frac{1}{2})(x_2-\frac{1}{2})}$ and
$\rho=1+(x_1-\frac{1}{2})(x_2-\frac{1}{2})$.

In this example, we also use two coarse meshes which are shown in Figure \ref{Initial_Mesh}
as the initial meshes to investigate the convergence behaviors.
Since the exact solution is not known, we choose an adequately accurate eigenvalue
approximations with the extrapolation method (see, e.g., \cite{LinLin}) as the exact
eigenvalues to measure errors.
Figure \ref{numerical_multi_grid_General_Multi} gives the corresponding
numerical results for the first six eigenvalue approximations. In this example, we also choose
$m=2$, $p=2$ and $2$ conjugate gradient smoothing step in the presmoothing and postsmoothing procedure.
Here we also compare the numerical results with the direct algorithm. The corresponding results 
are shown in Figure \ref{numerical_multi_grid_General_Multi} which
  also exhibits the optimality of the error and complexity for
Algorithm \ref{Full_Multigrid}.
\begin{figure}[ht]
\centering
\includegraphics[width=7cm,height=6cm]{Error_General_Problem_H_6_Multi.ps}
\includegraphics[width=7cm,height=6cm]{Error_General_Problem_H_12_Multi.ps}
\caption{\small\texttt The errors of the full multigrid
algorithm for the first six eigenvalues on the unit square,
 $\lambda_h$ denotes the eigenvalue approximation
 by Algorithm \ref{Full_Multigrid},
 $\lambda_h^{\rm dir}$ denotes the eigenvalue approximation by direct eigenvalue solving
 (The left figure corresponds to the left mesh in Figure \ref{Initial_Mesh} and
the right figure corresponds to the right mesh in Figure \ref{Initial_Mesh}) }
 \label{numerical_multi_grid_General_Multi}
\end{figure}



%--------------------------------------------------------------------------------------
\section{Concluding remarks}
In this paper, we give a full multigrid scheme
to solve 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 some multigrid iteration steps, and solutions of
eigenvalue problems defined on the coarsest finite element space.

We can replace the multigrid iteration by other types of efficient iteration schemes
such as algebraic multigrid method, the type of preconditioned schemes based on
the subspace decomposition and subspace corrections (see, e.g., \cite{BrennerScott, Xu}),
and the domain decomposition method (see, e.g., \cite{ToselliWidlund,XuZhou_Eigen_LocalParallel}).
The ideas can be extended to other types of linear and nonlinear eigenvalue
problems and other types problems. These will be investigated in  our future work.








\begin{thebibliography}{17}


\bibitem{Adams}
R. A. Adams, {\em Sobolev Spaces}, Academic Press, New York, 1975.


\bibitem{BabuskaOsborn_1989}
I. Babu\v{s}ka and J. E. Osborn, {\em Finite element-Galerkin
approximation of the eigenvalues and eigenvectors of selfadjoint
problems}, Math. Comp. 52 (1989), 275-297.

\bibitem{BabuskaOsborn_Book}
I. Babu\v{s}ka and J. Osborn, {\em Eigenvalue Problems}, In Handbook of
Numerical Analysis, Vol. II, (Eds. P. G. Lions and Ciarlet P.G.),
Finite Element Methods (Part 1), North-Holland, Amsterdam, 641-787,
1991.

\bibitem{BankDupont}
R. E. Bank and T. Dupont, {\em An optimal order process for solving finite element equations},
 Math. Comp., 36 (1981), 35-51.

\bibitem{Bramble}
J. H. Bramble, {\em Multigrid Methods}, Pitman Research Notes in Mathematics, V. 294,
John Wiley and Sons, 1993.


\bibitem{BramblePasciak}
J. H. Bramble and J. E. Pasciak, {\em New convergence estimates for multigrid algorithms},
Math. Comp. 49 (1987), 311-329.



\bibitem{BrambleZhang}
J. H. Bramble and X. Zhang, {\em The analysis of Multigrid Methods}, Handbook of Numerical Analysis,
Vol. VII, P. G. Ciarlet and J. L. Lions, eds., Elsevier Science, 173-415, 2000.

%\bibitem{BrandtMcCormickRuge}
%A. Brandt, S. McCormick, and J. Ruge, {\em Multigrid methods for differential eigenproblems},
%SIAM J. Sci. Stat. Comput., 4(2) (1983), 244-260.

\bibitem{BrennerScott}
S. Brenner and L. Scott, {\em The Mathematical Theory of Finite Element
Methods}, New York: Springer-Verlag, 1994.

%\bibitem{ChanSharapov}
%T. F. Chan and I. Sharapov, {\em Subspace correction multi-level methods for elliptic eigenvalue problems},
%Numer. Linear Algebra Appl., 9  (2002), 1-20.

\bibitem{Chatelin}
F. Chatelin, {\em Spectral Approximation of Linear Operators}, Academic
Press Inc, New York, 1983.

%\bibitem{ChenGongHeYangZhou}
%H. Chen, X. Gong, L. He, Z. Yang and A. Zhou,
%{\em Numerical analysis of finite dimensional approximations of Kohn-Sham models},
%Adv. Comput. Math., 38 (2013), 225-256.


%\bibitem{ChenGongZhou}
%H. Chen, X. Gong and A. Zhou, {\em Numerical approximations of a nonlinear eigenvalue
%problem and applications to a density functional model},
%Math. Methods Applied Sci., 33 (2010), 1723-1742.
%
%\bibitem{ChenHeZhou}
%H. Chen, L. He and A. Zhou,
%{\em Finite element approximations of nonlinear eigenvalue problems in quantum physics},
%Comput. Meth. Appl. Mech. Engrg., 200 (2011), 1846-1865.


\bibitem{Ciarlet}
P. G. Ciarlet, {\em The finite Element Method for Elliptic Problem},
North-holland Amsterdam, 1978.

%\bibitem{Conway}
%J. Conway, {\em A Course in Functional Analysis}, Springer-Verlag, New-York, 1990.

%\bibitem{DaiZhou}
%X. Dai and A. Zhou, Three-scale finite element discretizations for quantum eigenvalue problems,
%SIAM J. Numer. Anal., 46 (2008), 295-324.

\bibitem{Hackbusch}
W. Hackbusch, {\em On the computation of approximate eigenvalues and eigenfunctions of
elliptic operators by means of
a multi-grid method}, Siam J. Numer. Anal., 16(2) (1979), 201-215.

\bibitem{Hackbusch_Book}
W. Hackbusch, {\em Multi-grid Methods and Applications}, Springer-Verlag, Berlin, 1985.

%\bibitem{HuCheng}
%X. Hu and X. Cheng,
%{\em Acceleration of a two-grid method for eigenvalue problems}, Math. Comp.,
%80(275) (2011), 1287-1301.

%\bibitem{KohnSham}
%W. Kohn and L.J. Sham, {\em Self-consistent equations including exchange and correlation effects},
%Phys. Rev. A, 140 (1965), 4743-4754.

%\bibitem{LinXie}
%Q. Lin and H. Xie, {\em A multi-level correction scheme for eigenvalue problems},
%http://arxiv.org/abs/1107.0223, 2010, accepted by Math. Comput.

\bibitem{LinXie_MultiLevel}
Q. Lin and H. Xie, {\em A multi-level correction scheme for eigenvalue problems},
Math. Comp., DOI: http://dx.doi.org/10.1090/S0025-5718-2014-02825-1, 2014.

%\bibitem{LinXieXu}
%Q. Lin, H. Xie, and J. Xu, {\em Lower bounds of the discretization for piecewise polynomials},
%http://arxiv.org/abs/1106.4395, 2011, accepted by Math. Comput.


%\bibitem{LinYan}
%Q. Lin and N. Yan, {\em The Construction and Analysis of High Efficiency
%Finite Element Methods}, Hebei University Publishers, 1995.
%
%
%\bibitem{Martin}
%R. Martin, {\em Electronic Structure: Basic Theory and Practical Methods}, Cambridge University
%Press, London, (2004).

\bibitem{LinLin}
Q. Lin  and J. Lin, Finite Element Methods: Accuracy and Inprovement,
Science Press, Beijing, 2006.

\bibitem{McCormick}
S. F. McCormick, ed., {\em Multigrid Methods}. SIAM Frontiers in Applied Matmematics 3.
 Society for Industrial and Applied Mathematics, Philadelphia, 1987.

%\bibitem{ParrYang}
%R. Parr and W. Yang, {\em Density-Functional Theory of Atoms and Molecules}, Oxford University
%Press, New York, Clarendon Press, Oxford, (1994).

\bibitem{ScottZhang}
L. R. Scott and S. Zhang, {\em Higher dimensional non-nested multigrid methods}, Math. Comp.,
 58 (1992), 457-466.

\bibitem{Shaidurov}
V. V. Shaidurov, {\em Multigrid methods for finite element}, Kluwer
Academic Publics, Netherlands, 1995.

%\bibitem{SulemSulem}
%C. Sulem and P. Sulem, {\em The Nonlinear Schr\"{o}dinger Equation: Self-focusing and Wave Collapse},
%Springer, New York, (1999).

\bibitem{ToselliWidlund}
A. Toselli and O. Widlund, {\em Domain Decomposition Methods: Algorithm and Theory},
Springer-Verlag, Berlin Heidelberg, 2005.

\bibitem{Xie_IMA}
H. Xie, A type of multilevel method for the Steklov eigenvalue problem,
IMA J. Numer. Anal., 34 (2014), 592-608.

\bibitem{Xie_JCP}
H. Xie, A multigrid method for eigenvalue problem,
J. Comput. Phys., 274 (2014),  550-561.

\bibitem{Xu}
J. Xu, {\em Iterative methods by space decomposition and subspace
correction}, SIAM Review, 34(4) (1992), 581-613.

\bibitem{Xu_Two_Grid}
J. Xu, {\em A new class of iterative methods for nonselfadjoint or indefinite problems},
SIAM J. Numer. Anal., 29 (1992), 303-319.

%\bibitem{Xu_Nonlinear}
%J. Xu, {\em A novel two-grid method for semilinear elliptic equations},
%SIAM J. Sci. Comput., 15 (1994), 231-237.

%\bibitem{XuZhou}
%J. Xu and A. Zhou, {\em A two-grid discretization scheme for eigenvalue
%problems}, Math. Comput., 70 (233) (2001), 17-25.

\bibitem{XuZhou_Eigen_LocalParallel}
J. Xu and A. Zhou, {\em Local and parallel finite element algorithm for
eigenvalue problems}, Acta Math. Appl. Sin. Engl. Ser.,  18(2) (2002),
185-200.

%\bibitem{YangBi}
%Y. Yang and H. Bi,  {\em Two-grid finite element discretization
%schemes based on shifted-inverse power method for elliptic eigenvalue problems},
%SIAM J. Numer. Anal., 49(4) (2011), 1602-1624.

%\bibitem{Yserentant}
%H. Yserentant, {\em On the multilevel splitting of finite element spaces}, Numer. Math.,
%49 (1986), 379-412.

%\bibitem{Zhou}
%A. Zhou, {\em Multi-level adaptive corrections in finite dimensional
%approximations}, J. Comp. Math., 28(1) (2010), 45-54.

\end{thebibliography}

\end{document}

1409.7944.extracted_bib
{Adams R. A. Adams, {\em Sobolev Spaces, Academic Press, New York, 1975.
1409.7944.extracted_bib
{BabuskaOsborn_1989 I. Babu\v{ska and J. E. Osborn, {\em Finite element-Galerkin approximation of the eigenvalues and eigenvectors of selfadjoint problems, Math. Comp. 52 (1989), 275-297.
1409.7944.extracted_bib
{BabuskaOsborn_Book I. Babu\v{ska and J. Osborn, {\em Eigenvalue Problems, In Handbook of Numerical Analysis, Vol. II, (Eds. P. G. Lions and Ciarlet P.G.), Finite Element Methods (Part 1), North-Holland, Amsterdam, 641-787, 1991.
1409.7944.extracted_bib
{BankDupont R. E. Bank and T. Dupont, {\em An optimal order process for solving finite element equations, Math. Comp., 36 (1981), 35-51.
1409.7944.extracted_bib
{Bramble J. H. Bramble, {\em Multigrid Methods, Pitman Research Notes in Mathematics, V. 294, John Wiley and Sons, 1993.
1409.7944.extracted_bib
{BramblePasciak J. H. Bramble and J. E. Pasciak, {\em New convergence estimates for multigrid algorithms, Math. Comp. 49 (1987), 311-329.
1409.7944.extracted_bib
{BrambleZhang J. H. Bramble and X. Zhang, {\em The analysis of Multigrid Methods, Handbook of Numerical Analysis, Vol. VII, P. G. Ciarlet and J. L. Lions, eds., Elsevier Science, 173-415, 2000. %
1409.7944.extracted_bib
{BrandtMcCormickRuge %A. Brandt, S. McCormick, and J. Ruge, {\em Multigrid methods for differential eigenproblems, %SIAM J. Sci. Stat. Comput., 4(2) (1983), 244-260.
1409.7944.extracted_bib
{BrennerScott S. Brenner and L. Scott, {\em The Mathematical Theory of Finite Element Methods, New York: Springer-Verlag, 1994. %
1409.7944.extracted_bib
{ChanSharapov %T. F. Chan and I. Sharapov, {\em Subspace correction multi-level methods for elliptic eigenvalue problems, %Numer. Linear Algebra Appl., 9 (2002), 1-20.
1409.7944.extracted_bib
{Chatelin F. Chatelin, {\em Spectral Approximation of Linear Operators, Academic Press Inc, New York, 1983. %
1409.7944.extracted_bib
{ChenGongHeYangZhou %H. Chen, X. Gong, L. He, Z. Yang and A. Zhou, %{\em Numerical analysis of finite dimensional approximations of Kohn-Sham models, %Adv. Comput. Math., 38 (2013), 225-256. %
1409.7944.extracted_bib
{ChenGongZhou %H. Chen, X. Gong and A. Zhou, {\em Numerical approximations of a nonlinear eigenvalue %problem and applications to a density functional model, %Math. Methods Applied Sci., 33 (2010), 1723-1742. % %
1409.7944.extracted_bib
{ChenHeZhou %H. Chen, L. He and A. Zhou, %{\em Finite element approximations of nonlinear eigenvalue problems in quantum physics, %Comput. Meth. Appl. Mech. Engrg., 200 (2011), 1846-1865.
1409.7944.extracted_bib
{Ciarlet P. G. Ciarlet, {\em The finite Element Method for Elliptic Problem, North-holland Amsterdam, 1978. %
1409.7944.extracted_bib
{Conway %J. Conway, {\em A Course in Functional Analysis, Springer-Verlag, New-York, 1990. %
1409.7944.extracted_bib
{DaiZhou %X. Dai and A. Zhou, Three-scale finite element discretizations for quantum eigenvalue problems, %SIAM J. Numer. Anal., 46 (2008), 295-324.
1409.7944.extracted_bib
{Hackbusch W. Hackbusch, {\em On the computation of approximate eigenvalues and eigenfunctions of elliptic operators by means of a multi-grid method, Siam J. Numer. Anal., 16(2) (1979), 201-215.
1409.7944.extracted_bib
{Hackbusch_Book W. Hackbusch, {\em Multi-grid Methods and Applications, Springer-Verlag, Berlin, 1985. %
1409.7944.extracted_bib
{HuCheng %X. Hu and X. Cheng, %{\em Acceleration of a two-grid method for eigenvalue problems, Math. Comp., %80(275) (2011), 1287-1301. %
1409.7944.extracted_bib
{KohnSham %W. Kohn and L.J. Sham, {\em Self-consistent equations including exchange and correlation effects, %Phys. Rev. A, 140 (1965), 4743-4754. %
1409.7944.extracted_bib
{LinXie %Q. Lin and H. Xie, {\em A multi-level correction scheme for eigenvalue problems, %http://arxiv.org/abs/1107.0223, 2010, accepted by Math. Comput.
1409.7944.extracted_bib
{LinXie_MultiLevel Q. Lin and H. Xie, {\em A multi-level correction scheme for eigenvalue problems, Math. Comp., DOI: http://dx.doi.org/10.1090/S0025-5718-2014-02825-1, 2014. %
1409.7944.extracted_bib
{LinXieXu %Q. Lin, H. Xie, and J. Xu, {\em Lower bounds of the discretization for piecewise polynomials, %http://arxiv.org/abs/1106.4395, 2011, accepted by Math. Comput. %
1409.7944.extracted_bib
{LinYan %Q. Lin and N. Yan, {\em The Construction and Analysis of High Efficiency %Finite Element Methods, Hebei University Publishers, 1995. % % %
1409.7944.extracted_bib
{Martin %R. Martin, {\em Electronic Structure: Basic Theory and Practical Methods, Cambridge University %Press, London, (2004).
1409.7944.extracted_bib
{LinLin Q. Lin and J. Lin, Finite Element Methods: Accuracy and Inprovement, Science Press, Beijing, 2006.
1409.7944.extracted_bib
{McCormick S. F. McCormick, ed., {\em Multigrid Methods. SIAM Frontiers in Applied Matmematics 3. Society for Industrial and Applied Mathematics, Philadelphia, 1987. %
1409.7944.extracted_bib
{ParrYang %R. Parr and W. Yang, {\em Density-Functional Theory of Atoms and Molecules, Oxford University %Press, New York, Clarendon Press, Oxford, (1994).
1409.7944.extracted_bib
{ScottZhang L. R. Scott and S. Zhang, {\em Higher dimensional non-nested multigrid methods, Math. Comp., 58 (1992), 457-466.
1409.7944.extracted_bib
{Shaidurov V. V. Shaidurov, {\em Multigrid methods for finite element, Kluwer Academic Publics, Netherlands, 1995. %
1409.7944.extracted_bib
{SulemSulem %C. Sulem and P. Sulem, {\em The Nonlinear Schr\"{odinger Equation: Self-focusing and Wave Collapse, %Springer, New York, (1999).
1409.7944.extracted_bib
{ToselliWidlund A. Toselli and O. Widlund, {\em Domain Decomposition Methods: Algorithm and Theory, Springer-Verlag, Berlin Heidelberg, 2005.
1409.7944.extracted_bib
{Xie_IMA H. Xie, A type of multilevel method for the Steklov eigenvalue problem, IMA J. Numer. Anal., 34 (2014), 592-608.
1409.7944.extracted_bib
{Xie_JCP H. Xie, A multigrid method for eigenvalue problem, J. Comput. Phys., 274 (2014), 550-561.
1409.7944.extracted_bib
{Xu J. Xu, {\em Iterative methods by space decomposition and subspace correction, SIAM Review, 34(4) (1992), 581-613.
1409.7944.extracted_bib
{Xu_Two_Grid J. Xu, {\em A new class of iterative methods for nonselfadjoint or indefinite problems, SIAM J. Numer. Anal., 29 (1992), 303-319. %
1409.7944.extracted_bib
{Xu_Nonlinear %J. Xu, {\em A novel two-grid method for semilinear elliptic equations, %SIAM J. Sci. Comput., 15 (1994), 231-237. %
1409.7944.extracted_bib
{XuZhou %J. Xu and A. Zhou, {\em A two-grid discretization scheme for eigenvalue %problems, Math. Comput., 70 (233) (2001), 17-25.
1409.7944.extracted_bib
{XuZhou_Eigen_LocalParallel J. Xu and A. Zhou, {\em Local and parallel finite element algorithm for eigenvalue problems, Acta Math. Appl. Sin. Engl. Ser., 18(2) (2002), 185-200. %
1409.7944.extracted_bib
{YangBi %Y. Yang and H. Bi, {\em Two-grid finite element discretization %schemes based on shifted-inverse power method for elliptic eigenvalue problems, %SIAM J. Numer. Anal., 49(4) (2011), 1602-1624. %
1409.7944.extracted_bib
{Yserentant %H. Yserentant, {\em On the multilevel splitting of finite element spaces, Numer. Math., %49 (1986), 379-412. %
1409.7944.extracted_bib
{Zhou %A. Zhou, {\em Multi-level adaptive corrections in finite dimensional %approximations, J. Comp. Math., 28(1) (2010), 45-54.