On the convergence of nonnested multigrid methods with nested spaces on coarse grids

Multigrid methods for discretized partial differential problems using nonnested conforming and nonconforming finite elements are here defined in the general setting. The coarse‐grid corrections of these multigrid methods make use of different finite element spaces from those on the finest grid. In general, the finite element spaces on the finest grid are nonnested, while the spaces are nested on the coarse grids. An abstract convergence theory is developed for these multigrid methods for differential problems without full elliptic regularity. This theory applies to multigrid methods of nonnested conforming and nonconforming finite elements with the coarse‐grid corrections established on nested conforming finite element spaces. Uniform convergence rates (independent of the number of grid levels) are obtained for both the V and W‐cycle methods with one smoothing on all coarse grids and with a sufficiently large number of smoothings solely on the finest grid. In some cases, these uniform rates are attained even with one smoothing on all grids. The present theory also applies to multigrid methods for discretized partial differential problems using mixed finite element methods. © 2000 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 16: 265–284, 2000     

Numerical inaccuracies across the interface of a nested grid

This article addresses and discusses the inaccuracies in finite differencing across the interface of a nested grid. Explicit schemes for the advection and diffusion equations are analyzed on the fine and coarse grids and reformulated at the interface to guarantee that the evolving solution is unaffected by the abrupt change of the spatial grid resolution. The associated errors are expressed as a function of the wavelength of the initial field distribution and the ratio between the coarse and fine grid resolution. It is found that large-scale features of the coarse grid must supply energy to sustain the small-scale features of the fine grid. To not deplete the large-scale motion, a source of energy must be given at the interface in the form of a computational diffusive term with negative viscosity coefficient. On the other hand, not all the energy of the small-scale features of the fine grid has to be transferred to the large-scale motion, but some of it needs to be computationally dissipated at the interface. © 1994 John Wiley & Sons, Inc.     

Option pricing with a direct adaptive sparse grid approach

We present an adaptive sparse grid algorithm for the solution of the Black–Scholes equation for option pricing, using the finite element method. Sparse grids enable us to deal with higher-dimensional problems better than full grids. In contrast to common approaches that are based on the combination technique, which combines different solutions on anisotropic coarse full grids, the direct sparse grid approach allows for local adaptive refinement. When dealing with non-smooth payoff functions, this reduces the computational effort significantly. In this paper, we introduce the spatially adaptive discretization of the Black–Scholes equation with sparse grids and describe the algorithmic structure of the numerical solver. We present several strategies for adaptive refinement, evaluate them for different dimensionalities, and demonstrate their performance showing numerical results.     

The Finite Difference Based Fast Adaptive Composite Grid Method

The fast adaptive composite grid (FAC) method is an iterative method for solving discrete boundary value problems on composite grids. McCormick introduced the method in [8] and considered the convergence behaviour for discrete problems resulting from finite volume element discretization on composite grids. In this paper we consider discrete problems resulting from finite difference discretization on composite grids. We distinguish between two obvious discretization approaches at the grid points on the interfaces between fine and coarse subgrids. The FAC method for solving such discrete problems is described. In the FAC method several intergrid transfer operators appear. We study how the convergence behaviour depends on these intergrid transfer operators. Based on theoretical insights, (quasi-)optimal intergrid transfer operators are derived. Numerical results illustrate the fast convergence of the FAC method using these intergrid transfer operators.     

Local and Parallel Finite Element Algorithms Based on Two-Grid Discretizations for Nonlinear Problems

In this paper, some local and parallel discretizations and adaptive finite element algorithms are proposed and analyzed for nonlinear elliptic boundary value problems in both two and three dimensions. The main technique is to use a standard finite element discretization on a coarse grid to approximate low frequencies and then to apply some linearized discretization on a fine grid to correct the resulted residual (which contains mostly high frequencies) by some local/parallel procedures. The theoretical tools for analyzing these methods are some local a priori and a posteriori error estimates for finite element solutions on general shape-regular grids that are also obtained in this paper.     

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

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

Finite difference simulation of elastic wave propagation through 3D heterogeneous multiscale media based on locally refined grids

To simulate the interaction of seismic waves with microheterogeneities (like cavernous/fractured reservoirs), a finite difference technique based on grids locally refined in time and space is used. These grids are used because the scales of heterogeneities in the reference medium and in the reservoir are different. Parallel computations based on domain decomposition of the target area into elementary subdomains in both the reference medium (a coarse grid) and the reservoir (a fine grid) are performed. Each subdomain is assigned to a specific processor unit, which forms two groups: one for the reference medium, and the other for the reservoir. The data exchange between the groups within a processor unit is performed by non-blocking iSend/iReceive MPI commands. The data exchange between the two groups is performed simultaneously with coupling the coarse and a fine grids, and is controlled by a specially chosen processor unit. The results of a numerical simulation for a realistic model of fracture corridors are presented and discussed.     

非定常的热传导-对流问题的非线性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.     

自适应多重网格法与超松弛法的比较

多重网格法(Multiple Grid Method,简称M-G方法)是近年来出现的快速方法之一,本文在M-G方法中采用自适应控制层间转换的技术,并将自适应M-G方法与G-S迭代方法及SOR迭代方,法进行了比较。其计算结果表明,自适应M-G方法的计算量比G-S迭代及SOR迭代少得多,当M-G方法所用层数为4-6层,这种优越性就更加明显,且自适应M-G方法中选取控制参数有很大的灵活性。     

Local and parallel finite element algorithms based on two-grid discretizations

A number of new local and parallel discretization and adaptive finite element algorithms are proposed and analyzed in this paper for elliptic boundary value problems. These algorithms are motivated by the observation that, for a solution to some elliptic problems, low frequency components can be approximated well by a relatively coarse grid and high frequency components can be computed on a fine grid by some local and parallel procedure. The theoretical tools for analyzing these methods are some local a priori and a posteriori estimates that are also obtained in this paper for finite element solutions on general shape-regular grids. Some numerical experiments are also presented to support the theory.

     

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.     

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     

Mortar multiscale finite element methods for Stokes–Darcy flows

We investigate mortar multiscale numerical methods for coupled Stokes and Darcy flows with the Beavers–Joseph–Saffman interface condition. The domain is decomposed into a series of subdomains (coarse grid) of either Stokes or Darcy type. The subdomains are discretized by appropriate Stokes or Darcy finite elements. The solution is resolved locally (in each coarse element) on a fine scale, allowing for non-matching grids across subdomain interfaces. Coarse scale mortar finite elements are introduced on the interfaces to approximate the normal stress and impose weakly continuity of the normal velocity. Stability and a priori error estimates in terms of the fine subdomain scale $h$ and the coarse mortar scale $H$ are established for fairly general grid configurations, assuming that the mortar space satisfies a certain inf-sup condition. Several examples of such spaces in two and three dimensions are given. Numerical experiments are presented in confirmation of the theory.     

地形构造中地震波传播的非对称交错网格模拟

提出了一种新的三维空间对称交错网格差分方法,模拟地形构造中弹性波传播过程．通过具有二阶时间精度和四阶空间精度的不规则网格差分算子用来近似一阶弹性波动方程,引入附加差分公式解决非均匀交错网格的不对称问题．该方法无需在精细网格和粗糙网格间进行插值,所有网格点上的计算在同一次空间迭代中完成．使用精细不规则网格处理海底粗糙界面、 断层和空间界面等复杂几何构造, 理论分析和数值算例表明, 该方法不但节省了大量内存和计算时间, 而且具有令人满意的稳定性和精度．在模拟地形构造中地震波传播时,该方法比常规方法效率更高．     

Barrier variational generation of quasi‐isometric grids

A grid generation method based on the minimization of the discrete barrier functional with feasible set consisting of quasi‐isometric grids is suggested. The deviation from isometry for given grid connectivity and prescribed boundary conditions is minimized via the contraction of the feasible set into a small vicinity of the optimal grid. Formulation of functional with given metrics in both physical and logical spaces allows to consider the adaptive grid generation in terms of quasi‐isometric grids and cover many practical applications. A fast and reliable grid untangling procedure based on the penalty‐like reformulation of barrier functional and the continuation technique is described. Numerical experiments demonstrate that the suggested functional produces high‐quality grids with small global condition numbers. Copyright © 2001 John Wiley & Sons, Ltd.     

Two-level method and some a priori estimates in unsteady Navier-Stokes calculations

A two-level method proposed for quasielliptic problems is adapted in this paper to the simulation of unsteady incompressible Navier-Stokes flows. The method requires a solution of a nonlinear problem on a coarse grid and a solution of linear symmetric problem on a fine grid, the scaling between these two grids is superlinear. Approximation, stability, and convergence aspects of a fully discrete scheme are considered. Stability properties of the two-level scheme are compared with those for a commonly used semi-implicit scheme, some new estimates are also proved for the latter.     

An interior point algorithm with inexact step computation in function space for state constrained optimal control

We consider an interior point method in function space for PDE constrained optimal control problems with state constraints. Our emphasis is on the construction and analysis of an algorithm that integrates a Newton path-following method with adaptive grid refinement. This is done in the framework of inexact Newton methods in function space, where the discretization error of each Newton step is controlled by adaptive grid refinement in the innermost loop. This allows to perform most of the required Newton steps on coarse grids, such that the overall computational time is dominated by the last few steps. For this purpose we propose an a-posteriori error estimator for a problem suited norm.     

Overlapping Schwarz methods on unstructured meshes using non-matching coarse grids

Summary. We consider two level overlapping Schwarz domain decomposition methods for solving the finite element problems that arise from discretizations of elliptic problems on general unstructured meshes in two and three dimensions. Standard finite element interpolation from the coarse to the fine grid may be used. Our theory requires no assumption on the substructures that constitute the whole domain, so the substructures can be of arbitrary shape and of different size. The global coarse mesh is allowed to be non-nested to the fine grid on which the discrete problem is to be solved, and neither the coarse mesh nor the fine mesh need be quasi-uniform. In addition, the domains defined by the fine and coarse grid need not be identical. The one important constraint is that the closure of the coarse grid must cover any portion of the fine grid boundary for which Neumann boundary conditions are given. In this general setting, our algorithms have the same optimal convergence rate as the usual two level overlapping domain decomposition methods on structured meshes. The condition number of the preconditioned system depends only on the (possibly small) overlap of the substructures and the size of the coarse grid, but is independent of the sizes of the subdomains. Received March 23, 1994 / Revised version received June 2, 1995     

Variational method for adaptive mesh generation

A variational method is suggested for generating adaptive grids composed of hexahedral cells. The method is based on the minimization of a functional written on a manifold in a space whose variables are usual spatial coordinates in a physical domain and the components of a monitor vector function. A grid is constructed in the manifold, and its projection onto the physical domain yields an adaptive grid. Examples of adaptive grid generation are given.