General theory of domain decomposition: Beyond Schwarz methods

Recently, Herrera presented a general theory of domain decomposition methods (DDM). This article is part of a line of research devoted to its further development and applications. According to it, DDM are classified into direct and indirect, which in turn can be subdivided into overlapping and nonoverlapping. Some articles dealing with general aspects of the theory and with indirect (Trefftz–Herrera) methods have been published. In the present article, a very general direct‐overlapping method, which subsumes Schwarz methods, is introduced. Also, this direct‐overlapping method is quite suitable for parallel implementation. © 2001 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 17: 495–517, 2001     

Comments on algorithms for grid interfaces in simulating Euler flows

Some results concerning the algorithms for grid interfaces, which are crucial in simulating flows by zonal methods, are presented in this paper. It is indicated that the commonly used conservative interface scheme can ensure the discrete entropy condition, but it may be inconsistent and would bring a nonoverlapping solution on overlapping grids. A nonconservative interface matching obtained by interpolation can be monotonicity preserving, and it leads large conservation error when discontinuities are close to the interfaces. Methods for improvement of interface algorithms are also proposed.     

A conforming finite element method for overlapping and nonmatching grids

In this paper we propose a finite element method for nonmatching overlapping grids based on the partition of unity. Both overlapping and nonoverlapping cases are considered. We prove that the new method admits an optimal convergence rate. The error bounds are in terms of local mesh sizes and they depend on neither the overlapping size of the subdomains nor the ratio of the mesh sizes from different subdomains. Our results are valid for multiple subdomains and any spatial dimensions.

     

DOMAIN DECOMPOSITION WITH NONMATCHING GRIDS FOR EXTERIOR TRANSMISSION PROBLEMS VIA FEM AND DTN MAPPING

In this paper, we are concerned with a non-overlapping domain decomposition method （DDM） for exterior transmission problems in the plane. Based on the natural boundary integral operator, we combine the DDM with a Dirichlet-to-Neumann （DtN） mapping and provide the numerical analysis with nonmatching grids. The weak continuity of the approximation solutions on the interface is imposed by a dual basis multiplier. We show that this multiplier space can generate optimal error estimate and obtain the corresponding rate of convergence. Finally, several numerical examples confirm the theoretical results.     

Overlapping grids for the diffusion equation

Yiqi Qiu ^{We examine the use of nonmatching, overlapping grids for theapproximate solution of time-dependent diffusion problems withNeumann boundary conditions. This problem arises as a modelof the so-called well test analysis of oil and gas reservoirs,which has geometry modelling requirements that make overlappinggrids particularly suitable. We describe the problem and theoverlapping grid approximation, and then carry out a stabilityand convergence analysis in one space dimension (1D). We showthat for suitable schemes, stability is relatively easy to establishin much more general situations. Convergence is less easy togeneralise, but we demonstrate that 2D approximations appearto have the same convergence behaviour as their 1D counterparts.}     

A linear system‐free Gaussian RBF method for the Gross‐Pitaevskii equation on unbounded domains

Gaussian radial basis function (RBF) interpolation methods are theoretically spectrally accurate. However, in applications this accuracy is seldom realized due to the necessity of solving a very poorly conditioned linear system to evaluate the methods. Recently, by using approximate cardinal functions and restricting the method to a uniformly spaced grid (or a smooth mapping thereof), it has been shown that the Gaussian RBF method can be formulated in a matrix free framework that does not involve solving a linear system [ 1 ]. In this work, we differentiate the linear system‐free Gaussian (LSFG) method and use it to solve partial differential equations on unbounded domains that have solutions that decay rapidly and that are negligible at the ends of the grid. As an application, we use the LSFG collocation method to numerically simulate Bose‐Einstein condensates. © 2010 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 28: 389–401, 2012     

Adaptive finite element approximations on nonmatching grids for second‐order elliptic problems

In this article we consider a finite element approximation for a model elliptic problem of second order on non‐matching grids. This method combines the continuous finite element method with interior penalty discontinuous Galerkin method. As a special case, we develop a finite element method that is continuous on the matching part of the grid and is discontinuous on the nonmatching part. A residual type a posteriori error estimate is derived. Results of numerical experiments are presented. © 2009 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 2010     

解单障碍问题的Lagrangian乘子非匹配网格区域分解法

针对二阶椭圆型单障碍问题提出了一类基于非匹配网格的Lagrang ian乘子非重叠型区域分解方法.并在适当条件下给出了该方法的收敛性分析和收敛速度估计.     

A Two-Grid Finite-Element Method for the Nonlinear Schrödinger Equation

In this paper, some two-grid finite element schemes are constructed for solving the nonlinear Schrödinger equation. With these schemes, the solution of the original problem is reduced to the solution of the same problem on a much coarser grid together with the solutions of two linear problems on a fine grid. We have shown, both theoretically and numerically, that our schemes are efficient and achieve asymptotically optimal accuracy.     

The comparison between the DRBEM and DQM solution of nonlinear reaction–diffusion equation

In this study, both the dual reciprocity boundary element method and the differential quadrature method are used to discretize spatially, initial and boundary value problems defined by single and system of nonlinear reaction–diffusion equations. The aim is to compare boundary only and a domain discretization method in terms of accuracy of solutions and computational cost. As the time integration scheme, the finite element method is used achieving solution in terms of time block with considerably large time steps. The comparison between the dual reciprocity boundary element method and the differential quadrature method solutions are made on some test problems. The results show that both methods achieve almost the same accuracy when they are combined with finite element method time discretization. However, as a method providing very good accuracy with considerably small number of grid points differential quadrature method is preferrable.     

Indirect methods of collocation: Trefftz‐Herrera collocation

A nonstandard collocation method (TH‐collocation) is presented, where collocation is used to construct specialized weighting functions instead of the solution itself, as it is usual, so that in this sense it is an indirect method. TH‐collocation is shown to be as accurate as standard collocation, but computationally far more efficient. The present article is the first of a series devoted to explore thoroughly collocation methods. The following classification of collocation methods is introduced: direct‐nonoverlapping; indirect‐nonoverlapping; direct‐overlapping; and indirect‐overlapping. Most of the effort reported in the literature has gone to direct‐nonoverlapping methods. The procedure presented in this article falls into the indirect‐nonoverlapping category and it is based on Trefftz‐Herrera formulation. © 1999 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 15: 709–738, 1999     

A comparison result for multisplittings and waveform relaxation methods

We show that certain multisplitting iterative methods based on overlapping blocks yield faster convergence than corresponding nonoverlapping block iterations, provided the coefficient matrix is an M-matrix. This result can be used to compare variants of the waveform relaxation algorithm for solving initial value problems. The methods under consideration use the same discretization technique, but are based on multisplittings with different overlaps. Numerical experiments on the Intel iPSC/860 hypercube are included.     

A symmetric integrated radial basis function method for solving differential equations

In this article, integrated radial basis functions (IRBFs) are used for Hermite interpolation in the solution of differential equations, resulting in a new meshless symmetric RBF method. Both global and local approximation‐based schemes are derived. For the latter, the focus is on the construction of compact approximation stencils, where a sparse system matrix and a high‐order accuracy can be achieved together. Cartesian‐grid‐based stencils are possible for problems defined on nonrectangular domains. Furthermore, the effects of the RBF width on the solution accuracy for a given grid size are fully explored with a reasonable computational cost. The proposed schemes are numerically verified in some elliptic boundary‐value problems governed by the Poisson and convection‐diffusion equations. High levels of the solution accuracy are obtained using relatively coarse discretisations.     

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).     

Linear and nonlinear substructured Restricted Additive Schwarz iterations and preconditioning

Iterative substructuring Domain Decomposition (DD) methods have been extensively studied, and they are usually associated with nonoverlapping decompositions. It is less known that classical overlapping DD methods can also be formulated in substructured form, i.e., as iterative methods acting on variables defined exclusively on the interfaces of the overlapping domain decomposition. We call such formulations substructured domain decomposition methods. We introduce here a substructured version of Restricted Additive Schwarz (RAS) which we call SRAS. We show that RAS and SRAS are equivalent when used as iterative solvers, as they produce the same iterates, while they are substantially different when used as preconditioners for GMRES. We link the volume and substructured Krylov spaces and show that the iterates are different by deriving the least squares problems solved at each GMRES iteration. When used as iterative solvers, SRAS presents computational advantages over RAS, as it avoids computations with matrices and vectors at the volume level. When used as preconditioners, SRAS has the further advantage of allowing GMRES to store smaller vectors and perform orthogonalization in a lower dimensional space. We then consider nonlinear problems, and we introduce SRASPEN (Substructured Restricted Additive Schwarz Preconditioned Exact Newton), where SRAS is used as a preconditioner for Newton’s method. In contrast to the linear case, we prove that Newton’s method applied to the preconditioned volume and substructured formulation produces the same iterates in the nonlinear case. Next, we introduce two-level versions of nonlinear SRAS and SRASPEN. Finally, we validate our theoretical results with numerical experiments.

     

A discontinuous Galerkin method with nonoverlapping domain decomposition for the Stokes and Navier-Stokes problems

A family of discontinuous Galerkin finite element methods is formulated and analyzed for Stokes and Navier-Stokes problems. An inf-sup condition is established as well as optimal energy estimates for the velocity and estimates for the pressure. In addition, it is shown that the method can treat a finite number of nonoverlapping domains with nonmatching grids at interfaces.

     

Preconditioning for radial basis functions with domain decomposition methods

In our previous work, an effective preconditioning scheme that is based upon constructing least-squares approximation cardinal basis functions (ACBFs) from linear combinations of the RBF-PDE matrix elements has shown very attractive numerical results. The preconditioner costs O(N²) flops to set up and O(N) storage. The preconditioning technique is sufficiently general that it can be applied to different types of different operators. This was applied to the 2D multiquadric method, with c~1/√N on the Poisson test problem, the preconditioned GMRES converges in tens of iterations. In this paper, we combine the RBF methods and the ACBF preconditioning technique with the domain decomposition method (DDM). We studied different implementations of the ACBF-DDM scheme and provide numerical results for N > 10,000 nodes. We shall demonstrate that the efficiency of the ACBF-DDM scheme improves dramatically as successively finer partitions of the domain are considered.     

A general effective method for combining collocation and DDM: An application of discontinuous Galerkin methods

Domain decomposition methods (DDM) have received much attention in recent years. They constitute the most effective means of using parallel computing resources to model continuous systems. However, combining collocation procedures with domain decomposition methods presents complications that must be overcome in order to profit from the advantages of parallel computing. The present paper belongs to a line of research in which a theory that constitutes a general and systematic formulation of discontinuous Galerkin methods (dG) is being investigated. Based on it, a new method of collocation of general applicability, TH‐collocation, was recently introduced. For a broad class of symmetric and positive continuous systems, TH‐collocation yields symmetric and positive matrices. This clears the way for applying effectively DDM and parallel computing, in combination with collocation, to such systems. In this paper the general procedure is explained with some detail and then is applied to develop an effective method for processing elliptic equations of second order. This, by the way, overcomes the difficulties encountered in a previous Herrera and Pinder's article. © 2004 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2005.     

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     

有限元法中大单元的构造

在通常的有限元法中,单元内的插值多项式的阶数固定不变,通过加密剖分网格来提高精度.大单元法则剖分的网格固定不变而通过增加单元内逼近级数的项数来提高精度. 本文提出采用两套变量的办法来构造大单元,即单元内采用一套变量,单元的边界上采用另一套变量,然后用杂交罚函数法把两者联系起来.这种方法能适用于任何椭圆型方程,任意几何形状区域以及任何复杂的边界条件.本文用严密的数学方法证明了:在一般情况下,这种方法的精度比通常的有限元法和文[7]的大单元法高得多.即在达到相同的精度时,本文方法所需要的自由度(即未知数数目)比上述两种方法少得多.