On the convergence of a dual-primal substructuring method

Summary.   In the Dual-Primal FETI method, introduced by Farhat et al. [5], the domain is decomposed into non-overlapping subdomains, but the degrees of freedom on crosspoints remain common to all subdomains adjacent to the crosspoint. The continuity of the remaining degrees of freedom on subdomain interfaces is enforced by Lagrange multipliers and all degrees of freedom are eliminated. The resulting dual problem is solved by preconditioned conjugate gradients. We give an algebraic bound on the condition number, assuming only a single inequality in discrete norms, and use the algebraic bound to show that the condition number is bounded by for both second and fourth order elliptic selfadjoint problems discretized by conforming finite elements, as well as for a wide class of finite elements for the Reissner-Mindlin plate model. Received January 20, 2000 / Revised version received April 25, 2000 / Published online December 19, 2000     

A Dual-Primal FETI method for incompressible Stokes equations

In this paper, a dual-primal FETI method is developed for incompressible Stokes equations approximated by mixed finite elements with discontinuous pressures. The domain of the problem is decomposed into nonoverlapping subdomains, and the continuity of the velocity across the subdomain interface is enforced by introducing Lagrange multipliers. By a Schur complement procedure, the solution of an indefinite Stokes problem is reduced to solving a symmetric positive definite problem for the dual variables, i.e., the Lagrange multipliers. This dual problem is solved by the conjugate gradient method with a Dirichlet preconditioner. In each iteration step, both subdomain problems and a coarse level problem are solved by a direct method. It is proved that the condition number of this preconditioned dual problem is independent of the number of subdomains and bounded from above by the square of the product of the inverse of the inf-sup constant of the discrete problem and the logarithm of the number of unknowns in the individual subdomains. Numerical experiments demonstrate the scalability of this new method. This work is based on a doctoral dissertation completed at Courant Institute of Mathematical Sciences, New York University. This work was supported in part by the National Science Foundation under Grants NSF-CCR-9732208, and in part by the U.S. Department of Energy under contract DE-FG02-92ER25127.     

First mixed problem for a parabolic difference-differential equation

The first mixed boundary value problem for a parabolic difference-differential equation with shifts with respect to the spatial variables is considered. The unique solvability of this problem and the smoothness of generalized solutions in some cylindrical subdomains are established. It is shown that the smoothness of generalized solutions can be violated on the interfaces of neighboring subdomains. Translated fromMatematicheskie Zametki, Vol. 66, No. 1, pp. 145–153, July, 1999.     

Iterative solution of a coupled mixed and standard Galerkin discretization method for elliptic problems

In this paper, we consider approximation of a second‐order elliptic problem defined on a domain in two‐dimensional Euclidean space. Partitioning the domain into two subdomains, we consider a technique proposed by Wieners and Wohlmuth [9] for coupling mixed finite element approximation on one subdomain with a standard finite element approximation on the other. In this paper, we study the iterative solution of the resulting linear system of equations. This system is symmetric and indefinite (of saddle‐point type). The stability estimates for the discretization imply that the algebraic system can be preconditioned by a block diagonal operator involving a preconditioner for H (div) (on the mixed side) and one for the discrete Laplacian (on the finite element side). Alternatively, we provide iterative techniques based on domain decomposition. Utilizing subdomain solvers, the composite problem is reduced to a problem defined only on the interface between the two subdomains. We prove that the interface problem is symmetric, positive definite and well conditioned and hence can be effectively solved by a conjugate gradient iteration. Copyright © 2001 John Wiley & Sons, Ltd.     

一类无结构三角网上抛物方程的有限差分区域分解算法

本文讨论了一类在无结构三角网上数值求解二维热传导方程的有限差分区域分解算法．在这个算法中,将通过引进两类不同类型的内界点,将求解区域分裂成若干子区域．一旦内界点处的值被计算出来,其余子区域上的计算可完全并行．本文得到了稳定性条件和最大模误差估计,它表明我们的格式有令人满意的稳定性和较高的收敛阶．     

Convergence of the solution for a domain decomposed,heterogeneously modeled flow past a concave profile problem

The free streamline problem investigated is that of fluid flow past a symmetric truncated concave‐shaped profile between walls. An open wake or cavity is formed behind the profile. Conformal mapping techniques are used to solve this problem. The problem formulated in the hodograph plane is decomposed into two nonoverlapping domains. Heterogeneous modeling is then used to describe the problems, i.e., a different governing differential equation in each domain. In one of these domains, a Baiocchi‐type transformation is used to obtain a fixed domain formulation for the part of the transformed problem containing an unknown boundary. In the other domain, the Baiocchi‐type transformation is extended across the boundary between the two domains, thus yielding a different problem formulation. This also assures that the dependent variables and their normal derivatives are continuous along this common boundary. The numerical solution scheme, a successive over‐relaxation approach, is applied over the whole problem domain with the use of a projection‐operation over only the fixed domain formulated part. Numerical results are obtained for the case of a truncated circular profile. These results are found to be in good agreement with another published result. The existence and uniqueness of the solution to the problem as a variational inequality is shown, and the convergence of the numerical solution using a domain decomposition method scheme is demonstrated by assuming some convergence property on the common interface of the two subdomains. © 2000 John Wiley & Sons, Inc. Numeer Methods Partial Differential Eq 16: 459–479, 2000     

Studies of an interface relaxation domain decomposition technique using finite elements on a parallel computer

Studies are presented for an interface relaxation domain decomposition technique using finite elements on an iPSC/2 D5 Hypercube Concurrent computer. The general type of problem to be solved is one governed by a partial differential equation. The application of the approach, however, will be extended to a free boundary value problem by appropriate modification of the numerical scheme. Using the domain decomposition technique, the computation domain is subdivided into several subdomains. In addition, on the interfaces between two adjacent subdomains are imposed a continuity condition on one side and an equilibrium condition on the other side. Successive overrelaxation iterative processes are then carried out in all subdomains with a relaxation process imposed on the interfaces. With this domain decomposition technique, the problem can be solved parallelly until convergence is reached both in the interiors and on the interfaces of all subdomains. Moreover, the formulation includes a simple domain decomposer that automatically divides a finite element mesh into a list of subdomains to guarantee load balancing. Furthermore, it is shown, through numerical experiments performed on an example problem of free surface seepage through a porous dam, how the values of the relaxation parameters, the choice of imposed boundary conditions, and the number of subdomains (i.e., the number of processors used) affect the solution convergence in this parallel computing environment. © 1993 John Wiley & Sons, Inc.     

Nonoverlapping domain decomposition and additive splitting up methods for multidimensional parabolic problem

The explicit implicit domain decomposition methods are noniterative types of methods for nonoverlapping domain decomposition but due to the use of the explicit step for the interface prediction, the methods suffer from inaccuracy of the usual explicit scheme. In this article a specific type of first‐ and second‐order splitting up method, of additive type, for the dependent variables is initially considered to solve the two‐ or three‐dimensional parabolic problem over nonoverlapping subdomains. We have also considered the parallel explicit splitting up algorithm to define (predict) the interface boundary conditions with respect to each spatial variable and for each nonoverlapping subdomains. The parallel second‐order splitting up algorithm is then considered to solve the subproblems defined over each subdomain; the correction step will then be considered for the predicted interface nodal points using the most recent solution values over the subdomains. Finally several model problems will be considered to test the efficiency of the presented algorithm. © 2005 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2006     

Error estimate for a stabilised domain decomposition method with nonmatching grids

Summary. In this paper, we analyse a stabilisation technique for the so-called three-field formulation for nonoverlapping domain decomposition methods. The stabilisation is based on boundary bubble functions in each subdomain which are then eliminated by static condensation. The discretisation grids in the subdomains can be chosen independently as well as the grid for the final interface problem. We present the analysis of the method and we construct a set of bubble functions which guarantees the optimal rate of convergence. Received May 12, 1998 / Revised version received November 21, 2000 / Published online June 7, 2001     

A New Non-Overlapping Domain Decomposition Method for a 3D Laplace Exterior Problem

We propose a method for solving three-dimensional boundary value problems for Laplace’s equation in an unbounded domain. It is based on non-overlapping decomposition of the exterior domain into two subdomains so that the initial problem is reduced to two subproblems, namely, exterior and interior boundary value problems on a sphere. To solve the exterior boundary value problem, we propose a singularity isolation method. To match the solutions on the interface between the subdomains (the sphere), we introduce a special operator equation approximated by a system of linear algebraic equations. This system is solved by iterative methods in Krylov subspaces. The performance of the method is illustrated by solving model problems.     

结构三角网上抛物方程的有限差分区域分解算法

1引言对于大型科学与工程计算问题,并行计算是必需的．构造高效率的数值并行方法一直是人们关心的问题,并且已有了大量的研究．在三层交替计算方法的研究中出现了许多既具有明显并行性又绝对稳定的差分格式(见[1]-[5])．在只涉及两个时间层的算法研究中,Dawson等人(见[6])首先发展了求解一维热传导方程的区域分解算法,并将其推广到     

Uniform estimates for transmission problems with high contrast in heat conduction and electromagnetism

In this paper we prove uniform a priori estimates for transmission problems with constant coefficients on two subdomains, with a special emphasis for the case when the ratio between these coefficients is large. In the most part of the work, the interface between the two subdomains is supposed to be Lipschitz. We first study a scalar transmission problem which is handled through a converging asymptotic series. Then we derive uniform a priori estimates for Maxwell transmission problem set on a domain made up of a dielectric and a highly conducting material. The technique is based on an appropriate decomposition of the electric field, whose gradient part is estimated thanks to the first part. As an application, we develop an argument for the convergence of an asymptotic expansion as the conductivity tends to infinity.     

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 nonoverlapping domain decomposition method for nonlinear physical processes

A coupling technique for a nonoverlapping domain decomposition method is investigated in this paper. We test this method on a nonlinear heat conduction process taking place in a multi-chip module which has many geometrically structured subdomains. The problem of interface condition between two adjacent subdomains is tackled by incorporating a defect equation which is solved iteratively. We evaluate two defect equations on this scheme, i.e. the difference of normal derivative and the residual of the heat conduction equation itself. Both equations lead to systems of nonlinear equations which are solved by means of quasi-Newton methods with an adaptive alpha rate instead of a Jacobian matrix. The simulation suggests that the second defect equation is much more accurate. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Optimal Design of Periodic Diffractive Structures

The problem of designing a periodic interface between two different materials, which gives rise to a specified far-field diffraction pattern for a given incoming plane wave, is considered. The time harmonic waves are assumed to be TM (transverse magnetic) polarized. The diffraction problem is modeled by a generalized Helmholtz equation with transparent boundary conditions. In this paper the design problem is relaxed to include highly oscillatory profiles. Existence of an optimal design is established. The principal method is based on the theory of homogenization for the model equation. Accepted 31 May 2000. Online publication 26 February 2001.     

Parallel algorithm for the solutions of PDEs in linux clustered workstations

In this paper we propose parallel algorithm for the solution of partial differential equations over a rectangular domain using the Crank–Nicholson method by cooperation with the DuFort–Frankel method and apply it on a model problem, namely, the heat conduction equation. One of the well known parallel techniques in solving partial differential equations in cluster computing environment is the domain decomposition technique. Using this technique, the whole domain is decomposed into subdomains, each of them has its own boundaries that are called the interface points. Parallelization is realized by approximating interface values using the unconditionally stable DuFort–Frankel explicit scheme, and these values serve as Neumann boundary conditions for the Crank–Nicholson implicit scheme in the subdomains. The numerical results show that our algorithm is more accurate than the algorithm based on the forward explicit method to approximate the values of the interface points, especially, when we use a small number of time steps. Moreover, these numerical results show that increasing the number of processors which are used in the cluster, yields an increase in the algorithm speedup.     

Modeling and simulation of keyhole-based welding as multi-domain problem using the extended finite element method

In this article, we demonstrate the flexibility of a multi-domain approach combined with the extended finite element method by addressing the modeling and simulation of keyhole-based welding. The welding process is modeled by the heat equation where the keyhole geometry and the interface separating molten and solid area are represented by two independent level set functions, separating the domain into three time-dependent subdomains. The keyhole shape is computed by an analytical approach based on the energy balance at the keyhole wall and its shape is assumed to be fixed. The solid-liquid interface is considered as free boundary whose evolution is described by the two-phase Stefan problem. The coupled problem including the two discontinuities is solved using a multi-domain XFEM implementation. The simulated results are shown together with experimental data on different welded materials.     

Finite-difference approximation of dirichlet observation problems for weak solutions to the wave equation subject to Robin boundary conditions

For the wave equation with variable coefficients subject to Neumann and Robin boundary conditions, two mutually dual problems are considered: the Dirichlet observation problem with weak generalized solutions and the control problem with strong generalized solutions. Both problems are approximated by finite differences preserving the duality relation. The convergence of the approximate solutions is established in the norms of the corresponding dual spaces.     

An additive Schwarz preconditioner for the FETI method

Summary.  A new additive Schwarz preconditioner for the Finite Element Tearing and Interconnecting (FETI) method is analyzed in this paper. This preconditioner has the unique feature that the coefficient matrix of its ``coarse grid' problem is mesh independent. For a model second order heterogeneous elliptic boundary value problem in two dimensions, the condition number of the preconditioned system is shown to be bounded by C[1+ln(H/h)]², where h is the mesh size, H is the typical diameter of the subdomains, and the constant C is independent of h, H, the number of subdomains and the coefficients of the boundary value problem. Received May 8, 2000 / Revised version received January 2, 2002 / Published online July 18, 2002 Mathematics Subject Classification (1991): 65N55, 65N30