Stochastic Domain Decomposition for Time Dependent Adaptive Mesh Generation

The efficient generation of meshes is an important component in the numerical solution of problems in physics and engineering. Of interest are situations where global mesh quality and a tight coupling to the solution of the physical partial differential equation (PDE) is important. We consider parabolic PDE mesh generation and present a method for the construction of adaptive meshes in two spatial dimensions using stochastic domain decomposition that is suitable for an implementation in a multi- or many-core environment. Methods for mesh generation on periodic domains are also provided. The mesh generator is coupled to a time dependent physical PDE and the system is evolved using an alternating solution procedure. The method uses the stochastic representation of the exact solution of a parabolic linear mesh generator to find the location of an adaptive mesh along the (artificial) subdomain interfaces. The deterministic evaluation of the mesh over each subdomain can then be obtained completely independently using the probabilistically computed solutions as boundary conditions. A small scaling study is provided to demonstrate the parallel performance of this stochastic domain decomposition approach to mesh generation. We demonstrate the approach numerically and compare the mesh obtained with the corresponding single domain mesh using a representative mesh quality measure.     

Substructured two-grid and multi-grid domain decomposition methods

Two-level Schwarz domain decomposition methods are very powerful techniques for the efficient numerical solution of partial differential equations (PDEs). A two-level domain decomposition method requires two main components: a one-level preconditioner (or its corresponding smoothing iterative method), which is based on domain decomposition techniques, and a coarse correction step, which relies on a coarse space. The coarse space must properly represent the error components that the chosen one-level method is not capable to deal with. In the literature, most of the works introduced efficient coarse spaces obtained as the span of functions defined on the entire space domain of the considered PDE. Therefore, the corresponding two-level preconditioners and iterative methods are defined in volume. In this paper, we use the excellent smoothing properties of Schwarz domain decomposition methods to define, for general elliptic problems, a new class of substructured two-level methods, for which both Schwarz smoothers and coarse correction steps are defined on the interfaces (except for the application of the smoother that requires volumetric subdomain solves). This approach has several advantages. On the one hand, the required computational effort is cheaper than the one required by classical volumetric two-level methods. On the other hand, our approach does not require, like classical multi-grid methods, the explicit construction of coarse spaces, and it permits a multilevel extension, which is desirable when the high dimension of the problem or the scarce quality of the coarse space prevents the efficient numerical solution. Numerical experiments demonstrate the effectiveness of the proposed new numerical framework.

     

Virtual and effective control for distributed systems and decomposition of everything

For the numerical approximation of the solution of boundary value problems (BVP), decomposition techniques are very important, in particular in view of parallel computations. The same is true, in principle, for optimal control of distributed systems, i.e., systems governed (modelled) by partial differential equations (PDE). Very many techniques have been studied for the approximation of BVP, such as DDM (domain decomposition method), decomposition of operators (splitting up, for instance). In contrast, not so many techniques of decomposition have been used in control problems for distributed systems, as pointed out in the contributions of Benamou [1], Benamou and Després [2], and Lagnese and Leugering [11]. However, it has been observed by Pironneau and Lions [24], [26] that by using so-calledvirtual controls, systematic DDM can be obtained, and that problems of optimal control and analysis of BVP can be considered in the same framework. We then deal with virtual control problems for BVP, virtual and effective control problems for the control of PDE (cf. Pironneau and Lions [25]). Using the idea of virtual control in other guises, Glowinski, Lions and Pironneau [9] have shown how to obtain new decomposition methods for the energy spaces (cf. Section 3), and Pironneau and Lions [27] have shown how to obtain systematically operator decomposition in BVP. In the present paper, we show (without assuming prior knowledge) how to apply the virtual control ideas in several different guises to the “decomposition of everything” for PDE of evolution and for their control. In this way, one can decompose the geometrical domain, the energy space and the operator. This is briefly presented in Sections 2, 3 and 4. We show in Section 5 how one can simultaneously apply two of the decomposition techniques and also indicate briefly how virtual control ideas can be used in case of bilinear control. The content of this paper is presented here for the first time. It is part of a systematic program which is in progress, developed with several colleagues. I wish to thank particularly F. Hecht, R. Glowinski, J. Periaux, O. Pironneau, H. Q. Chen and T. W. Pan. Of course we do not claim by any means that the methods based on “virtual control” are “better” than the many decomposition techniques already available (no attempt has been made to compile a Bibliography on these topics). Numerical works in progress show that the methods are “not bad”, but no serious benchmarking has been made yet. Possible interest lies in the fact thatone technique, with some variants, seems to lead to all possible Decompositions of Everything.     

On variations in the solutions of integro-differential equations of mixed problems of elasticity theory for domain variations

The behaviour of the solution of the boundary value problem for a pseudodifferential equation (PDE), Green's function of this problem, and also some of their local and global characteristics, during variation of the domain is investigated. Formulas are proposed that enable the solution of a broad class of PDE in a domain to be expressed in terms of the solution in the near domain. Local characteristics of the solution are expressed in terms of the local characteristics of the solution in the near domain. A double asymptotic form of Green's function for both arguments tending to the domain boundary occurs in the variation formula. The variation of this double asymptotic form as the domain varies is expressed in terms of this same asymptotic form. The system of variation formulas obtained is closed. It enables the PDE solution in the domain to be reduced to the solution of an ordinary differential equation in functional space. The local characteristics of the solution can also be found by this method without calculating the solution itself. If there is sufficient symmetry in the initial operator, then conservation laws in the Noether sense are obtained for its Green's function and its asymptotic form. The behaviour of the quantities under investigation is studied under inversion.

The investigation of variations of the solutions of problems for the variation of the domain occurs in the paper by Hadamard /1/, who studied the variation in conformal mapping and obtained a formula similar to (1.4). The formula for the variation of the solution of the boundary value problem for an elliptic differential equation is obtained in /2/. Variation formulas for the case of the operator of the problem about a crack and a circular domain are obtained in /3, 4/. The Irwin formula /5/ is obtained from formulas (1.4) and (1.21) by substitution.     

A new method of fundamental solutions applied to nonhomogeneous elliptic problems

The classical method of fundamental solutions (MFS) has only been used to approximate the solution of homogeneous PDE problems. Coupled with other numerical schemes such as domain integration, dual reciprocity method (with polynomial or radial basis functions interpolation), the MFS can be extended to solve the nonhomogeneous problems. This paper presents an extension of the MFS for the direct approximation of Poisson and nonhomogeneous Helmholtz problems. This can be done by using the fundamental solutions of the associated eigenvalue equations as a basis to approximate the nonhomogeneous term. The particular solution of the PDE can then be evaluated. An advantage of this mesh-free method is that the resolution of both homogeneous and nonhomogeneous equations can be combined in a unified way and it can be used for multiscale problems. Numerical simulations are presented and show the quality of the approximations for several test examples. AMS subject classification 35J25, 65N38, 65R20, 74J20     

Nonoverlapping Domain Decomposition Method with Mixed Element for Elliptic Problems

1.IntroductionDomaindecompositionasanewmethodofcomputationalmathematics,waJsdevel-opedsincethedevelopmentofparallelcomputersandmultiprocessorsupercomputers-Usingdomaindecompositionwecandecreasethescaleoftheproblemandimplementthesub-problemsonparallelcomputer.Fromatechnicalpointofviewmostofdo-maindecompositionmethodsconsideredsofarhavebeendealingwithfiniteelementmethods.In[1,2]ZhangandHuanghavegivenakindofnonoverlappingdomaindecompositionprocedurewithpiecewiselinearfiniteelementapproximation.…     

Spectral domain embedding for elliptic PDEs in complex domains

Spectral methods are a class of methods for solving partial differential equations (PDEs). When the solution of the PDE is analytic, it is known that the spectral solutions converge exponentially as a function of the number of modes used. The basic spectral method works only for regular domains such as rectangles or disks. Domain decomposition methods/spectral element methods extend the applicability of spectral methods to more complex geometries. An alternative is to embed the irregular domain into a regular one. This paper uses the spectral method with domain embedding to solve PDEs on complex geometry. The running time of the new algorithm has the same order as that for the usual spectral collocation method for PDEs on regular geometry. The algorithm is extremely simple and can handle Dirichlet, Neumann boundary conditions as well as nonlinear equations.     

Solitary and Periodic Solutions of Nonlinear Nonintegrable Equations

The singular manifold method and partial fraction decomposition allow one to find some special solutions of nonintegrable partial differential equations (PDE) in the form of solitary waves, traveling wave fronts, and periodic pulse trains. The truncated Painlevé expansion is used to reduce a nonlinear PDE to a multilinear form. Some special solutions of the latter equation represent solitary waves and traveling wave fronts of the original PDE. The partial fraction decomposition is used to obtain a periodic wave train solution as an infinite superposition of the "corrected" solitary waves.     

Construction dʼun champ continu de métriques

Adaptive computation using adaptive meshes is now recognized as essential for solving complex PDE problems. This computation requires, at each step, the definition of a continuous metric field to govern the generation of the adapted meshes. In practice, via an appropriate a posteriori error estimation, metrics are calculated at the vertices of the computational domain mesh. In order to obtain a continuous metric field, the discrete field is interpolated in the whole domain mesh. In this Note, a new method for interpolating discrete metric fields, based on a so-called “natural decomposition” of metrics, is introduced. The proposed method is based on known matrix decompositions and is computationally robust and efficient. Some qualitative comparisons with classical methods are made to show the relevance of this methodology.     

A Dirichlet–Neumann reduced basis method for homogeneous domain decomposition problems

Reduced basis methods allow efficient model reduction of parametrized partial differential equations. In the current paper, we consider a reduced basis method based on an iterative Dirichlet–Neumann coupling for homogeneous domain decomposition of elliptic PDEʼs. We gain very small basis sizes by an efficient treatment of problems with a-priori known geometry. Moreover iterative schemes may offer advantages over other approaches in the context of parallelization. We prove convergence of the iterative reduced scheme, derive rigorous a-posteriori error bounds and provide a full offline/online decomposition. Different methods for basis generation are investigated, in particular a variant of the POD-Greedy procedure. Experiments confirm the rigor of the error estimators and identify beneficial basis construction procedures.     

The Klein–Gordon Equation in a Domain with Time‐Dependent Boundary

We solve a Dirichlet boundary value problem for the Klein–Gordon equation posed in a time‐dependent domain. Our approach is based on a general transform method for solving boundary value problems for linear and integrable nonlinear PDE in two variables. Our results consist of the inversion formula for a generalized Fourier transform, and of the application of this generalized transform to the solution of the boundary value problem.     

A Source Transfer Domain Decomposition Method for Helmholtz Equations in Unbounded Domain Part II: Extensions

In this paper we extend the source transfer domain decomposition method (STDDM) introduced by the authors to solve the Helmholtz problems in two-layered media, the Helmholtz scattering problems with bounded scatterer, and Helmholtz problems in 3D unbounded domains. The STDDM is based on the decomposition of the domain into non-overlapping layers and the idea of source transfer which transfers the sources equivalently layer by layer so that the solution in the final layer can be solved using a PML method defined locally outside the last two layers. The details of STDDM is given for each extension. Numerical results are presented to demonstrate the efficiency of STDDM as a preconditioner for solving the discretization problem of the Helmholtz problems considered in the paper.     

A parallel domain reduction method

We relate a particular version of a parallel multigrid method to a domain decomposition method, showing that the parallel multigrid method reduces computation to a small portion of the domain and then extends the solution to the entire domain using the correct reflections to get the exact solution. We extend a particular example to double the parallelism in a nonobvious manner. While the techniques of this paper are applied to twodimensional problems, they can be applied to higher dimensional problems in an obvious manner.     

Two-level Schwarz method for unilateral variational inequalities

The numerical solution of variational inequalities of obstacletype associated with second-order elliptic operators is considered.Iterative methods based on the domain decomposition approachare proposed for discrete obstacle problems arising from thecontinuous, piecewise linear finite element approximation ofthe differential problem. A new variant of the Schwarz methodology,called the two-level Schwarz method, is developed offering thepossibility of making use of fast linear solvers (e.g., linearmultigrid and fictitious domain methods) for the genuinely nonlinearobstacle problems. Namely, by using particular monotonicityresults, the computational domain can be partitioned into (mesh)subdomains with linear and nonlinear (obstacle-type) subproblems.By taking advantage of this domain decomposition and fast linearsolvers, efficient implementation algorithms for large-scalediscrete obstacle problems can be developed. The last part ofthe paper is devoted to illustrate numerical experiments.     

不可分离凸背包问题的拉格朗日分解和区域分割方法

本文对线性约束不可分离凸背包问题给出了一种精确算法．该算法是拉格朗日分解和区域分割结合起来的一种分枝定界算法．利用拉格朗日分解方法可以得到每个子问题的一个可行解，一个不可行解，一个下界和一个上界．区域分割可以把一个整数箱子分割成几个互不相交的整数子箱子的并集，每个整数子箱子对应一个子问题．通过区域分割可以逐步减小对偶间隙并最终经过有限步迭代找到原问题的最优解．数值结果表明该算法对不可分离凸背包问题是有效的．     

Initial/boundary value problems for the semidiscrete Boltzmann equation: Analysis by Adomian's decomposition method

This paper provides a solution technique based on Adomian's decomposition method for a large class of initial/boundary value problems for the semidiscrete Boltzmann equation: a partial differential-integral equation of a semilinear type, in the kinetic theory of gases. The paper also proposes a use of the decomposition method as an algorithm for the continuous approximation of the solutions in a discretized time-space domain.     

基于几何非协调分解的区域分解方法误差分析

对三维可压线弹性问题采用一种基于几何非协调分解的区域分解方法进行求解,证明了数值解具有最优误差估计.     

Multiscale finite element coarse spaces for the application to linear elasticity

We extend the multiscale finite element method (MsFEM) as formulated by Hou and Wu in [Hou T.Y., Wu X.-H., A multiscale finite element method for elliptic problems in composite materials and porous media, J. Comput. Phys., 1997, 134(1), 169–189] to the PDE system of linear elasticity. The application, motivated by the multiscale analysis of highly heterogeneous composite materials, is twofold. Resolving the heterogeneities on the finest scale, we utilize the linear MsFEM basis for the construction of robust coarse spaces in the context of two-level overlapping domain decomposition preconditioners. We motivate and explain the construction and show that the constructed multiscale coarse space contains all the rigid body modes. Under the assumption that the material jumps are isolated, that is they occur only in the interior of the coarse grid elements, our numerical experiments show uniform convergence rates independent of the contrast in Young’s modulus within the heterogeneous material. Elsewise, if no restrictions on the position of the high coefficient inclusions are imposed, robustness cannot be guaranteed any more. These results justify expectations to obtain coefficient-explicit condition number bounds for the PDE system of linear elasticity similar to existing ones for scalar elliptic PDEs as given in the work of Graham, Lechner and Scheichl [Graham I.G., Lechner P.O., Scheichl R., Domain decomposition for multiscale PDEs, Numer. Math., 2007, 106(4), 589–626]. Furthermore, we numerically observe the properties of the MsFEM coarse space for linear elasticity in an upscaling framework. Therefore, we present experimental results showing the approximation errors of the multiscale coarse space w.r.t. the fine-scale solution.     

杂交有限元的区域分解法

近几年来,由于并行计算机的迅速发展,求解椭圆型微分方程的区城分解法又引起了人们的重视.这一方法的基本思想是把求解区域分解成许多子区域,每个子区域上用一台计算机求解.这种方法适应并行机的需要,是用并行机解大型椭圆型偏微分方程的一     

Non-Conforming Domain Decomposition with Hybrid Method

We present a non-conforming domain decomposition technique for solving elliptic problems with the finite element method. Functions in the finite element space associated with this method may be discontinuous on the boundary of subdomains. The sizes of the finite meshes, the kinds of elements and the kinds of interpolation functions may be different in different subdomains. So, this method is more convenient and more efficient than the conforming domain decomposition method. We prove that the solution obtained by this method has the same convergence rate as by the conforming method, and both the condition number and the order of the capacitance matrix are much lower than those in the conforming case.