SUBSTRUCTURE PRECONDITIONERS FOR NONCONFORMING PLATE ELEMENTS

1.IntroductionInthispaper,wegeneralizetheBPSalgorithm[1]tononconformingelementfproximationsofthebiharmonicequation.WeconstructapreconditionerforMor:elementbysubstructuringonthebasisofafunctiondecompositionfordiscretebibmonicfunctions.Thefunctiondecomposit…     

A PARALLEL ITERATIVE DOMAIN DECOMPOSITION ALGORITHM FOR ELLIPTIC PROBLEMS

1.IntroductionNolloverlappillgdomaindecolllpositionnletllodshavereceivedalotofattentionlenlsilllldallowefficielltparallelisnl.F'Orarecentdevelopmelltofthesemethods,werefertot…     

Analysis of Iterative Sub-structuring Techniques for Boundary Element Approximation of the Hypersingular Operator in Three Dimensions

The article deals with the analysis of Additive Schwarz preconditioners for the h -version of the boundary element method for the hypersingular integral equation on surfaces in three dimensions. The first preconditioner consists of decomposing into local spaces associated with the subdomain interiors, supplemented with a wirebasket space associated with the subdomain interfaces. The wirebasket correction only involves the inversion of a diagonal matrix, while the interior correction consists of inverting the sub-blocks of the stiffness matrix corresponding to the interior degrees of freedom on each subdomain. It is shown that the condition number of the preconditioned system grows at most as max K H m 1 (1 + log H / h K ) 2 where H is the size of the quasi-uniform subdomains and h K is the size of the elements in subdomain K . A second preconditioner is given that incorporates a coarse space associated with the subdomains. This improves the robustness of the method with respect to the number of subdomains: theoretical analysis shows that growth of the condition number of the preconditioned system is now bounded by max K (1 + log H / h K ) 2 .     

A spatial domain decomposition method for parabolic optimal control problems

We present a non-overlapping spatial domain decomposition method for the solution of linear–quadratic parabolic optimal control problems. The spatial domain is decomposed into non-overlapping subdomains. The original parabolic optimal control problem is decomposed into smaller problems posed on space–time cylinder subdomains with auxiliary state and adjoint variables imposed as Dirichlet boundary conditions on the space–time interface boundary. The subdomain problems are coupled through Robin transmission conditions. This leads to a Schur complement equation in which the unknowns are the auxiliary state adjoint variables on the space-time interface boundary. The Schur complement operator is the sum of space–time subdomain Schur complement operators. The application of these subdomain Schur complement operators is equivalent to the solution of an subdomain parabolic optimal control problem. The subdomain Schur complement operators are shown to be invertible and the application of their inverses is equivalent to the solution of a related subdomain parabolic optimal control problem. We introduce a new family of Neumann–Neumann type preconditioners for the Schur complement system including several different coarse grid corrections. We compare the numerical performance of our preconditioners with an alternative approach recently introduced by Benamou.     

Balancing Neumann‐Neumann methods for incompressible Stokes equations

Balancing Neumann‐Neumann methods are introduced and studied for incompressible Stokes equations discretized with mixed finite or spectral elements with discontinuous pressures. After decomposing the original domain of the problem into nonoverlapping subdomains, the interior unknowns, which are the interior velocity component and all except the constant‐pressure component, of each subdomain problem are implicitly eliminated. The resulting saddle point Schur complement is solved with a Krylov space method with a balancing Neumann‐Neumann preconditioner based on the solution of a coarse Stokes problem with a few degrees of freedom per subdomain and on the solution of local Stokes problems with natural and essential boundary conditions on the subdomains. This preconditioner is of hybrid form in which the coarse problem is treated multiplicatively while the local problems are treated additively. The condition number of the preconditioned operator is independent of the number of subdomains and is bounded from above by the product of the square of the logarithm of the local number of unknowns in each subdomain and a factor that depends on the inverse of the inf‐sup constants of the discrete problem and of the coarse subproblem. Numerical results show that the method is quite fast; they are also fully consistent with the theory. © 2002 John Wiley & Sons, Inc.     

Coupling nonlinear Stokes and Darcy flow using mortar finite elements

We study a system composed of a nonlinear Stokes flow in one subdomain coupled with a nonlinear porous medium flow in another subdomain. Special attention is paid to the mathematical consequence of the shear-dependent fluid viscosity for the Stokes flow and the velocity-dependent effective viscosity for the Darcy flow. Motivated by the physical setting, we consider the case where only flow rates are specified on the inflow and outflow boundaries in both subdomains. We recast the coupled Stokes–Darcy system as a reduced matching problem on the interface using a mortar space approach. We prove a number of properties of the nonlinear interface operator associated with the reduced problem, which directly yield the existence, uniqueness and regularity of a variational solution to the system. We further propose and analyze a numerical algorithm based on mortar finite elements for the interface problem and conforming finite elements for the subdomain problems. Optimal a priori error estimates are established for the interface and subdomain problems, and a number of compatibility conditions for the finite element spaces used are discussed. Numerical simulations are presented to illustrate the algorithm and to compare two treatments of the defective boundary conditions.     

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.     

Augmented hybrid finite element method for domain decomposition

We present an Augmented Hybrid Finite Element Method for Domain Decompositon. In this method, finite element approximations are defined independently on each subdomain and do not match at interface. This dows the user to mda local change of design, of meshes on one aubdomain without modifying other subdomains. Optimal reaults are obtained for a second-order model problem.     

Synchronous exploration for the control of real-time external noise suppression in a three-dimensional subdomain

A mathematical (difference) model is proposed for a real-time active shielding device that shields an acoustic field in a given subdomain from the influence of sound sources located in an additional subdomain. An algorithm for computing the current control ensuring a prescribed process is based on information produced by the author’s technique of synchronous weak noise exploration. This information can be measured in real time. Active control problems for nonstationary solutions of linear difference equations in a three-dimensional domain consisting of two subdomains are studied using the difference potential method. The shape of the domain and the boundary conditions may depend on time, while the coefficients may depend on time and spatial coordinates. If the difference problem is a mathematical model of sound propagation, the goal of control is to change the acoustic field in the given subdomains, for example, to shield the acoustic field in one subdomain from the undesirable influence (noise) of sources located in the other subdomain.     

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.     

On the domain decomposition method for the generalized Stokes problem with continuous pressure

Using the nonoverlapping domain decomposition approach, we propose a formulation of the dual Schur algorithm for the generalized Stokes problem discretized by a mixed finite element method continuous for the pressure in each subdomain, but discontinuous at the interfaces. The corresponding LBB condition is checked. The dual interface problem is written in the case of two subdomains, and it is generalized to several subdomains. An efficient preconditioner for the interface problem is derived. Numerical results are presented for two different local solvers. Parallel computations were made on an IBM‐SP2. © 2000 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 16: 84–106, 2000     

A coupled continuous-discontinuous FEM approach for convection diffusion equations

In this article, we introduce a coupled approach of local discontinuous Galerkin and standard finite element method for solving convection diffusion problems. The whole domain is divided into two disjoint subdomains. The discontinuous Galerkin method is adopted in the subdomain where the solution varies rapidly, while the standard finite element method is used in the other subdomain due to its lower computational cost. The stability and a priori error estimate are established. We prove that the coupled method has O((ε1 / 2 + h 1 / 2 )h k ) convergence rate in an associated norm, where ε is the diffusion coefficient, h is the mesh size and k is the degree of polynomial. The numerical results verify our theoretical results. Moreover, 2k-order superconvergence of the numerical traces at the nodes, and the optimal convergence of the errors under L 2 norm are observed numerically on the uniform mesh. The numerical results also indicate that the coupled method has the same convergence order and almost the same errors as the purely LDG method.     

Iterative solution of a singular convection-diffusion perturbation problem

An iterative domain decomposition method is developed to solve a singular perturbation problem. The problem consists of a convection-diffusion equation with a discontinuous (piecewise-constant) diffusion coefficient, and the problem domain is decomposed into two subdomains, on each of which the coefficient is constant. After showing that the boundary value problem is well posed, we indicate a specific numerical implementation of the iterative technique that combines the finite element method on one subdomain with the method of matched asymptotic expansions on the other subdomain. This procedure extends work by Carlenzoli and Quarteroni, which was originally intended for a boundary layer problem with an outer region and an inner region. Our extension carries over to a problem where the domain consists of the outer and inner boundary layer regions plus a region in which the diffusion coefficient is constant and significant in magnitude. An unexpected benefit of our new implementation is its efficiency, which is due to the fact that at each iteration the problem needs to be solved explicitly only on one subdomain. It is only when the final approximation on the entire domain is desired that the matched asymptotic expansions approximation need be computed on the second subdomain. Two-dimensional convergence results and numerical results illustrating the method for a two-dimensional test problem are given.     

Convergence analysis of a balancing domain decomposition method for solving a class of indefinite linear systems

A variant of balancing domain decomposition method by constraints (BDDC) is proposed for solving a class of indefinite systems of linear equations of the form (K?σ²M)u=f, which arise from solving eigenvalue problems when an inverse shifted method is used and also from the finite element discretization of Helmholtz equations. Here, both K and M are symmetric positive definite. The proposed BDDC method is closely related to the previous dual–primal finite element tearing and interconnecting method (FETI‐DP) for solving this type of problems (Appl. Numer. Math. 2005; 54 :150–166), where a coarse level problem containing certain free‐space solutions of the inherent homogeneous partial differential equation is used in the algorithm to accelerate the convergence. Under the condition that the diameters of the subdomains are small enough, the convergence rate of the proposed algorithm is established, which depends polylogarithmically on the dimension of the individual subdomain problems and which improves with a decrease of the subdomain diameters. These results are supported by numerical experiments of solving a two‐dimensional problem. Copyright © 2009 John Wiley & Sons, Ltd.     

A computational methodology to study coupled physical processes over partitioned domains

In this paper, we describe a computational methodology to couple physical processes defined over independent subdomains, that are partitions of a global domain in three-dimensions. The methodology presented helps to compute the numerical solution on the global domain by appropriately piecing the local solutions from each subdomain. We discuss the mixed method formulation for the technique applied to a model problem and derive an error estimate for the finite element solution. We demonstrate through numerical experiments that the method is robust and reliable in higher dimensions.     

On linear monotone iteration and Schwarz methods for nonlinear elliptic PDEs

Summary The Schwarz Alternating Method can be used to solve elliptic boundary value problems on domains which consist of two or more overlapping subdomains. The solution is approximated by an infinite sequence of functions which results from solving a sequence of elliptic boundary value problems in each subdomain. In this paper, proofs of convergence of some Schwarz Alternating Methods for nonlinear elliptic problems which are known to have solutions by the monotone method (also known as the method of subsolutions and supersolutions) are given. In particular, an additive Schwarz method for scalar as well some coupled nonlinear PDEs are shown to converge to some solution on finitely many subdomains, even when multiple solutions are possible. In the coupled system case, each subdomain PDE is linear, decoupled and can be solved concurrently with other subdomain PDEs. These results are applicable to several models in population biology. This work was in part supported by a grant from the RGC of HKSAR, China (HKUST6171/99P)     

An element agglomeration nonlinear additive Schwarz preconditioned Newton method for unstructured finite element problems

This paper extends previous results on nonlinear Schwarz preconditioning (Cai and Keyes 2002) to unstructured finite element elliptic problems exploiting now nonlocal (but small) subspaces. The nonlocal finite element subspaces are associated with subdomains obtained from a non-overlapping element partitioning of the original set of elements and are coarse outside the prescribed element subdomain. The coarsening is based on a modification of the agglomeration based AMGe method proposed in Jones and Vassilevski 2001. Then, the algebraic construction from Jones, Vassilevski and Woodward 2003 of the corresponding non-linear finite element subproblems is applied to generate the subspace based nonlinear preconditioner. The overall nonlinearly preconditioned problem is solved by an inexact Newton method. A numerical illustration is also provided.This work was performed under the auspices of the U.S. Department of Energy by the University of California Lawrence Livermore National Laboratory: contract/grant number: W-7405-Eng-48. The contribution of the second author was also partially supported by Polish Scientific Grant 2/P03A/005/24.     

Iterative solution of a singular convection-diffusion perturbation problem

An iterative domain decomposition method is developed to solve a singular perturbation problem. The problem consists of a convection-diffusion equation with a discontinuous (piecewise-constant) diffusion coefficient, and the problem domain is decomposed into two subdomains, on each of which the coefficient is constant. After showing that the boundary value problem is well posed, we indicate a specific numerical implementation of the iterative technique that combines the finite element method on one subdomain with the method of matched asymptotic expansions on the other subdomain. This procedure extends work by Carlenzoli and Quarteroni, which was originally intended for a boundary layer problem with an outer region and an inner region. Our extension carries over to a problem where the domain consists of the outer and inner boundary layer regions plus a region in which the diffusion coefficient is constant and significant in magnitude. An unexpected benefit of our new implementation is its efficiency, which is due to the fact that at each iteration the problem needs to be solved explicitly only on one subdomain. It is only when the final approximation on the entire domain is desired that the matched asymptotic expansions approximation need be computed on the second subdomain. Two-dimensional convergence results and numerical results illustrating the method for a two-dimensional test problem are given.Received: February 12, 2004     

Non-overlapping Domain Decomposition Method for a Nodal Finite Element Method

A new approach is proposed for constructing nonoverlapping domain decomposition procedures for solving a linear system related to a nodal finite element method. It applies to problems involving either positive semi-definite or complex indefinite local matrices. The main feature of the method is to preserve the continuity requirements on the unknowns and the finite element equations at the nodes shared by more than two subdomains and to suitably augment the local matrices. We prove that the corresponding algorithm can be seen as a converging iterative method for solving the finite element system and that it cannot break down. Each iteration is obtained by solving uncoupled local finite element systems posed in each subdomain and, in contrast to a strict domain decomposition method, is completed by solving a linear system whose unknowns are the degrees of freedom attached to the above special nodes.     

Accelerated Non-Overlapping Domain Decomposition Method for Total Variation Minimization

We concern with fast domain decomposition methods for solving the total variation minimization problems in image processing. By decomposing the image domain into non-overlapping subdomains and interfaces, we consider the primal-dual problem on the interfaces such that the subdomain problems become independent problems and can be solved in parallel. Suppose both the interfaces and subdomain problems are uniformly convex, we can apply the acceleration method to achieve an $\mathcal{O}(1 / n^2)$ convergent domain decomposition algorithm. The convergence analysis is provided as well. Numerical results on image denoising, inpainting, deblurring, and segmentation are provided and comparison results with existing methods are discussed, which not only demonstrate the advantages of our method but also support the theoretical convergence rate.