A two-grid discretization scheme for eigenvalue problems

A two-grid discretization scheme is proposed for solving eigenvalue problems, including both partial differential equations and integral equations. With this new scheme, the solution of an eigenvalue problem on a fine grid is reduced to the solution of an eigenvalue problem on a much coarser grid, and the solution of a linear algebraic system on the fine grid and the resulting solution still maintains an asymptotically optimal accuracy.

     

A two-grid discretization scheme for the Steklov eigenvalue problem

In the paper, a two-grid discretization scheme is discussed for the Steklov eigenvalue problem. With the scheme, the solution of the Steklov eigenvalue problem on a fine grid is reduced to the solution of the Steklov eigenvalue problem on a much coarser grid and the solution of a linear algebraic system on the fine grid. Using spectral approximation theory, it is shown theoretically that the two-scale scheme is efficient and the approximate solution obtained by the scheme maintains the asymptotically optimal accuracy. Finally, numerical experiments are carried out to confirm the considered theory.     

非定常的热传导-对流问题的非线性Galerkin混合元法(Ⅱ):向后一步的Euler全离散化格式

1．引言本文的工作主要是讨论非定常的热传导一对流问题的向后一步的Euler全离散化的非线性Galerkin混合元解的存在性及其误差估计．该工作是对山中的同一问题研究的第二部分．在第一部分［1］，我们已经讨论了此问题的半离散化的情形．由于所研究的目标都是非定常的热传导一对流问题，其背景是相同的，在此将不重复了，请参考［1］．本文的安排如下，52先回顾非定常的热传导一对流问题的混合元解的经典性质．53回顾半离散化的非线性Galerkin混合元解的性质，并导出后续讨论需要的一些关于时间导数的估计．54讨论向后一步的Euler全离散化…     

Three-scale finite element eigenvalue discretizations

Some three-scale finite element discretization schemes are proposed and analyzed in this paper for a class of elliptic eigenvalue problems on tensor product domains. With these schemes, the solution of an eigenvalue problem on a fine grid may be reduced to the solutions of eigenvalue problems on a relatively coarse grid and some partially mesoscopic grids, together with the solutions of linear algebraic systems on a globally mesoscopic grid and several partially fine grids. It is shown theoretically and numerically that this type of discretization schemes not only significantly reduce the number of degrees of freedom but also produce very accurate approximations. AMS subject classification (2000)  65N15, 65N25, 65N30, 65N50     

非定常的热传导-对流问题的非线性Galerkin混合元法(Ⅱ):向后一步的Euler全离散化格式

In this paper, a fully discrete format of nonlinear Galerkin mixed element method with backward one-step Euler discretization of time for the non stationary conduction-convection problems is presented. The scheme is based on two finite element spaces XH and Xh for the approximation of the velocity, defined respectively on a coarse grid with grids size H and another fine grid with grid size h<< H, a finite element space Mh for the approximation of the pressure and two finite element spaces AH and Wh, for the approximation of the temperature,also defined respectivply on the coarse grid with grid size H and another fine grid with grid size h. The existence and the convergence of the fully discrete mixed element solution are shown. The scheme consists in using standard backward one step Euler-Galerkin fully discrete format at first L0 steps (L0 2) on fine grid with grid size h, but using nonlinear Galerkin mixed element method of backward one step Euler-Galerkin fully discrete format through L0 + 1 step to end step. We have proved that the fully discrete nonlinear Galerkin mixed element procedure with respect to the coarse grid spaces with grid size H holds superconvergence.     

A posteriori error control for finite element approximations of elliptic eigenvalue problems

We develop a new approach to a posteriori error estimation for Galerkin finite element approximations of symmetric and nonsymmetric elliptic eigenvalue problems. The idea is to embed the eigenvalue approximation into the general framework of Galerkin methods for nonlinear variational equations. In this context residual-based a posteriori error representations are available with explicitly given remainder terms. The careful evaluation of these error representations for the concrete situation of an eigenvalue problem results in a posteriori error estimates for the approximations of eigenvalues as well as eigenfunctions. These suggest local error indicators that are used in the mesh refinement process.     

Comparison of the finite difference and Galerkin methods as applied to the solution of the hydrodynamic equations

The three-dimensional nonlinear hydrodynamic equations which describe wind induced flow in a homogeneous sea are transformed from Cartesian coordinates into sigma coordinates. The solution of these equations in the horizontal is accomplished using a standard finite difference grid and established finite difference methods.The accuracy and computational efficiency, in terms of both computer time and main memory requirements, of using either the Galerkin method or a finite difference grid through the vertical is considered. Calculations, using the same number of functions in the Galerkin method as grid bases through the vertical shows that the Galerkin method has superior accuracy over the grid box method. Hence, for a given accuracy a smaller number of functions than grid boxes may be used, with associated saving in computational resources.For the case in which the vertical variation of eddy viscosity is fixed, an eigenvalue problem can be solved to yield a set of eigenfunctions. Using these eigenfunctions as a basis set with the Galerkin approach, a Galerkin-eigenfunction method is developed. Calculations show that the Galerkin-eigenfunction technique is accurate and in a linear model is clearly computationally more economic than the use of grid boxes through the vertical.     

TWO-GRID DISCRETIZATION SCHEMES OF THE NONCONFORMING FEM FOR EIGENVALUE PROBLEMS

This paper extends the two-grid discretization scheme of the conforming finite elements proposed by Xu and Zhou （Math. Comput., 70 （2001）, pp.17-25） to the nonconforming finite elements for eigenvalue problems. In particular, two two-grid discretization schemes based on Rayleigh quotient technique are proposed. By using these new schemes, the solution of an eigenvalue problem on a fine mesh is reduced to that on a much coarser mesh together with the solution of a linear algebraic system on the fine mesh. The resulting solution still maintains an asymptotically optimal accuracy. Comparing with the two-grid discretization scheme of the conforming finite elements, the main advantages of our new schemes are twofold when the mesh size is small enough. First, the lower bounds of the exact eigenvalues in our two-grid discretization schemes can be obtained. Second, the first eigenvalue given by the new schemes has much better accuracy than that obtained by solving the eigenvalue problems on the fine mesh directly.     

Acceleration of two-grid stabilized mixed finite element method for the Stokes eigenvalue problem

This paper provides an accelerated two-grid stabilized mixed finite element scheme for the Stokes eigenvalue problem based on the pressure projection. With the scheme, the solution of the Stokes eigenvalue problem on a fine grid is reduced to the solution of the Stokes eigenvalue problem on a much coarser grid and the solution of a linear algebraic system on the fine grid. By solving a slightly different linear problem on the fine grid, the new algorithm significantly improves the theoretical error estimate which allows a much coarser mesh to achieve the same asymptotic convergence rate. Finally, numerical experiments are shown to verify the high efficiency and the theoretical results of the new method.     

Local and Parallel Finite Element Algorithms for Eigenvalue Problems

Abstract Some new local and parallel finite element algorithms are proposed and analyzed in this paper foreigenvalue problems.With these algorithms, the solution of an eigenvalue problem on a fine grid is reduced tothe solution of an eigenvalue problem on a relatively coarse grid together with solutions of some linear algebraicsystems on fine grid by using some local and parallel procedure.A theoretical tool for analyzing these algorithmsis some local error estimate that is also obtained in this paper for finite element approximations of eigenvectorson general shape-regular grids.     

Two-grid methods for characteristic finite volume element solution of semilinear convection-diffusion equations

Two-grid methods for characteristic finite volume element solutions are presented for a kind of semilinear convection-dominated diffusion equations. The methods are based on the method of characteristics, two-grid method and the finite volume element method. The nonsymmetric and nonlinear iterations are only executed on the coarse grid (with grid size H). And the fine-grid solution (with grid size h) can be obtained by a single symmetric and linear step. It is proved that the coarse grid can be much coarser than the fine grid. The two-grid methods achieve asymptotically optimal approximation as long as the mesh sizes satisfy H = O(h^1/3).     

Higher order convergence results for the Rayleigh-Ritz method applied to eigenvalue problems: 2. Improved error bounds for eigenfunctions

The application of the Rayleigh-Ritz method for approximating the eigenvalues and eigenfunctions of linear eigenvalue problems in several dimensions is investigated. The object is to improve upon known error estimates for the approximate eigenfunctions. Results for the Galerkin approximation of the eigenfunctions are developed under varying assumptions on the boundary conditions and domain of definition of the eigenvalue problem. These results, coupled with a previous result relating Galerkin and Rayleigh-Ritz approximation of the eigenfunctions, are then used to obtain improved error estimates for the approximate eigenfunctions in theL ² and uniform norms.This research was supported in part by AEC Grant (11-1)-2075.     

A TWO-LEVEL FINITE ELEMENT GALERKIN METHOD FOR THE NONSTATIONARY NAVIER-STOKES EQUATIONS I： SPATIAL DISCRETIZATION

In this article we consider a two-level finite element Galerkin method using mixed finite elements for the two-dimensional nonstationary incompressible Navier-Stokes equations. The method yields a $H^1$-optimal velocity approximation and a $L_2$-optimal pressure approximation. The two-level finite element Galerkin method involves solving one small, nonlinear Navier-Stokes problem on the coarse mesh with mesh size $H$, one linear Stokes problem on the fine mesh with mesh size $h << H$. The algorithm we study produces an approximate solution with the optimal, asymptotic in $h$, accuracy.     

Multigrid transfers for nonsymmetric systems based on Schur complements and Galerkin projections

A framework is proposed for constructing algebraic multigrid transfer operators suitable for nonsymmetric positive definite linear systems. This framework follows a Schur complement perspective as this is suitable for both symmetric and nonsymmetric systems. In particular, a connection between algebraic multigrid and approximate block factorizations is explored. This connection demonstrates that the convergence rate of a two‐level model multigrid iteration is completely governed by how well the coarse discretization approximates a Schur complement operator. The new grid transfer algorithm is then based on computing a Schur complement but restricting the solution space of the corresponding grid transfers in a Galerkin‐style so that a far less expensive approximation is obtained. The final algorithm corresponds to a Richardson‐type iteration that is used to improve a simple initial prolongator or a simple initial restrictor. Numerical results are presented illustrating the performance of the resulting algebraic multigrid method on highly nonsymmetric systems. Copyright © 2013 John Wiley & Sons, Ltd.     

求解半线性抛物问题的两种二重网格算法

用线性方法对半线性抛物问题进行求解。方法依赖粗、细二重网格,针对粗解在细网格上的修正提出了两种算法,算法1是乘积倍的增长精度而算法2是平方倍的增长精度,而且重复算法1、2的最后几步可以任意阶地逼近细网格上的非线性解。数值算例验证了算法的可行性和有效性。     

A nonstandard multigrid method with flexible multiple semicoarsening for the numerical solution of the pressure equation in a Navier-Stokes solver

Numerical methods for the incompressible Reynolds-averaged Navier-Stokes equations discretized by finite difference techniques on collocated cell-centered structured grids are considered in this paper. A widespread solution method to solve the pressure-velocity coupling problem is to use a segregated approach, in which the computational work is deeply controlled by the solution of the pressure problem. This pressure equation is an elliptic partial differential equation with possibly discontinuous or anisotropic coeffficients. The resulting singular linear system needs efficient solution strategies especially for 3-dimensional applications. A robust method (close to MG-S [22,34]) combining multiple cell-centered semicoarsening strategies, matrix-independent transfer operators, Galerkin coarse grid approximation is therefore designed. This strategy is both evaluated as a solver or as a preconditioner for Krylov subspace methods on various 2- or 3-dimensional fluid flow problems. The robustness of this method is shown. This revised version was published online in June 2006 with corrections to the Cover Date.     

An overlapping domain decomposition preconditioner for a class of discontinuous Galerkin approximations of advection-diffusion problems

We consider a scalar advection-diffusion problem and a recently proposed discontinuous Galerkin approximation, which employs discontinuous finite element spaces and suitable bilinear forms containing interface terms that ensure consistency. For the corresponding sparse, nonsymmetric linear system, we propose and study an additive, two-level overlapping Schwarz preconditioner, consisting of a coarse problem on a coarse triangulation and local solvers associated to a family of subdomains. This is a generalization of the corresponding overlapping method for approximations on continuous finite element spaces. Related to the lack of continuity of our approximation spaces, some interesting new features arise in our generalization, which have no analog in the conforming case. We prove an upper bound for the number of iterations obtained by using this preconditioner with GMRES, which is independent of the number of degrees of freedom of the original problem and the number of subdomains. The performance of the method is illustrated by several numerical experiments for different test problems using linear finite elements in two dimensions.

     

A theory of discretization for nonlinear evolution inequalities applied to parabolic Signorini problems

We present a discretization theory for a class of nonlinear evolution inequalities that encompasses time dependent monotone operator equations and parabolic variational inequalities. This discretization theory combines a backward Euler scheme for time discretization and the Galerkin method for space discretization. We include set convergence of convex subsets in the sense of Glowinski-Mosco-Stummel to allow a nonconforming approximation of unilateral constraints. As an application we treat parabolic Signorini problems involving the p-Laplacian, where we use standard piecewise polynomial finite elements for space discretization. Without imposing any regularity assumption for the solution we establish various norm convergence results for piecewise linear as well piecewise quadratic trial functions, which in the latter case leads to a nonconforming approximation scheme. Entrata in Redazione il 16 marzo 1998, in versione riveduta il 15 febbraio 1999.     

Modification of basis functions in high order discontinuous Galerkin schemes for advection equation

High order discontinuous Galerkin (DG) discretization schemes are considered for an advection boundary-value problem on 2-D unstructured grids with arbitrary geometry of grid cells. A number of test cases are developed to study the sensitivity of a high order DG scheme to local grid distortion. It will be demonstrated how to modify the formulation of a DG discretization for the advection equation. Our approach allows one to maintain the required accuracy on distorted grids while using a fewer number of basis functions for the solution approximation in order to save computational resources.     

Spectral corrections for Sturm–Liouville problems

The numerical solution of the Sturm–Liouville problem can be achieved using shooting to obtain an eigenvalue approximation as a solution of a suitable nonlinear equation and then computing the corresponding eigenfunction. In this paper we use the shooting method both for eigenvalues and eigenfunctions. In integrating the corresponding initial value problems we resort to the boundary value method. The technique proposed seems to be well suited to supplying a general formula for the global discretization error of the eigenfunctions depending on the discretization errors arising from the numerical integration of the initial value problems. A technique to estimate the eigenvalue errors is also suggested, and seems to be particularly effective for the higher-index eigenvalues. Numerical experiments on some classical Sturm–Liouville problems are presented.