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     

非匹配网格上Stokes-Darcy 问题非协调元离散的两水平和多水平方法

本文讨论了非匹配网格上Stokes-Darcy 问题的两种低阶非协调元方法, 给出了误差估计, 对耦合的非协调元离散问题, 通过粗网格求得的界面条件, 我们提出了一个解耦的两水平算法. 并且我们将两水平方法推广到多水平情形, 其只需在一个很粗的网格上解一耦合问题, 然后在逐步加细的网格上求解解耦的问题, 理论分析和数值试验都说明方法的高效性.     

Robust iterative methods for elliptic problems with highly varying coefficients in thin substructures

Summary. In this paper we introduce a class of robust multilevel interface solvers for two-dimensional finite element discrete elliptic problems with highly varying coefficients corresponding to geometric decompositions by a tensor product of strongly non-uniform meshes. The global iterations convergence rate is shown to be of the order with respect to the number of degrees of freedom on the single subdomain boundaries, uniformly upon the coarse and fine mesh sizes, jumps in the coefficients and aspect ratios of substructures. As the first approach, we adapt the frequency filtering techniques [28] to construct robust smoothers on the highly non-uniform coarse grid. As an alternative, a multilevel averaging procedure for successive coarse grid correction is proposed and analyzed. The resultant multilevel coarse grid preconditioner is shown to have (in a two level case) the condition number independent of the coarse mesh grading and jumps in the coefficients related to the coarsest refinement level. The proposed technique exhibited high serial and parallel performance in the skin diffusion processes modelling [20] where the high dimensional coarse mesh problem inherits a strong geometrical and coefficients anisotropy. The approach may be also applied to magnetostatics problems as well as in some composite materials simulation. Received December 27, 1994     

Additive Schwarz domain decomposition methods for elliptic problems on unstructured meshes

We give several additive Schwarz domain decomposition methods for solving finite element problems which arise from the discretizations of elliptic problems on general unstructured meshes in two and three dimensions. Our theory requires no assumption (for the main results) on the substructures which constitute the whole domain, so each substructure 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 both the coarse meshes and the fine meshes need not be quasi-uniform. In this general setting, our algorithms have the same optimal convergence rate of the usual domain decomposition methods on structured meshes. The condition numbers of the preconditioned systems depend only on the (possibly small) overlap of the substructures and the size of the coares grid, but is independent of the sizes of the subdomains.Revised version on Sept. 20, 1994. Original version: CAM Report 93-40, Dec. 1993, Dept. of Math., UCLA.The work of this author was partially supported by the National Science Foundation under contract ASC 92-01266, the Army Research Office under contract DAAL03-91-G-0150, and ONR under contract ONR-N00014-92-J-1890.The work of this author was partially supported by the National Science Foundation under contract ASC 92-01266, the Army Research Office under contract DAAL03-91-G-0150, and subcontract DAAL03-91-C-0047.     

A domain decomposition preconditioner for hermite collocation problems

We propose a preconditioning method for linear systems of equations arising from piecewise Hermite bicubic collocation applied to two‐dimensional elliptic PDEs with mixed boundary conditions. We construct an efficient, parallel preconditioner for the GMRES method. The main contribution of the article is a novel interface preconditioner derived in the framework of substructuring and employing a local Hermite collocation discretization for the interface subproblems based on a hybrid fine‐coarse mesh. Interface equations based on this mesh depend only weakly on unknowns associated with subdomains. The effectiveness of the proposed method is highlighted by numerical experiments that cover a variety of problems. © 2003 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 19: 135–151, 2003     

TWO-GRID CHARACTERISTIC FINITE VOLUME METHODS FOR NONLINEAR PARABOLIC PROBLEMS＊

In this work, two-grid characteristic finite volume schemes for the nonlinear parabolic problem are considered. In our algorithms, the diffusion term is discretized by the finite volume method, while the temporal differentiation and advection terms are treated by the characteristic scheme. Under some conditions about the coefficients and exact solution, optimal error estimates for the numerical solution are obtained. Furthermore, the two- grid characteristic finite volume methods involve solving a nonlinear equation on coarse mesh with mesh size H, a large linear problem for the Oseen two-grid characteristic finite volume method on a fine mesh with mesh size h = O（H2） or a large linear problem for the Newton two-grid characteristic finite volume method on a fine mesh with mesh size h = 0（I log hll/2H3）. These methods we studied provide the same convergence rate as that of the characteristic finite volume method, which involves solving one large nonlinear problem on a fine mesh with mesh size h. Some numerical results are presented to demonstrate the efficiency of the proposed methods.     

非嵌套网格上的Morley元两水平加性Schwarz方法

1．引言设0是RZ中的有界多边形区域，其边界为Rfl．考虑下面的重调和Dirichlet问题：（1．1）的变分形式为：求。EHI（fi）使得对？／EL‘（m，问题（1．幻的唯一可解性可由冯（m上的M线性型的强制性和连续性以及La。Mlgram定理得出（of［4］）．令人一｛丸）是n的一个三角剖分，并且满足最小角条件，其中h是它的网格参数．设Vh为Money元空间［41．问题（1．2）的有限元离散问题为：求。eVh使得当有限元参数人很小时，这个方程组很大，而且矩阵A的条件数变得非常大，直接求解，存贮量及计算量都很大．如果B可逆，则方程组（1．4）等…     

The finite element method for parabolic equations

Summary In this first of two papers, computable a posteriori estimates of the space discretization error in the finite element method of lines solution of parabolic equations are analyzed for time-independent space meshes. The effectiveness of the error estimator is related to conditions on the solution regularity, mesh family type, and asymptotic range for the mesh size. For clarity the results are limited to a model problem in which piecewise linear elements in one space dimension are used. The results extend straight-forwardly to systems of equations and higher order elements in one space dimension, while the higher dimensional case requires additional considerations. The theory presented here provides the basis for the analysis and adaptive construction of time-dependent space meshes, which is the subject of the second paper. Computational results show that the approach is practically very effective and suggest that it can be used for solving more general problems.The work was partially supported by ONR Contract N00014-77-C-0623     

Numerical modeling of 1D transient poroelastic waves in the low-frequency range

Propagation of transient mechanical waves in porous media is numerically investigated in 1D. The framework is the linear Biot model with frequency-independent coefficients. The coexistence of a propagating fast wave and a diffusive slow wave makes numerical modeling tricky. A method combining three numerical tools is proposed: a fourth-order ADER scheme with time-splitting to deal with the time-marching, a space-time mesh refinement to account for the small-scale evolution of the slow wave, and an interface method to enforce the jump conditions at interfaces. Comparisons with analytical solutions confirm the validity of this approach.     

An ultra-weak method for acoustic fluid–solid interaction

We introduce the ultra-weak variational formulation (UWVF) for fluid–solid vibration problems. In particular, we consider the scattering of time-harmonic acoustic pressure waves from solid, elastic objects. The problem is modeled using a coupled system of the Helmholtz and Navier equations. The transmission conditions on the fluid–solid interface are represented in an impedance-type form after which we can employ the well known ultra-weak formulations for the Helmholtz and Navier equations. The UWVF approximation for both equations is computed using a superposition of propagating plane waves. A condition number based criterion is used to define the plane wave basis dimension for each element. As a model problem we investigate the scattering of sound from an infinite elastic cylinder immersed in a fluid. A comparison of the UWVF approximation with the analytical solution shows that the method provides a means for solving wave problems on relatively coarse meshes. However, particular care is needed when the method is used for problems at frequencies near the resonance frequencies of the fluid–solid system.     

Two grid discretizations with backtracking of the stream function form of the Navier-Stokes equations

We analyze a two grid finite element method with backtracking for the stream function formulation of the stationary Navier—Stokes equations. This two grid method involves solving one small, nonlinear coarse mesh system, one linearized system on the fine mesh and one linear correction problem on the coarse mesh. The algorithm and error analysis are presented.     

Navier-Stokes方程流函数形式两重网格算法的误差分析

对定常Navier-Stokes方程流函数形式两重网格有限元算法进行了误差分析。此方法包括在粗网格上求解一个非线性问题，在细网格上求解一个线性问题，然后再在粗网格上求解一个线性校正问题。分析了包括校正项和不包括校正项两种方法的误差，得出对于任意固定的Beynolds数，能达到最优逼近阶。     

热传导-对流问题的回溯二重水平法

该文给出定常的热传导-对流问题的有限元逼近的一种二重水平方法. 这种二重水平方法包括解一个小的非线性的粗网格系统、一个细网格上的线性Oseen问题和一个粗网格上的线性校正问题. 同时,给出了这种近似解的存在性和收敛性分析.     

A new method based on SOM network to generate coarse meshes for overlapping unstructured multigrid algorithm

A new method to generate coarse meshes for overlapping unstructured multigrid algorithm based on self-organizing map (SOM) neural network is presented in this paper. The application of SOM neural network can overcome some limitations of conventional methods and which is designed to pursuit the best structure relation between fine and coarse unstructured meshes with the object to ensure robust convergence for overlapping unstructured multigrid algorithm. Besides, this method can automate the generation of unstructured meshes and is suitable for both two and three dimensions conditions.     

A convergence theory of multilevel additive Schwarz methods on unstructured meshes

We develop a convergence theory for two level and multilevel additive Schwarz domain decomposition methods for elliptic and parabolic problems on general unstructured meshes in two and three dimensions. The coarse and fine grids are assumed only to be shape regular, and the domains formed by the coarse and fine grids need not be identical. In this general setting, our convergence theory leads to completely local bounds for the condition numbers of two level additive Schwarz methods, which imply that these condition numbers are optimal, or independent of fine and coarse mesh sizes and subdomain sizes if the overlap amount of a subdomain with its neighbors varies proportionally to the subdomain size. In particular, we will show that additive Schwarz algorithms are still very efficient for nonselfadjoint parabolic problems with only symmetric, positive definite solvers both for local subproblems and for the global coarse problem. These conclusions for elliptic and parabolic problems improve our earlier results in [12, 15, 16]. Finally, the convergence theory is applied to multilevel additive Schwarz algorithms. Under some very weak assumptions on the fine mesh and coarser meshes, e.g., no requirements on the relation between neighboring coarse level meshes, we are able to derive a condition number bound of the orderO(² L ²), where = max₁lL(h _l +_l– 1)/ _l,h _l is the element size of thelth level mesh, _l the overlap of subdomains on thelth level mesh, andL the number of mesh levels.The work was partially supported by the NSF under contract ASC 92-01266, and ONR under contract ONR-N00014-92-J-1890. The second author was also partially supported by HKRGC grants no. CUHK 316/94E and the Direct Grant of CUHK.     

Navier-Stokes方程带Backtracking技巧的两重网格算法

1 引 言考虑二维不可压 Navier-Stokes方程:     

Two-grid finite volume element method for linear and nonlinear elliptic problems

Two-grid finite volume element discretization techniques, based on two linear conforming finite element spaces on one coarse and one fine grid, are presented for the two-dimensional second-order non-selfadjoint and indefinite linear elliptic problems and the two-dimensional second-order nonlinear elliptic problems. With the proposed techniques, solving the non-selfadjoint and indefinite elliptic problem on the fine space is reduced into solving a symmetric and positive definite elliptic problem on the fine space and solving the non-selfadjoint and indefinite elliptic problem on a much smaller space; solving a nonlinear elliptic problem on the fine space is reduced into solving a linear problem on the fine space and solving the nonlinear elliptic problem on a much smaller space. Convergence estimates are derived to justify the efficiency of the proposed two-grid algorithms. A set of numerical examples are presented to confirm the estimates. The work is supported by the National Natural Science Foundation of China (Grant No: 10601045).     

Self-adaptive FEM numerical modeling of the mild-slope equation

Based on the linear wave theory, the mild-slope equation (MSE) is a preferred mathematical model to simulate nearshore wave propagation. A numerical model to solve the MSE is developed here on the basis of a self-adaptive finite element model (FEM) combined with an iterative method to determine the wave direction angle to the boundary and thus to improve the treatment of the boundary conditions. The numerical resolution of the waves into ideal domains and multidirectional waves through a breakwater gap shows that the numerical model developed here is effective in representing wave absorption at the absorbing boundaries and can be used to simulate multidirectional wave propagation. Finally, the simulated wave distribution in a real harbor shows that the numerical model can be used for engineering practice.     

Two-grid Methods for Finite Volume Element Approximations of Nonlinear Sobolev Equations

In this article, two-grid methods are studied for solving nonlinear Sobolev equation using the finite volume element method. The methods are based on one coarse grid space and one fine grid space. 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 in a single symmetric and linear step. The optimal H¹ error estimates are presented for the proposed methods, which show that the two-grid methods achieve optimal approximation as long as the mesh sizes satisfy h = 𝒪(H³|ln H|). As a result, solving such a large class of nonlinear Sobolev equations will not be much more difficult than solving one linearized equation.     

Graded Meshes for Higher Order FEM

A singularly perturbed one-dimensional convection-diffusion problem is solved numerically by the finite element method based on higher order polynomials. Numerical solutions are obtained using S-type meshes with special emphasis on meshes which are graded (based on a mesh generating function) in the fine mesh region. Error estimates in the ε-weighted energy norm are proved. We derive an 'optimal' mesh generating function in order to minimize the constant in the error estimate. Two layer-adapted meshes defined by a recursive formulae in the fine mesh region are also considered and a new technique for proving error estimates for these meshes is presented. The aim of the paper is to emphasize the importance of using optimal meshes for higher order finite element methods. Numerical experiments support all theoretical results.