Parallel adaptive time domain decomposition for stiff systems of ODEs/DAEs

Time domain decompositions to solve ODEs/DAEs have been numerically investigated by introducing adaptivity in the definition of the refinement of the time grid, time domain splitting. We show that the parareal method [Lions J-L, Maday Y, Turinici G. Résolution d’EDP par un schéma en temps “pararéel”, CRAS Sér I Math 2000;332(7):661-8] is a particular case of the multiple shooting method of Deuflhard. Numerical evidences of the limitation of this method to solve very stiff problems are exhibited, leading us to propose an adaptive parallel extrapolation method.     

A Domain Decomposition Preconditioner for p-FEM Discretizations of Two-dimensional Elliptic Problems

In this paper, a uniformly elliptic second order boundary value problem in 2-D discretized by the p-version of the finite element method is considered. An inexact Dirichlet-Dirichlet domain decomposition pre-conditioner for the system of linear algebraic equations is investigated. Two solvers for the problem in the sub-domains, a pre-conditioner for the Schur-complement and an extension operator operating from the edges of the elements into the interior are proposed as ingredients for the inexact DD-pre-conditioner. In the main part of the paper, several numerical experiments on a parallel computer are given.     

Numerical Integrations and Unit Resolution Multipliers for Domain Decomposition Methods with Nonmatching Grids

In this paper, we are concerned with the non-overlapping domain decomposition method (DDM) with nonmatching grids for three-dimensional problems. The weak continuity of the DDM solution on the interface is imposed by some Lagrange multiplier. We shall first analyze the influence of the numerical integrations over the interface on the (non-conforming) approximate solution. Then we will propose a simple approach to construct multiplier spaces, one of which can be simply spanned by some smooth basis functions with local compact supports, and thus makes the numerical integrations on the interface rather simple and inexpensive. Also it is shown this multiplier space can generate an optimal approximate solution. Numerical results are presented to compare the new method with the point to point method widely used in engineering.     

Solving the signorini problem on the basis of domain decomposition techniques

The finite element discretization of the Signorini Problem leads to a large scale constrained minimization problem. To improve the convergence rate of the projection method preconditioning must be developed. To be effective, the relative condition number of the system matrix with respect to the preconditioning matrix has to be small and the applications of the preconditioner as well as the projection onto the set of feasible elements have to be fast computable. In this paper, we show how to construct and analyze such preconditioners on the basis of domain decomposition techniques. The numerical results obtained for the Signorini problem as well as for contact problems in plane elasticity confirm the theoretical analysis quite well.     

Nitsche Type Mortaring for Singularly Perturbed Reaction-diffusion Problems

The paper is concerned with the Nitsche mortaring in the framework of domain decomposition where non-matching meshes and weak continuity of the finite element approximation at the interface are admitted. The approach is applied to singularly perturbed reaction-diffusion problems in 2D. Non-matching meshes of triangles being anisotropic in the boundary layers are applied. Some properties as well as error estimates of the Nitsche mortar finite element schemes are proved. In particular, using a suitable degree of anisotropy of triangles in the boundary layers of a rectangle, convergence rates as known for the conforming finite element method are derived. Numerical examples illustrate the approach and the results.     

BDDC and FETI-DP preconditioners for spectral element discretizations

Two of the most recent and important nonoverlapping domain decomposition methods, the BDDC method (Balancing Domain Decomposition by Constraints) and the FETI-DP method (Dual-Primal Finite Element Tearing and Interconnecting) are here extended to spectral element discretizations of second-order elliptic problems. In spite of the more severe ill-conditioning of the spectral element discrete systems, compared with low-order finite elements and finite differences, these methods retain their good properties of scalability, quasi-optimality and independence on the discontinuities of the elliptic operator coefficients across subdomain interfaces.     

An Algebraic Multigrid Method for Higher-order Finite Element Discretizations

In this paper, we will design and analyze a class of new algebraic multigrid methods for algebraic systems arising from the discretization of second order elliptic boundary value problems by high-order finite element methods. For a given sparse stiffness matrix from a quadratic or cubic Lagrangian finite element discretization, an algebraic approach is carefully designed to recover the stiffness matrix associated with the linear finite element disretization on the same underlying (but nevertheless unknown to the user) finite element grid. With any given classical algebraic multigrid solver for linear finite element stiffness matrix, a corresponding algebraic multigrid method can then be designed for the quadratic or higher order finite element stiffness matrix by combining with a standard smoother for the original system. This method is designed under the assumption that the sparse matrix to be solved is associated with a specific higher order, quadratic for example, finite element discretization on a finite element grid but the geometric data for the underlying grid is unknown. The resulting new algebraic multigrid method is shown, by numerical experiments, to be much more efficient than the classical algebraic multigrid method which is directly applied to the high-order finite element matrix. Some theoretical analysis is also provided for the convergence of the new method.     

Two-level methods for the single layer potential in ℝ3

We consider weakly singular integral equations of the first kind on open surface pieces Γ in ℝ³. To obtain approximate solutions we use theh-version Galerkin boundary element method. Furthermore we introduce two-level additive Schwarz operators for non-overlapping domain decompositions of Γ and we estimate the conditions numbers of these operators with respect to the mesh size. Based on these operators we derive an a posteriori error estimate for the difference between the exact solution and the Galerkin solution. The estimate also involves the error which comes from an approximate solution of the Galerkin equations. For uniform meshes and under the assumption of a saturation condition we show reliability and efficiency of our estimate. Based on this estimate we introduce an adaptive multilevel algorithm with easily computable local error indicators which allows direction control of the local refinements. The theoretical results are illustrated by numerical examples for plane and curved surfaces. Supported by the German Research Foundation (DFG) under grant Ste 238/25-9.     

h-p Spectral Element Method for Elliptic Problems on Non-smooth Domains Using Parallel Computers

We propose a new h-p spectral element method to solve elliptic boundary value problems with mixed Neumann and Dirichlet boundary conditions on non-smooth domains. The method is shown to be exponentially accurate and asymptotically faster than the standard h-p finite element method. The spectral element functions are fully non-conforming for pure Dirichlet problems and conforming only at the vertices of the elements for mixed problems, and hence, the dimension of the resulting Schur complement matrix is quite small. The method is a least-squares collocation method and the resulting normal equations are solved using preconditioned conjugate gradient method with an almost optimal preconditioner. The algorithm is suitable for a distributed memory parallel computer. The numerical results of a number of model problems are presented, which confirm the theoretical estimates.     

Higher Order Sparse Grid Methods for Elliptic Partial Differential Equations with Variable Coefficients

We present a method for discretizing and solving general elliptic partial differential equations on sparse grids employing higher order finite elements. On the one hand, our approach is charactarized by its simplicity. The calculation of the occurring functionals is composed of basic pointwise or unidirectional algorithms. On the other hand, numerical experiments prove our method to be robust and accurate. Discontinuous coefficients can be treated as well as curvilinearly bounded domains. When applied to adaptively refined sparse grids, our discretization results to be highly efficient, yielding balanced errors on the computational domain.     

Theoretically supported scalable BETI method for variational inequalities

Summary The Boundary Element Tearing and Interconnecting (BETI) methods were recently introduced as boundary element counterparts of the well established Finite Element Tearing and Interconnecting (FETI) methods. Here we combine the BETI method preconditioned by the projector to the “natural coarse grid” with recently proposed optimal algorithms for the solution of bound and equality constrained quadratic programming problems in order to develop a theoretically supported scalable solver for elliptic multidomain boundary variational inequalities such as those describing the equilibrium of a system of bodies in mutual contact. The key observation is that the “natural coarse grid” defines a subspace that contains the solution, so that the preconditioning affects also the non-linear steps. The results are validated by numerical experiments.      

Anisotropic error estimates for an interpolant defined via moments

Summary An interpolant defined via moments is investigated for triangles, quadrilaterals, tetrahedra, and hexahedra and arbitrarily high polynomial degree. The elements are allowed to have diameters with different asymptotic behavior in different space directions. Anisotropic interpolation error estimates are proved.      

Adaptive sparse grid multilevel methods for elliptic PDEs based on finite differences

We present a multilevel approach for the solution of partial differential equations. It is based on a multiscale basis which is constructed from a one-dimensional multiscale basis by the tensor product approach. Together with the use of hash tables as data structure, this allows in a simple way for adaptive refinement and is, due to the tensor product approach, well suited for higher dimensional problems. Also, the adaptive treatment of partial differential equations, the discretization (involving finite differences) and the solution (here by preconditioned BiCG) can be programmed easily. We describe the basic features of the method, discuss the discretization, the solution and the refinement procedures and report on the results of different numerical experiments.     

Anisotropic interpolation error estimates for isoparametric quadrilateral finite elements

Anisotropic local interpolation error estimates are derived for quadrilateral and hexahedral Lagrangian finite elements with straight edges. These elements are allowed to have diameters with different asymptotic behaviour in different space directions. The case of affine elements (parallel-epipeds) with arbitrarily high degree of the shape functions is considered first. Then, a careful examination of the multi-linear map leads to estimates for certain classes of more general, isoparametric elements. As an application, the Galerkin finite element method for a reaction diffusion problem in a polygonal domain is considered. The boundary layers are resolved using anisotropic trapezoidal elements.     

On the inf–sup Condition for the P mod 3 / P disc 2 Element

We consider a recently introduced triangular nonconforming finite element of third-order accuracy in the energy norm called P^mod₃ element. We show that this finite element is appropriate for approximating the velocity in incompressible flow problems since it satisfies an inf-sup condition for discontinuous piecewise quadratic pressures.     

The hierarchial preconditioning on unstructured grids

We present the implementation of two hierarchically preconditioned methods for the fast solution of mesh equations that approximate 2D-elliptic boundary value problems on unstructured quasi uniform triangulations. Based on the fictitious space approach the original problem can be embedded into an auxiliary one, where both the hierarchical grid information and the preconditioner are well defined. We implemented the corresponding Yserentant preconditioned conjugate gradient method as well as thebpx-preconditioned cg-iteration having optimal computational costs. Several numerical examples demonstrate the efficiency of the artificially constructed hierarchical methods which can be of importance in industrial engineering, where often only the nodal coordinates and the element connectivity of the underlying (fine) discretization are available.     

Robust Multigrid Methods for Nearly Incompressible Elasticity

We consider multigrid methods for problems in linear elasticity which are robust with respect to the Poisson ratio. Therefore, we consider mixed approximations involving the displacement vector and the pressure, where the pressure is approximated by discontinuous functions. Then, the pressure can be eliminated by static condensation. The method is based on a saddle point smoother which was introduced for the Stokes problem and which is transferred to the elasticity system. The performance and the robustness of the multigrid method are demonstrated on several examples with different discretizations in 2D and 3D. Furthermore, we compare the multigrid method for the saddle point formulation and for the condensed positive definite system. Received February 5, 1999; revised October 5, 1999     

A variational approximation method for 2nd order elliptic eigenvalue problems in a composite structure with nonstandard boundary conditions

In this paper we deal with the finite element analysis of a class of eigenvalue problems (EVPs) in a composite structure in the plane, consisting of rectangular subdomains which enclose an intermediate region. Nonlocal boundary conditions (BCs) of Robin type are imposed on the inner boundaries, i.e. on the interfaces of the respective subdomains with the intermediate region. On the eventual interfaces between two subdomains we impose discontinuous transition conditions (TCs). Finally, we have classical local BCs at the outer boundaries. Such problems are related to some heat transfer problems e.g. in a horizontal cross section of a wall enclosing an air cave.     

Multilevel Gauging for Edge Elements

The vector potential of a solenoidal vector field, if it exists, is not unique in general. Any procedure that aims to determine such a vector potential typically involves a decision on how to fix it. This is referred to by the term gauging. Gauging is an important issue in computational electromagnetism, whenever discrete vector potentials have to be computed. In this paper a new gauging algorithm for discrete vector potentials is introduced that relies on a hierarchical multilevel decomposition. With minimum computational effort it yields vector potentials whose L ²-norm does not severely blow up. Thus the new approach compares favorably to the widely used co-tree gauging. Received May 27, 1999; revised October 22, 1999     

Nitsche Type Mortaring for some Elliptic Problem with Corner Singularities

The paper deals with Nitsche type mortaring as a finite element method (FEM) for treating non-matching meshes of triangles at the interface of some domain decomposition. The approach is applied to the Poisson equation with Dirichlet boundary conditions (as a model problem) under the aspect that the interface passes re-entrant corners of the domain. For such problems and non-matching meshes with and without local refinement near the re-entrant corner, some properties of the finite element scheme and error estimates are proved. They show that appropriate mesh grading yields convergence rates as known for the classical FEM in presence of regular solutions. Finally, a numerical example illustrates the approach and the theoretical results. Received July 5, 2001; revised February 5, 2002 Published online April 25, 2002