Domain Decomposition Methods in Science and Engineering

In this paper we introduce a variant of the three-field formulation where we use only two sets of variables. Considering, to fix the ideas, the homogeneous Dirichlet problem for −

Δu

=

g

in

Ω

, our variables are

i)

an approximation

ψ

h

of

u

on the

skeleton

(the union of the interfaces of the sub-domains) on an independent grid (that could often be uniform), and

ii)

the approximations

u

h

s

of

u

in each subdomain

Ω

s

(each on its own grid). The novelty is in the way to derive, from

ψ

h

, the values of each trace of

u

h

s

on the boundary of each

Ω

s

. We do it by solving an auxiliary problem on each

∂Ω

s

that resembles the mortar method but is more flexible. Optimal error estimates are proved under suitable assumptions.

The FETI-DP domain decomposition method is extended to address the iterative solution of a class of indefinite problems of the form (

K

−

σ

2

M

)

x

=

b

, and a class of complex problems of the form (

K

−

σ

2

M

+

iσ

D

)

x

=

b

, where

K

,

M

, and

D

are three real symmetric positive semi-definite matrices arising from the finite element discretization of either second-order elastodynamic problems or fourth-order plate and shell dynamic problems,

i

is the imaginary complex number, and

σ

is a positive real number.

The performance of multigrid methods for the standard Poisson problem and for the consistent Poisson problem arising in spectral element discretizations of the Navier-Stokes equations is investigated. It is demonstrated that overlapping additive Schwarz methods are effective smoothers, provided that the solution in the overlap region is weighted by the inverse counting matrix. It is also shown that spectral element based smoothers are superior to those based upon finite element discretizations. Results for several large 3D Navier-Stokes applications are presented.

In this paper, we treat the numerical method for the Helmholtz equation in unbounded region with simple cylindrical or spherical shape outside some bounded region and apply the method to voice generation problem. The numerical method for the Helmholtz equation in unbounded region is based on the domain decomposition technique to divide the region into a bounded region and the rest unbounded one. We then treat the approximation of the artificial boundary condition given through the DtN mapping on the artificial boundary. We apply the finite element approximation to discretize the problem. In applying the method to the voice generation problem, it is essential to compute the frequency response function or the formant curve. We give variational formulas for the resolvent poles with respect to the variation of vocal tract boundary which determine the peaks of frequency response function known as formants, and we propose the use of variational formulas to design the location of formants.

Iterative substructuring methods with Lagrange multipliers for the elliptic system of linear elasticity are considered. The algorithms belong to the family of dual-primal FETI methods which was introduced for linear elasticity problems in the plane by Farhat et al. [2001] and then extended to three dimensional elasticity problems by Farhat et al. [2000]. In dual-primal FETI methods, some continuity constraints on primal displacement variables are required to hold throughout the iterations, as in primal iterative substructuring methods, while most of the constraints are enforced by the use of dual Lagrange multipliers, as in the older one-level FETI algorithms. The primal constraints should be chosen so that the local problems become invertible. They also provide a coarse problem and they should be chosen so that the iterative method converges rapidly.

Recently, the family of algorithms for scalar elliptic problems in three dimensions was extended and a theory was provided in Klawonn et al. [2002a,b]. It was shown that the condition number of the dual-primal FETI methods can be bounded polylogarithmically as a function of the dimension of the individual subregion problems and that the bounds can otherwise be made independent of the number of subdomains, the mesh size, and jumps in the coefficients.

In the case of the elliptic system of partial differential equations arising from linear elasticity, essential changes in the selection of the primal constraints have to be made in order to obtain the same quality bounds for elasticity problems as in the scalar case. Special emphasis is given to developing robust condition number estimates with bounds which are independent of arbitrarily large jumps of the material coefficients. For benign coefficients, without large jumps, selecting an appropriate set of edge averages as primal constraints are sufficient to obtain good bounds, whereas for arbitrary coefficient distributions, additional primal first order moments are also required.

We have recently introduced the Boundary Element Tearing and Interconnecting (BETI) methods as boundary element counterparts of the well-established Finite Element Tearing and Interconnecting (FETI) methods. Since Finite Element Methods (FEM) and Boundary Element Methods (BEM) have certain complementary properties, it is sometimes very useful to couple these discretization techniques and to benefit from both worlds. Combining our BETI techniques with the FETI methods gives new, quite attractive tearing and interconnecting parallel solvers for large scale coupled boundary and finite element equations. There is an unified framework for coupling, handling, and analyzing both methods. In particular, the FETI methods can benefit from preconditioning components constructed by boundary element techniques. This is especially true for sparse versions of the boundary element method such as the fast multipole method which avoid fully populated matrices arising in classical boundary element methods.

The simulation of flow in porous media is a computationally demanding task. Thermodynamical equilibrium calculations and complex, heterogeneous geological structures normally gives a multiphysics/multidomain problem to solve. Thus, efficient solution methods are needed. The research simulator

Athena

is a 3D, multiphase, multicomponent, porous media flow simulator. A parallel version of the simulator was developed based on a non-overlapping domain decomposition strategy, where the domains are defined a-priori from e.g. geological data. Selected domains are refined with locally matching grids, giving a globally non-matching, unstructured grid. In addition to the space domain, novel algorithms for parallel processing in time based on a predictor-corrector strategy has been successfully implemented.

We discuss how the domain decomposition framework can be used to include different physical and numerical models in selected sub-domains. Also we comment on how the two-level solver relates to multiphase upscaling techniques.

Adding communication functionality enables the original serial version to run on each sub-domain in parallel. Motivated by the need for larger time steps, an implicit formulation of the mass transport equations has been formulated and implemented in the existing parallel framework. Further, as the Message Passing Interface (MPI) is used for communication, the simulator is highly portable. Through benchmark experiments, we test the new formulation on platforms ranging from commercial super-computers to heterogeneous networks of workstations.

We shortly review the uncoupling-coupling method, a Markov chain Monte Carlo based approach to compute statistical properties of systems like medium-sized biomolecules. This technique has recently been proposed for the efficient computation of biomolecular conformations. One crucial step of UC is the decomposition of reversible nearly uncoupled Markov chains into rapidly mixing subchains. We show how the underlying scheme of uncoupling-coupling can also be applied to stochastic differential equations where it can be translated into a domain decomposition technique for partial differential equations.

The construction of accurate generalized impedance boundary conditions for the three-dimensional acoustic scattering problem by a homogeneous dissipative medium is analyzed. The technique relies on an explicit computation of the symbolic asymptotic expansion of the exact impedance operator in the interior domain. An efficient pseudolocalization of this operator based on Padé approximants is then proposed. The condition can be easily integrated in an iterative finite element solver without modifying its performances since the pseudolocal implementation preserves the sparse structure of the linear system. Numerical results are given to illustrate the method.

We present a way to efficiently treat the well-known transparent boundary conditions for the Schrödinger equation. Our approach is based on two ideas: firstly, to derive a discrete transparent boundary condition (DTBC) based on the Crank-Nicolson finite difference scheme for the governing equation. And, secondly, to approximate the discrete convolution kernel of DTBC by sum-of-exponentials for a rapid recursive calculation of the convolution. We illustrate the efficiency of the proposed method on several examples.

A much more detailed version of this article can be found in Arnold et al. [2003].

Two techniques are coupled to solve a model problem relative to the scattering of a 2D time-harmonic electromagnetic wave by an obstacle including an electrically deep cavity. Both of them are based on a boundary element method. The first technique uses a domain decomposition procedure to reduce the contribution of the cavity to a set of equations supported by the aperture. The second one is an additive Schwarz procedure to solve the problem after the reduction of the cavity. Numerical results are reported to give an insight into the approach.

The paper presents a conceptual model and details of an implementation for parallel adaptive finite element systems, particularly their computational kernels. The whole methodology is based on domain decomposition while message passing is used as a model of programming. The proposed finite element architecture consist of independent modules, most of them taken from sequential codes. The sequential modules are only slightly modified for parallel execution and three new modules, explicitly aimed at handling parallelism, are added. The most important new module is the domain decomposition manager that performs most tasks related to parallel execution. An example implementation that utilizes 3D prismatic meshes and discontinuous Galerkin approximation is presented. Two numerical examples, the first in which Laplace's equation is approximated using GMRES with multi-grid preconditioning and the second where dynamic adaptivity with load balancing is utilized for simulating linear convection, illustrate capabilities of the approach.

Most finite element, or finite volume software is built around a fixed mesh data structure. Therefore, each software package can only be used efficiently for a relatively narrow class of applications. For example, implementations supporting unstructured meshes allow the approximation of complex geometries but are in general much slower and require more memory than implementations using structured meshes. In this paper we show how a generic mesh interface can be defined such that one algorithm, e. g. a discretization scheme, works on different mesh implementations. For a cell centered finite volume scheme we show that the same algorithm runs thirty times faster on a structured mesh implementation than on an unstructured mesh and is only four times slower than a non-generic version for a structured mesh. The generic mesh interface is realized within the

Distributed Unified Numerics Environment

DUNE.

We present a new concept for the realization of finite element computations on parallel machines with distributed memory. The parallel programming model is based on a dynamic data structure addressed by points. All geometric objects (cells, faces, edges) are referenced by their midpoints, and all algebraic data structures (vectors and matrices) are tied to the nodal points of the finite elements. The parallel distribution of all objects is determined by processor lists assigned to the reference points.

Based on this new model for Distributed Point Objects (DPO) a first application to a geotechnical application with Taylor-Hood elements on hexahedra has been presented in Wieners et al. [2004]. Here, we consider the extension to parallel refinement, curved boundaries, and multigrid preconditioners. Finally, we present parallel results for a nonlinear model problem with isoparametric cubic elements.

The standard local defect correction (LDC) method has been extended to include multilevel adaptive gridding, domain decomposition, and regridding. The domain decomposition algorithm provides a natural route for parallelization by employing many small tensor-product grids, rather than a single large unstructured grid. The algorithm is applied to a laminar Bunsen flame with one-step chemistry.

The domain decomposition method is directed to electronic packaging simulation in this article. The objective is to address the entire simulation process chain, to alleviate user interactions where they are heavy to mechanization by component approach to streamline the model simulation process.

Inexact Newton method with backtracking is one of the most popular techniques for solving large sparse nonlinear systems of equations. The method is easy to implement, and converges well for many practical problems. However, the method is not robust. More precisely speaking, the convergence may stagnate for no obvious reason. In this paper, we extend the recent work of Tuminaro, Walker and Shadid [2002] on detecting the stagnation of Newton method using the angle between the Newton direction and the steepest descent direction. We also study a nonlinear additive Schwarz preconditioned inexact Newton method, and show that it is numerically more robust. Our discussion will be based on parallel numerical experiments on solving some high Reynolds numbers steady-state incompressible Navier-Stokes equations in the velocity-pressure formulation.

The numerical simulation of turbulent indoor-air flows is performed using iterative substructuring methods. We present a framework for coupling eddyviscosity turbulence models based on the non-stationary, incompressible, nonisothermal Navier-Stokes problem with non-isothermal near-wall models; this approach covers the

k

/ε model with an improved wall function concept. The iterative process requires the fast solution of linearized Navier-Stokes problems and of advection-diffusion-reaction problems. These subproblems are discretized using stabilized FEM together with a shock-capturing technique. For the linearized problems we apply an iterative substructuring technique which couples the subdomain problems via Robin-type transmission conditions. The method is applied to a benchmark problem, including comparison with experimental data by Tian and Karayiannis [2000] and to realistic ventilation problems.

Direct numerical solution of the highly nonlinear equations governing even the most simplified models of fluid-structure interaction requires that both the flow field and the domain shape be determined as part of the solution since neither is known

a priori

. To accomplish this, previous algorithms have decoupled the solid and fluid mechanics, solving for each separately and converging iteratively to a solution which satisfies both. In this paper, we describe a nonconforming finite element method which solves the problem of interaction between a viscous incompressible fluid and a structure whose deformation defines the interface between the two simultaneously. A general methodology is described for the model 2D problem and the algorithm is validated computationally for a one-dimensional example.

Viscous-inviscid coupling methods for the computation of aerodynamic boundary layers are discussed, with emphasis on the quasi-simultaneous method. Its interaction law is analysed using matrix theory and reduced to its essentials. The redesigned interaction law is tested for separated airfoil flow at maximum lift.

We investigate the performance of domain decomposition methods for solving the Poisson equation on the surface of the sphere. This equation arises in a global weather model as a consequence of an implicit time discretization.We consider two different types of algorithms: the Dirichlet-Neumann algorithm and the optimal Schwarz method. We show that both algorithms applied to a simple two subdomain decomposition of the surface of the sphere converge in two iterations. While the Dirichlet-Neumann algorithm achieves this with local transmission conditions, the optimal Schwarz algorithm needs non-local transmission conditions. This seems to be a disadvantage of the optimal Schwarz method. We then show however that for more than two subdomains or overlapping subdomains, both the optimal Schwarz algorithm and the Dirichlet Neumann algorithm need non-local interface conditions to converge in a finite number of steps. Hence the apparent advantage of Dirichlet-Neumann over optimal Schwarz is only an artifact of the special two subdomain decomposition.

We are interested in a robust and accurate domain decomposition method with arbitrary interface conditions on non-matching grids using a finite volume discretization. We introduce transmission operators to take into account the non-matching grids. Under compatibility assumptions, we have the well-posedness of the global problem and of the local subproblems with a new discretization of the arbitrary interface conditions. Then, we give two error estimates in the discrete

H

1

norm: the first one is in

O

(

h

1/2

) with

L

2

orthogonal projections onto piecewise functions along the interface and the second one in

O

(

h

) with transmission conditions based on a linear rebuilding along the interface. Finally, numerical results confirm the theory. Particular attention is paid to the situation with non matching grids and highly heterogeneous coefficients both across and inside subdomains. The addition of a third very thin subdomain between geological blocks is necessary to ensure a good accuracy.

We analyze the convergence behavior of the overlapping Schwarz waveform relaxation algorithm applied to nonlinear advection problems. We show for Burgers' equation that the algorithm converges super-linearly at a rate which is asymptotically comparable to the rate of the algorithm applied to linear advection problems. The convergence rate depends on the overlap and the length of the time interval. We carefully track dependencies on the viscosity parameter and show the robustness of all estimates with respect to this parameter.

We present and analyze a new nonconforming domain decomposition method based on a Schwarz method with Robin transmission conditions. We prove that the method is well posed and convergent. Our error analysis is valid in two dimensions for piecewise polynomials of low and high order and also in three dimensions for

P

1

elements. We further present an efficient algorithm in two dimensions to perform the required projections between arbitrary grids. We finally illustrate the new method with numerical results.

For advection-diffusion problems we show that a non-overlapping domain decomposition method with interface conditions of Robin type can be accelerated by using a critical parameter of the transmission condition in a cyclic way.

We propose a new stabilized three-field formulation applied to the advection-diffusion equation. Using finite elements with SUPG stabilization in the interior of the subdomains our approach enables us to use almost arbitrary discrete function spaces. They need not to satisfy the inf-sup conditions of the standard three-field formulation. The scheme is stable and satisfies an optimal a priori estimate. Furthermore, we show how the scheme can be solved efficiently in parallel by an adapted Schur complement equation and an alternating Schwarz algorithm. Finally some numerical experiments confirm our theoretical results.

Interface boundary conditions are the key ingredient to design efficient domain decomposition methods. However, convergence cannot be obtained for any method in a number of iterations less than the number of subdomains minus one in the case of a one-way splitting. This optimal convergence can be obtained with generalized Robin type boundary conditions associated with an operator equal to the Schur complement of the outer domain. Since the Schur complement is too expensive to compute exactly, a new approach based on the computation of the exact Schur complement for a small patch around each interface node is presented for the two-Lagrange multiplier FETI method.

We present overlapping Schwarz methods for the numerical solution of two model problems of delay PDEs: the heat equation with a fixed delay term, and the heat equation with a distributed delay in the form of an integral over the past. We first analyze properties of the solutions of these PDEs and find that their dynamics is fundamentally different from that of regular time-dependent PDEs without time delay. We then introduce and study overlapping Schwarz methods of waveform relaxation type for the two model problems. These methods compute the local solution in each subdomain over many time-levels before exchanging interface information to neighboring subdomains. We analyze the effect of the overlap and derive optimized transmission conditions of Robin type. Finally we illustrate the theoretical results and convergence estimates with numerical experiments.

In recent years the hybrid-Trefftz finite element (hT-FE) model, which originated in the work by Jirousek and his collaborators and makes use of an independently defined auxiliary inter-element frame, has been considerably improved. It has indeed become a highly efficient computational tool for the solution of difficult boundary value problems In parallel and to a large extent independently, a general and elegant theory of Domain Decomposition Methods (DDM) has been developed by Herrera and his coworkers, which has already produced very significant numerical results. Theirs is a general formulation of DDM, which subsumes and generalizes other standard approaches. In particular, it supplies a natural theoretical framework for Trefftz methods. To clarify further this point, it is important to spell out in greater detail than has been done so far, the relation between Herrera's theory and the procedures studied by researchers working in standard approaches to Trefftz method (Trefftz-Jirousek approach). As a contribution to this end, in this paper the hybrid-Trefftz finite element model is derived in considerable detail, from Herrera's theory of DDM. By so doing, the hT-FE model is generalized to non-symmetric systems (actually, to any linear differential equation, or system of such equations, independently of its type) and to boundary value problems with prescribed jumps. This process also yields some numerical simplifications.

The hybridization technique is applied to replace the macro-hybrid mixed finite element problem for the diffusion equation by the equivalent cell-based formulation. The underlying algebraic system is condensed by eliminating the degrees of freedom which represent the interface flux and cell pressure variables to the system containing the Lagrange multipliers variables. An approach to the numerical solution of the condensed system is briefly discussed.

Domain decomposition techniques provide a powerful tool for the numerical approximation of partial differential equations. We consider mortar techniques with dual Lagrange multiplier spaces to couple different discretization schemes. It is well known that the discretization error for linear mortar finite elements in the energy norm is of order

h

. Here, we apply these techniques to curvilinear boundaries, nonlinear problems and the coupling of different model equations and discretizations.

In the last decade, non-conforming domain decomposition methods such as the mortar finite element method have been shown to be reliable techniques for several engineering applications that often employ complex finite element design. With this technique, one can conveniently assemble local subcomponents into a global domain without matching the finite element nodes of each subcomponent at the common interface. In this work, we present computational results for the convergence of a mortar finite element technique in three dimensions for a model problem. We employ the mortar finite element formulation in conjunction with higher-order elements, where both mesh refinement and degree enhancement are combined to increase accuracy. Our numerical results demonstrate optimality for the resulting non-conforming method for various discretizations.

We consider an additive Schwarz preconditioner for the algebraic system resulting from the discretization of second order elliptic equations with discontinuous coefficients, using the lowest order Crouzeix-Raviart element on nonmatching meshes. The overall discretization is based on the mortar technique for coupling nonmatching meshes. A convergence analysis of the preconditioner has recently been given in Rahman et al. [2003]. In this paper, we give a matrix formulation of the preconditioner, and discuss some of its numerical properties.

Second order elliptic problems with discontinuous coefficients are considered. The problem is discretized by the finite element method on geometrically conforming non-matching triangulations across the interface using the mortar technique. The resulting discrete problem is solved by a FETI-DP method. We prove that the method is convergent and its rate of convergence is almost optimal and independent of the jumps of coefficients. Numerical experiments for the case of four subregions are reported. They confirm the theoretical results.

We consider a FETI-DP formulation of the Stokes problem with mortar methods. To solve the Stokes problem correctly and efficiently, redundant continuity constraints are introduced. Lagrange multipliers corresponding to the redundant constraints are treated as primal variables in the FETI-DP formulation. We propose a preconditioner for the FETI-DP operator and show that the condition number of the preconditioned FETI-DP operator is bounded by

C

max

i

=1,…,

N

{(1 + log (

H

i

/h

i

))

2

}, where

H

i

and

h

i

are the subdomain size and the mesh size, respectively, and

C

is a constant independent of

H

i

and

h

i

.

Iterative substructuring methods with Lagrange multipliers for elliptic problems are considered. The algorithms belong to the family of dual-primal FETI methods which were introduced for linear elasticity problems in the plane by Farhat et al. [2001] and were later extended to three dimensional elasticity problems by Farhat et al. [2000]. Recently, the family of algorithms for scalar diffusion problems was extended to three dimensions and successfully analyzed by Klawonn et al. [2002a,b]. It was shown that the condition number of these dual-primal FETI algorithms can be bounded polylogarithmically as a function of the dimension of the individual subregion problems and that the bounds are otherwise independent of the number of subdomains, the mesh size, and jumps in the diffusion coefficients. In this article, numerical results for some of these algorithms are presented and their relation to the theoretical bounds is studied. The algorithms have been implemented in PETSc, see Balay et al. [2001], and their parallel scalability is analyzed.

The contribution deals with the numerical solving of contact problems with Coulomb friction for 3D bodies. A variant of the FETI based domain decomposition method is used. Numerical experiments illustrate the efficiency of our algorithm.

We investigate whether different choices of nonmortar sides for the geometrically conforming partitions inherent to FETI-DP influence the convergence of the algorithms for four different preconditioners. We conclude experimentally that they do not, although better condition number estimates exist for a Neumann-Dirichlet choice of nonmortars.

In this contribution, we are concerned with electrothermomechanical coupling problems as they arise in the modeling and simulation of high power electronic devices. In particular, we are faced with a hierarchy of coupled physical effects in so far as electrical energy is converted to Joule heat causing heat stresses that have an impact on the mechanical behavior of the devices and may lead to mechanical damage. Moreover, there are structural coupling effects due to the sandwich-like construction of the devices featuring multiple layers of specific materials with different thermal and mechanical properties. The latter motivates the application of domain decomposition techniques on nonmatching grids based on individual finite element discretizations of the substructures. We will address in detail the modeling aspects of the hierarchy of coupling phenomena as well as the discretization-related couplings in the numerical simulation of the operating behavior of the devices.

This work is the first step towards a multiphysics strategy for free-surface flows simulation. In particular, we present a strategy to couple one and two-dimensional hydrostatic free surface flow models. We aim to reduce the computational cost required by a full 2D model. After introducing the two models along with suitable a priori error estimates, we discuss the choice of convenient matching conditions stemming from the results obtained in Formaggia et al. [2001]. The numerical results in the last section confirm the soundness of our analysis.

The theory of

multilevel methods

for solving Ritz-Galerkin equations arising from discretization of elliptic boundary value problems is by now well developed. There exists a variety of survey talks and books in this area ( see e.g.Xu [1992],Yserentant [1993],Oswald [1994]). Among them the

additive methods

are based on a suitable decomposition of the underlying projection operator (thus including also domain decomposition methods). In particular there is a close connection with classical concepts in approximation theory via so- called Jackson and Bernstein inequalities. These provide norm equivalences with the bilinear form underlying the Ritz- Galerkin procedure and thus preconditioners for the arising stiffness matrix.

The size of the constants in this equivalence is crucial for the stability of the resulting iteration methods. In this note we establish

robust norm equivalences

with constants which are

independent

of the mesh size and depend only

weakly

on the ellipticity of the problem, including the case of strongly varying coefficients. Extensions to the case of coefficients with discontinuities are possible, see Scherer [2003/4]. In the case of piecewise constant coefficients on the initial coarse grid there exist already estimates of the condition numbers of BPX-type preconditioners independent of the coefficients (see Yserentant [1990], Bramble and J.Xu [1991]) however they depend still on the mesh size (of the finest level).

The main focus of this paper is to suggest a domain decomposition method for mixed finite element approximations of elliptic problems with anisotropic coefficients in domains. The theorems on traces of functions from Sobolev spaces play an important role in studying boundary value problems of partial differential equations. These theorems are commonly used for a priori estimates of the stability with respect to boundary conditions, and also play very important role in constructing and studying effective domain decomposition methods. The trace theorem for anisotropic rectangles with anisotropic grids is the main tool in this paper to construct domain decomposition preconditioners.

After stating an abstract convergence result for the parareal algorithm used in the parallelization in time of general partial differential equations, we analyze the stability and convergence properties of the algorithm for equations with constant coefficients. We show that suitably damping coarse schemes ensure unconditional stability of the parareal algorithm and analyze how the regularity of the initial condition influences convergence in the absence of sufficient damping.

The “parareal in time” algorithm introduced in Lions et al. [2001] enables parallel computation using a decomposition of the interval of time integration. In this paper, we adapt this algorithm to solve the challenging Navier-Stokes problem. The coarse solver, based on a larger timestep, may also involve a coarser discretization in space. This helps to preserve stability and provides for more significant savings.

This paper is the basic one of the series resulting from the minisymposium entitled “Recent Advances for the Parareal in Time Algorithm” that was held at DD15. The parareal in time algorithm is presented in its current version (predictor-corrector) and the combination of this new algorithm with other more classical iterative solvers for parallelization which makes it possible to really consider the time direction as fertile ground to reduce the time integration costs.

We discuss the stability of the Parareal algorithm for an autonomous set of differential equations. The stability function for the algorithm is derived, and stability conditions for the case of real eigenvalues are given. The general case of complex eigenvalues has been investigated by computing the stability regions numerically.

A multilevel homotopic adaptive finite element method is presented in this paper for convection dominated problems. By the homotopic method with respect to the diffusion parameter, the grids are iteratively adapted to better approximate the solution. Some new theoretic results and practical techniques for the grid adaptation are presented. Numerical experiments show that a standard finite element scheme based on this properly adapted grid works in a robust and efficient manner.

Parallel methods are not usually applied to the time domain because the sequential nature of time is considered to be a handicap for the development of competitive algorithms. However, this sequential nature can also play to our advantage by ensuring convergence within a given number of iterations. The novel parallel algorithm presented in this paper acts as a predictor corrector improving both speed and accuracy with respect to the sequential solvers. Experiments using our in house fluid flow simulator in porous media, Athena, show that our parallel implementation exhibit an optimal speed up relative to the method.

We introduce some nonlinear positive and negative interpolation operators. The interpolation need to preserve positivity or negativity of a function. In addition, the interpolation must be pointwise below or above the function. Some of the operators also have the pointwise monotone property over refined meshes. It is also desirable that the interpolation have the needed approximation and stability estimates. Those operators could be used in the convergence analysis for domain decomposition and multigrid methods for obstacle problems.

Theoretical and experimental results concerning a new FETI based algorithm for numerical solution of variational inequalities are reviewed. A discretized model problem is first reduced by the duality theory of convex optimization to the quadratic programming problem with bound and equality constraints. The latter is then optionally modified by means of orthogonal projectors to the natural coarse space introduced by Farhat and Roux in the framework of their FETI method. The resulting problem is then solved by a new variant of the augmented Lagrangian type algorithm with the inner loop for the solution of bound constrained quadratic programming problems. Recent theoretical results are reported that guarantee scalability of the algorithm. The results are confirmed by numerical experiments.

We consider the numerical simulation of multi-body contact problems in linear elasticity. For the discretization of the transmission conditions at the interface between the bodies by means of a transfer operator nonconforming domain decomposition methods (mortar methods) are used. Here, we focus on the difficulties related to the discrete choice of the transfer operator. We explain in detail how the transfer operator can be implemented in the case of three-dimensional nonplanar contact boundaries. For the numerical solution of the arising nonlinear systems of equations monotone multigrid methods are used, which do not require any regularization of the nonpenetration condition at the contact interface.

(

and Introduction

) In this paper, we present a family of domain decomposition based on Aitken like acceleration of the Schwarz method seen as an iterative procedure with linear rate of convergence. This paper is a generalization of the method first introduced in Garbey and Tromeur-Dervout [2001] that was restricted to Cartesian grids. The general idea is to construct an approximation of the eigenvectors of the trace transfer operator associated to dominant eigenvalues and accelerate these components after few Schwarz iterates. We consider here examples with the finite volume approximation on general quadrangle meshes of Faille [1992] and finite element discretization.

The

Fat Boundary Method

(

FBM

) is a fictitious domain like method for solving partial differential equations in a domain with holes

Ω ∖

$$\bar B$$

— where

B

is a collection of smooth open subsets — that consists in splitting the initial problem into two parts to be coupled via Schwartz type iterations: the solution, with a fictitious domain approach, of a problem set in the whole domain

Ω

, for which fast solvers can be used, and the solution of a collection of independent problems defined on narrow strips around the connected components of

B

, that can be performed fully in parallel. In this work, we give some results on a semi-discrete

FBM

in the framework of a finite element discretization, and we present some numerical experiments.

We derive an upscaled but accurate 2D model of the global behavior of an underground radioactive waste disposal. This kind of computation occurs in safety assessment process. Asymptotic development of the solution leads to solve terms of order 1 on more regular and steady-state auxiliary problems. Neumann-Dirichlet domain decomposition methods, with non matching spectral grids, are performed to solve those auxiliary problems. Fourier and Chebychev polynomials approximation of the solution are used depending on boundary conditions implemented on subdomains. Since spectral representation of the solution or its derivatives allows accurate mappings between the interfaces of the different grids, we speed up the convergence of the Neumann-Dirichlet method by the Aitken acceleration which is sensitive to the accuracy of the representation of the iterate solution on the artificial interfaces. In order to enforce regularity for the spectral approximation, some regular extensions and filtering techniques on the artificial interfaces for the right hand side of the problem and the iterate solution are implemented.

For flow problems in multi-layered porous media, one can define a natural non-overlapping domain decomposition (DD). The simplest way to obtain DDMs is to distribute interface conditions (pressure and flux continuity) for each pair of adjacent subdomains and to use the Dirichlet-Neumann (D-N) algorithm. A different way is the use of two Robin conditions (RC) also distributed for each subdomain (Robin-Method). The main inconvenience of both methods is that the convergence is not ensured. To obtain efficient methods, we retain from previous works two basic ideas: an acceleration of Aitken type for the D-N algorithm and finding optimized coefficients for the Robin-Method. In the present paper, we analyze these improved algorithms in 1-D and 2-D framework for flow problems in heterogeneous porous media and we present a numerical comparison.

The main goal of this paper is to discuss the numerical simulation of propagation phenomena for time harmonic electromagnetic waves by methods combining controllability and fictitious domain techniques. These methods rely on distributed Lagrangian multipliers, which allow the propagation to be simulated on an obstacle free computational region using regular finite element meshes essentially independent of the geometry of the obstacle and on a controllability formulation which leads to algorithms with good convergence properties to time-periodic solutions. This novel methodology has been validated by the solutions of test cases associated to non trivial geometries, possibly non-convex. The numerical experiments show that the new method performs as well as the method discussed in Bristeau et al. [1998] where obstacle fitted meshes were used.

This paper presents an overlapped block-parallel Newton method for solving large nonlinear systems. The graph partitioning algorithms are first used to partition the Jacobian into weakly coupled overlapping blocks. Then the simplified Newton iteration is directly performed, with the diagonal blocks and the overlapping solutions assembled in a weighted average way at each iteration. In the algorithmic implementation, an accelerated technique has been proposed to reduce the number of iterations. The conditions under which the algorithm is locally and semi-locally convergent are studied. Numerical results from solving power flow equations are presented to support our study.

Balancing and dual Domain Decomposition Methods (DDMs) are used in practice on parallel computing environments with the number of generated subdomains being generally larger than the number of available processors. The present study describes partitioning concepts used to: (a) generate subdomains for such DDMs and (b) organize these subdomains into subdomain clusters, in order to assign each cluster to a processor. The discussion concerns distributed computing environments with dedicated homogeneous processors, as well as with heterogeneous and/or non-dedicated processors. The FETI method is used to obtain numerical results demonstrating the merits of the described partitioning algorithms.

We present iterative subdomain methods based on a domain decomposition approach to solve the coupled Stokes/Darcy problem using finite elements. The dependence of the convergence rate on the grid parameter

h

and on the physical data is discussed; some difficulties encountered when applying the algorithms are indicated together with possible improvement strategies.

In this work we discuss parallel preconditioning techniques for the bidomain equations, a non-linear system of partial differential equations which is widely used for describing electrical activity in cardiac tissue. We focus on the solution of the linear system associated with the elliptic part of the bidomain model, since it dominates computation, with the preconditioned conjugate gradient method. We compare different parallel preconditioning techniques, such as block incomplete LU, additive Schwarz and multigrid. The implementation is based on the PETSc library and we report results for a 16-node HP cluster. The results suggest the multigrid preconditioner is the best option for the bidomain equations.

The goal of this paper is the construction of a data-sparse approximation to the Schur complement on the interface corresponding to FEM and BEM approximations of an elliptic equation by domain decomposition. Using the hierarchical (

ℌ

-matrix) formats we elaborate the

approximate Schur complement inverse

in an explicit form. The required cost

$$\mathcal{O}$$

(

N

Γ

log

q

N

Γ

) is almost linear in

N

Γ

— the number of degrees of freedom on the interface. As input, we use the Schur complement matrices corresponding to subdomains and represented in the

ℌ

-matrix format. In the case of piecewise constant coefficients these matrices can be computed via the BEM representation with the cost

$$\mathcal{O}$$

(

N

Γ

log

q

N

Γ

), while in the general case the FEM discretisation leads to the complexity

O

(

N

Ω

log

q

N

Ω

).

We present Neumann-Neumann domain decomposition preconditioners for the solution of elliptic linear quadratic optimal control problems. The preconditioner is applied to the optimality system. A Schur complement formulation is derived that reformulates the original optimality system as a system in the state and adjoint variables restricted to the subdomain boundaries. The application of the Schur complement matrix requires the solution of subdomain optimal control problems with Dirichlet boundary conditions on the subdomain interfaces. The application of the inverses of the subdomain Schur complement matrices require the solution of subdomain optimal control problems with Neumann boundary conditions on the subdomain interfaces. Numerical tests show that the dependence of this preconditioner on mesh size and subdomain size is comparable to its counterpart applied to elliptic equations only.

In this paper, we present several domain decomposition preconditioners for high-order Spectral Nédélec element discretizations for a Maxwell model problem in

H

(

curl

), in particular overlapping Schwarz preconditioners and Balancing Neumann-Neumann preconditioners. For an efficient and fast implementation of these preconditioners, fast matrix-vector products and direct solvers for problems posed on one element or a small array of elements are needed. In previous work, we have presented such algorithms for the two-dimensional case; here, we will present a new fast solver that works both in the two- and three-dimensional case. Next, we define the preconditioners considered in this paper, present numerical results for overlapping methods in three dimensions and Balancing Neumann-Neumann methods in two dimensions. We will also give a condition number estimate for the overlapping Schwarz method.

The model problem is: Find

u

ε

H

0

(

curl

,

Ω

) such that for all

v

ε

H

0

(

curl

,

Ω

)

$$a(u,v): = (\alpha u,v) + (\beta CURLu,CURLv) = (f,v)$$

.

Here,

Ω

is a bounded, open, connected polyhedron in

$$\mathbb{R}$$

3

or a polygon in

$$\mathbb{R}$$

2

,

H

(

curl

Ω

) is the space of vectors in (

L

2

(

Ω

))

2

or (

L

2

(

Ω

))

3

with

curl

in

L

2

(

Ω

) or (

L

2

(

Ω

))

3

, respectively;

H

0

(

curl

Ω

) is its subspace of vectors with vanishing tangential components on

∂Ω

;

f

ε (

L

2

(

Ω

))

d

for

d

= 2, 3, and (·, ·) denotes the inner product in

L

2

(

Ω

) of functions or vector fields. For simplicity, we will assume that

α

and

β

are piecewise constant.

The aim of this work is to reduce the development costs of new domain decomposition methods and to develop the parallel distributed software adapted to high performance computers. A new approach to development of the domain decomposition software system is suggested; it is based on the object-oriented analysis and middleware CORBA, MPI. In this paper, the main steps of domain decomposition are determined, the object-oriented framework is described, and then it is extended for parallel distributed computing. The given examples demonstrate that the software developed in such a way provides mathematical clarity and rapid implementation of the parallel algorithms.

We present two non-overlapping domain decomposition based two-level Newton schemes for solving nonlinear problems and demonstrate their effectiveness by analyzing systems with balanced and unbalanced nonlinearities. They both have been implemented in parallel and show good scalability. The implementations accommodate non-symmetric matrices and unstructured meshes.

We report on recent results related to domain decomposition methods based on the Discontinuous Galerkin discretizations of Stokes equations. We analyze the efficiency of a block nonoverlapping Schwarz preconditioner based on the approach by Feng and Karakashian [2001]. We also prove the inf-sup stability of a substructuring method.

Hierarchical matrices provide a technique to efficiently compute and store explicit approximations to the inverses of stiffness matrices computed in the discretization of partial differential equations. In a previous paper, Le Borne [2003], it was shown how standard ℌ-matrices must be modified in order to obtain good approximations in the case of a convection dominant equation with a constant convection direction. This paper deals with a generalization to arbitrary (non-constant) convection directions. We will show how these ℌ-matrix approximations to the inverse can be used as preconditioners in iterative methods.

In this paper we study the parallel performance of some nonlinear additive Schwarz preconditioned inexact Newton methods for solving large sparse system of nonlinear equations arising from the discretization of partial differential equations. The main idea of nonlinear preconditioning is to replace an ill-conditioned nonlinear system by an equivalent nonlinear system that has more balanced nonlinearities. In addition to balance the nonlinearities through nonlinear preconditioning, we also need to make sure that the multilayered iterative solver is scalable with respect to the number of processors. We focus on some two-level nonlinear additive Schwarz preconditioners, and show numerically that these two-level methods can reduce the nonlinearities and at the same time maintain the parallel scalability. Parallel numerical results for some high Reynolds number incompressible Navier-Stokes equations will be presented.

During the last few years, an algebraic formulation of Schwarz methods was developed. In this paper this algebraic formulation is used to prove new convergence results for multiplicative Schwarz methods when applied to consistent singular systems of linear equations. Coarse grid corrections are also studied. In particular, these results are applied to the numerical solutions of Markov chains.

We are interested in solving time dependent problems using domain decomposition method. In the classical methods, one discretizes first the time dimension and then one solves a sequence of steady problems by a domain decomposition method. In this paper, we study a Schwarz Waveform Relaxation method which treats directly the time dependent problem. We propose algorithms for the viscous Shallow Water equations.

The alternate strip-based iterative substructuring algorithms are preconditioning techniques for the discrete systems which arise from the finite element approximation of symmetric elliptic boundary value problems. The algorithms presented in this paper may be viewed as simple, direct extensions of the two disjoint subdomains case to the multiple domains decomposition with interior cross-points. The separate treatment of vertex points is avoided by dividing the original nonoverlapping subdomains into strip-subregions. Both scalability and efficiency are enhanced by alternating the direction of the strips.

We present and study a parallel iterative solver for reaction-diffusion systems in three dimensions arising in computational electrocardiology, such as the Bidomain and Monodomain models. The models include intramural fiber rotation and anisotropic conductivity coefficients that can be fully orthotropic or axially symmetric around the fiber direction. These cardiac models are coupled with a membrane model for the ionic currents, consisting of a system of ordinary differential equations. The solver employs structured isoparametric

Q

1

finite elements in space and a semi-implicit adaptive method in time. Parallelization and portability are based on the PETSc parallel library and large-scale computations with up to

O

(10

7

) unknowns have been run on parallel computers. These simulation of the full Bidomain model (without operator or variable splitting) for a full cardiac cycle are, to our knowledge, among the most complete in the available literature.

In this paper we present new numerical approach to solve the continuous casting problem. The main tool is to use IPEC method and DDM similar to Lapin and Pieska [2002] with multilevel domain decomposition. On the subdomains we use multidecomposition of the subdomains. The IPEC is used both in the whole calculation domain and inside the subdomains. The calculation algorithm is presented and numerically tested. Several conclusions are made and discussed.