Acceleration of a two-grid method for eigenvalue problems

Authors:
Xiaozhe Hu and Xiaoliang Cheng

Journal:
Math. Comp. **80** (2011), 1287-1301

MSC (2010):
Primary 65L15, 65N15, 65N25, 65N30, 65N55

Published electronically:
February 18, 2011

Corrigendum:
Math. Comp. 84 (2015), 2701--2704.

MathSciNet review:
2785459

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: This paper provides a new two-grid discretization method for solving partial differential equation or integral equation eigenvalue problems. In 2001, Xu and Zhou introduced a scheme that reduces the solution of an eigenvalue problem on a finite element grid to that of one single linear problem on the same grid together with a similar eigenvalue problem on a much coarser grid. By solving a slightly different linear problem on the fine grid, the new algorithm in this paper significantly improves the theoretical error estimate which allows a much coarser mesh to achieve the same asymptotic convergence rate. Numerical examples are also provided to demonstrate the efficiency of the new method.

**1.**O. Axelsson and W. Layton,*A two-level discretization of nonlinear boundary value problems*, SIAM J. Numer. Anal.**33**(1996), no. 6, 2359–2374. MR**1427468**, 10.1137/S0036142993247104**2.**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**, 10.1090/S0025-5718-1989-0962210-8**3.**P. G. Ciarlet and J.-L. Lions (eds.),*Handbook of numerical analysis. Vol. II*, Handbook of Numerical Analysis, II, North-Holland, Amsterdam, 1991. Finite element methods. Part 1. MR**1115235****4.**Françoise Chatelin,*Spectral approximation of linear operators*, Computer Science and Applied Mathematics, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York, 1983. With a foreword by P. Henrici; With solutions to exercises by Mario Ahués. MR**716134****5.**L Chen and C.-S. Zhang,*AFEM@matlab: a Matlab package of adaptive finite element methods*, Tech. report, University of Maryland at College Park, 2006.**6.**C.-S. Chien and B.-W. Jeng,*A two-grid discretization scheme for semilinear elliptic eigenvalue problems*, SIAM J. Sci. Comput.**27**(2006), no. 4, 1287–1304. MR**2199749**, 10.1137/030602447**7.**Clint N. Dawson and Mary F. Wheeler,*Two-grid methods for mixed finite element approximations of nonlinear parabolic equations*, Domain decomposition methods in scientific and engineering computing (University Park, PA, 1993) Contemp. Math., vol. 180, Amer. Math. Soc., Providence, RI, 1994, pp. 191–203. MR**1312392**, 10.1090/conm/180/01971**8.**Clint N. Dawson, Mary F. Wheeler, and Carol S. Woodward,*A two-grid finite difference scheme for nonlinear parabolic equations*, SIAM J. Numer. Anal.**35**(1998), no. 2, 435–452 (electronic). MR**1618822**, 10.1137/S0036142995293493**9.**Gene H. Golub and Charles F. Van Loan,*Matrix computations*, 3rd ed., Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 1996. MR**1417720****10.**Jicheng Jin, Shi Shu, and Jinchao Xu,*A two-grid discretization method for decoupling systems of partial differential equations*, Math. Comp.**75**(2006), no. 256, 1617–1626 (electronic). MR**2240627**, 10.1090/S0025-5718-06-01869-2**11.**W. Layton and W. Lenferink,*Two-level Picard and modified Picard methods for the Navier-Stokes equations*, Appl. Math. Comput.**69**(1995), no. 2-3, 263–274. MR**1326676**, 10.1016/0096-3003(94)00134-P**12.**W. Layton and L. Tobiska,*A two-level method with backtracking for the Navier-Stokes equations*, SIAM J. Numer. Anal.**35**(1998), no. 5, 2035–2054 (electronic). MR**1639994**, 10.1137/S003614299630230X**13.**Martine Marion and Jinchao Xu,*Error estimates on a new nonlinear Galerkin method based on two-grid finite elements*, SIAM J. Numer. Anal.**32**(1995), no. 4, 1170–1184. MR**1342288**, 10.1137/0732054**14.**Beresford N. Parlett,*The symmetric eigenvalue problem*, Classics in Applied Mathematics, vol. 20, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1998. Corrected reprint of the 1980 original. MR**1490034****15.**G. Peters and J. H. Wilkinson,*Inverse iteration, ill-conditioned equations and Newton’s method*, SIAM Rev.**21**(1979), no. 3, 339–360. MR**535118**, 10.1137/1021052**16.**T. Utnes,*Two-grid finite element formulations of the incompressible Navier-Stokes equations*, Comm. Numer. Methods Engrg.**13**(1997), no. 8, 675–684. MR**1466044**, 10.1002/(SICI)1099-0887(199708)13:8<675::AID-CNM98>3.0.CO;2-N**17.**Jinchao Xu,*A new class of iterative methods for nonselfadjoint or indefinite problems*, SIAM J. Numer. Anal.**29**(1992), no. 2, 303–319. MR**1154268**, 10.1137/0729020**18.**Jinchao Xu,*A novel two-grid method for semilinear elliptic equations*, SIAM J. Sci. Comput.**15**(1994), no. 1, 231–237. MR**1257166**, 10.1137/0915016**19.**Jinchao Xu,*Two-grid discretization techniques for linear and nonlinear PDEs*, SIAM J. Numer. Anal.**33**(1996), no. 5, 1759–1777. MR**1411848**, 10.1137/S0036142992232949**20.**Jinchao Xu and Aihui Zhou,*Local and parallel finite element algorithms based on two-grid discretizations*, Math. Comp.**69**(2000), no. 231, 881–909. MR**1654026**, 10.1090/S0025-5718-99-01149-7**21.**Jinchao Xu and Aihui Zhou,*Local and parallel finite element algorithms based on two-grid discretizations for nonlinear problems*, Adv. Comput. Math.**14**(2001), no. 4, 293–327. MR**1865099**, 10.1023/A:1012284322811**22.**Jinchao Xu and Aihui Zhou,*A two-grid discretization scheme for eigenvalue problems*, Math. Comp.**70**(2001), no. 233, 17–25. MR**1677419**, 10.1090/S0025-5718-99-01180-1**23.**Jinchao Xu and Aihui Zhou,*Local and parallel finite element algorithms for eigenvalue problems*, Acta Math. Appl. Sin. Engl. Ser.**18**(2002), no. 2, 185–200. MR**2008551**, 10.1007/s102550200018

Retrieve articles in *Mathematics of Computation*
with MSC (2010):
65L15,
65N15,
65N25,
65N30,
65N55

Retrieve articles in all journals with MSC (2010): 65L15, 65N15, 65N25, 65N30, 65N55

Additional Information

**Xiaozhe Hu**

Affiliation:
Department of Mathematics, Zhejiang University, Yuquan Campus, Hangzhou, 310027, People’s Republic of China

Email:
huxiaozhezju@gmail.com

**Xiaoliang Cheng**

Affiliation:
Department of Mathematics, Zhejiang University, Yuquan Campus, Hangzhou, 310027, People’s Republic of China

Email:
xiaoliangcheng@zju.edu.cn

DOI:
https://doi.org/10.1090/S0025-5718-2011-02458-0

Keywords:
Eigenvalue problems,
finite elements,
partial differential equations,
integral equations,
two-grid method.

Received by editor(s):
October 21, 2009

Received by editor(s) in revised form:
June 15, 2010

Published electronically:
February 18, 2011

Additional Notes:
This work was supported in part by National Science Foundation of China (No. 10871179).

Article copyright:
© Copyright 2011
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication.