Application of the parallel BDDC preconditioner to the Stokes flow

A parallel implementation of the Balancing Domain Decomposition by Constraints (BDDC) method is described. It is based on formulation of BDDC with global matrices without explicit coarse problem. The implementation is based on the MUMPS parallel solver for computing the approximate inverse used for preconditioning. It is successfully applied to several problems of Stokes flow discretized by Taylor–Hood finite elements and BDDC is shown to be a promising method also for this class of problems.     

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.     

Adaptive selection of face coarse degrees of freedom in the BDDC and the FETI-DP iterative substructuring methods

We propose a class of methods for the adaptive selection of the coarse space of the BDDC and FETI-DP iterative substructuring methods. The methods work by adding coarse degrees of freedom constructed from eigenvectors associated with intersections of selected pairs of adjacent substructures. It is assumed that the starting coarse degrees of freedom are already sufficient to prevent relative rigid body motions in any selected pair of adjacent substructures. A heuristic indicator of the the condition number is developed and a minimal number of coarse degrees of freedom is added to decrease the indicator under a given threshold. It is shown numerically on 2D elasticity problems that the indicator based on pairs of substructures with common edges predicts the actual condition number reasonably well, and that the method can select adaptively the hard part of the problem and concentrate computational work there to achieve good convergence of the iterations at a modest cost.     

BDDC preconditioning for high-order Galerkin Least-Squares methods using inexact solvers

A high-order Galerkin Least-Squares (GLS) finite element discretization is combined with a Balancing Domain Decomposition by Constraints (BDDC) preconditioner and inexact local solvers to provide an efficient solution technique for large-scale, convection-dominated problems. The algorithm is applied to the linear system arising from the discretization of the two-dimensional advection–diffusion equation and Euler equations for compressible, inviscid flow. A Robin–Robin interface condition is extended to the Euler equations using entropy-symmetrized variables. The BDDC method maintains scalability for the high-order discretization of the diffusion-dominated flows, and achieves low iteration count in the advection-dominated regime. The BDDC method based on inexact local solvers with incomplete factorization and p = 1 coarse correction maintains the performance of the exact counterpart for the wide range of the Peclet numbers considered while at significantly reduced memory and computational costs.     

BDDC and FETI-DP under minimalist assumptions

Summary The FETI-DP, BDDC and P-FETI-DP preconditioners are derived in a particulary simple abstract form. It is shown that their properties can be obtained from only a very small set of algebraic assumptions. The presentation is purely algebraic and it does not use any particular definition of method components, such as substructures and coarse degrees of freedom. It is then shown that P-FETI-DP and BDDC are in fact the same. The FETI-DP and the BDDC preconditioned operators are of the same algebraic form, and the standard condition number bound carries over to arbitrary abstract operators of this form. The equality of eigenvalues of BDDC and FETI-DP also holds in the minimalist abstract setting. The abstract framework is explained on a standard substructuring example. J. Mandel and B. Sousedík were supported by the National Science Foundation under grants CNS-0325314, CNS-0719641, and DMS-0713876. B. Sousedík was supported by the program of the Information society of the Academy of Sciences of the Czech Republic 1ET400760509 and by the Grant Agency of the Czech Republic GA CR 106/05/2731.     

Face-based selection of corners in 3D substructuring

In most recent substructuring methods, a fundamental role is played by the coarse space. For some of these methods (e.g. BDDC and FETI-DP), its definition relies on a ‘minimal’ set of coarse nodes (sometimes called corners) which assures invertibility of local subdomain problems and also of the global coarse problem. This basic set is typically enhanced by enforcing continuity of functions at some generalized degrees of freedom, such as average values on edges or faces of subdomains. We revisit existing algorithms for selection of corners. The main contribution of this paper consists of proposing a new heuristic algorithm for this purpose. Considering faces as the basic building blocks of the interface, inherent parallelism, and better robustness with respect to disconnected subdomains are among features of the new technique. The advantages of the presented algorithm in comparison to some earlier approaches are demonstrated on three engineering problems of structural analysis solved by the BDDC method.     

Additive Schwarz with aggregation-based coarsening for elliptic problems with highly variable coefficients

Summary We develop a new coefficient-explicit theory for two-level overlapping domain decomposition preconditioners with non-standard coarse spaces in iterative solvers for finite element discretisations of second-order elliptic problems. We apply the theory to the case of smoothed aggregation coarse spaces introduced by Vanek, Mandel and Brezina in the context of algebraic multigrid (AMG) and are particularly interested in the situation where the diffusion coefficient (or the permeability) α is highly variable throughout the domain. Our motivating example is Monte Carlo simulation for flow in rock with permeability modelled by log–normal random fields. By using the concept of strong connections (suitably adapted from the AMG context) we design a two-level additive Schwarz preconditioner that is robust to strong variations in α as well as to mesh refinement. We give upper bounds on the condition number of the preconditioned system which do not depend on the size of the subdomains and make explicit the interplay between the coefficient function and the coarse space basis functions. In particular, we are able to show that the condition number can be bounded independent of the ratio of the two values of α in a binary medium even when the discontinuities in the coefficient function are not resolved by the coarse mesh. Our numerical results show that the bounds with respect to the mesh parameters are sharp and that the method is indeed robust to strong variations in α. We compare the method to other preconditioners and to a sparse direct solver.      

A finite difference discretization method for elliptic problems on composite grids

In this paper we discusss a simple finite difference method for the discretization of elliptic boundary value problems on composite grids. For the model problem of the Poisson equation we prove stability of the discrete operator and bounds for the global discretization error. These bounds clearly show how the discretization error depends on the grid size of the coarse grid, on the grid size of the local fine grid and on the order of the interpolation used on the interface. Furthermore, the constants in these bounds do not depend on the quotient of coarse grid size and fine grid size. We also discuss an efficient solution method for the resulting composite grid algebraic problem.     

Lower Bounds for Eigenvalues of Elliptic Operators: By Nonconforming Finite Element Methods

The paper is to introduce a new systematic method that can produce lower bounds for eigenvalues. The main idea is to use nonconforming finite element methods. The conclusion is that if local approximation properties of nonconforming finite element spaces are better than total errors (sums of global approximation errors and consistency errors) of nonconforming finite element methods, corresponding methods will produce lower bounds for eigenvalues. More precisely, under three conditions on continuity and approximation properties of nonconforming finite element spaces we analyze abstract error estimates of approximate eigenvalues and eigenfunctions. Subsequently, we propose one more condition and prove that it is sufficient to guarantee nonconforming finite element methods to produce lower bounds for eigenvalues of symmetric elliptic operators. We show that this condition hold for most low-order nonconforming finite elements in literature. In addition, this condition provides a guidance to modify known nonconforming elements in literature and to propose new nonconforming elements. In fact, we enrich locally the Crouzeix-Raviart element such that the new element satisfies the condition; we also propose a new nonconforming element for second order elliptic operators and prove that it will yield lower bounds for eigenvalues. Finally, we prove the saturation condition for most nonconforming elements.     

BDDC by a frontal solver and the stress computation in a hip joint replacement

A parallel implementation of the Balancing Domain Decomposition based on Constraints (BDDC) method using the frontal solver is employed to solve systems of linear equations from finite element analysis, and incorporated into a standard finite element system for engineering analysis by linear elasticity. Results of computation of stress in a hip replacement are presented. The part is made of titanium and loaded by the weight of human body. The performance of BDDC with added constraints by averages and with added corners is compared.     

On the scalability of inexact balancing domain decomposition by constraints with overlapped coarse/fine corrections

In this work, we analyze the scalability of inexact two-level balancing domain decomposition by constraints (BDDC) preconditioners for Krylov subspace iterative solvers, when using a highly scalable asynchronous parallel implementation where fine and coarse correction computations are overlapped in time. This way, the coarse-grid problem can be fully overlapped by fine-grid computations (which are embarrassingly parallel) in a wide range of cases. Further, we consider inexact solvers to reduce the computational cost/complexity and memory consumption of coarse and local problems and boost the scalability of the solver. Out of our numerical experimentation, we conclude that the BDDC preconditioner is quite insensitive to inexact solvers. In particular, one cycle of algebraic multigrid (AMG) is enough to attain algorithmic scalability. Further, the clear reduction of computing time and memory requirements of inexact solvers compared to sparse direct ones makes possible to scale far beyond state-of-the-art BDDC implementations. Excellent weak scalability results have been obtained with the proposed inexact/overlapped implementation of the two-level BDDC preconditioner, up to 93,312 cores and 20 billion unknowns on JUQUEEN. Further, we have also applied the proposed setting to unstructured meshes and partitions for the pressure Poisson solver in the backward-facing step benchmark domain.     

Preconditioning of the coarse problem in the method of balanced domain decomposition by constraints

The method of balanced domain decomposition by constraints is an iterative algorithm for numerical solution of partial differential equations which exploits a non-overlapping partition of a domain. As an essential part of each step, restricted problems are solved on every subdomain and a certain coarse grid solution is found. In this paper we present a new strategy of preconditioning of the coarse problem. This is based on the algebraic multilevel preconditioning technique. We present numerical estimates of constants defining the condition numbers of the preconditioned coarse problems for several two- and three-dimensional elliptic equations.     

A Class of Domain Decomposition Preconditioners for <Emphasis Type="Italic">hp</Emphasis>-Discontinuous Galerkin Finite Element Methods

In this article we address the question of efficiently solving the algebraic linear system of equations arising from the discretization of a symmetric, elliptic boundary value problem using hp-version discontinuous Galerkin finite element methods. In particular, we introduce a class of domain decomposition preconditioners based on the Schwarz framework, and prove bounds on the condition number of the resulting iteration operators. Numerical results confirming the theoretical estimates are also presented.     

An overlapping Schwarz method for virtual element discretizations in two dimensions

A new coarse space for domain decomposition methods is presented for nodal elliptic problems in two dimensions. The coarse space is derived from the novel virtual element methods and therefore can accommodate quite irregular polygonal subdomains. It has the advantage with respect to previous studies that no discrete harmonic extensions are required. The virtual element method allows us to handle polygonal meshes and the algorithm can then be used as a preconditioner for linear systems that arise from a discretization with such triangulations. A bound is obtained for the condition number of the preconditioned system by using a two-level overlapping Schwarz algorithm, but the coarse space can also be used for different substructuring methods. This bound is independent of jumps in the coefficient across the interface between the subdomains. Numerical experiments that verify the result are shown, including some with triangular, square, hexagonal and irregular elements and with irregular subdomains obtained by a mesh partitioner.     

Efficient domain decomposition methods for elliptic problems arising from flows in heterogeneous porous media

In this paper we study domain decomposition methods for solving some elliptic problem arising from flows in heterogeneous porous media. Due to the multiple scale nature of the elliptic coefficients arising from the heterogeneous formations, the construction of efficient domain decomposition methods for these problems requires a coarse solver which is adaptive to the fine scale features, [4]. We propose the use of a multiscale coarse solver based on a finite volume – finite element formulation. The resulting domain decomposition methods seem to induce a convergence rate nearly independent of the aspect ratio of the extreme permeability values within the substructures. A rigorous convergence analysis based on the Schwarz framework is carried out, and we demonstrate the efficiency and robustness of the preconditioner through numerical experiments which include problems with multiple scale coefficients, as well as problems with continuous scales. Communicated by: G. Wittum     

A Parallel Subgrid Stabilized Finite Element Method Based on Two-Grid Discretization for Simulation of 2D/3D Steady Incompressible Flows

Based on domain decomposition and two-grid discretization, a parallel subgrid stabilized finite element method for simulation of 2D/3D steady convection dominated incompressible flows is proposed and analyzed. In this method, a subgrid stabilized nonlinear Navier–Stokes problem is first solved on a coarse grid where the stabilization term is based on an elliptic projection defined on the same coarse grid, and then corrections are calculated in overlapped fine grid subdomains by solving a linearized problem. By the technical tool of local a priori estimate for finite element solution, error bounds of the approximate solution are estimated. Algorithmic parameter scalings of the method are derived. Numerical results are also given to demonstrate the effectiveness of the method.     

Certified Reduced Basis Methods for Parametrized Elliptic Optimal Control Problems with Distributed Controls

In this paper, we consider the efficient and reliable solution of distributed optimal control problems governed by parametrized elliptic partial differential equations. The reduced basis method is used as a low-dimensional surrogate model to solve the optimal control problem. To this end, we introduce reduced basis spaces not only for the state and adjoint variable but also for the distributed control variable. We also propose two different error estimation procedures that provide rigorous bounds for the error in the optimal control and the associated cost functional. The reduced basis optimal control problem and associated a posteriori error bounds can be efficiently evaluated in an offline–online computational procedure, thus making our approach relevant in the many-query or real-time context. We compare our bounds with a previously proposed bound based on the Banach–Ne?as–Babu?ka theory and present numerical results for two model problems: a Graetz flow problem and a heat transfer problem. Finally, we also apply and test the performance of our newly proposed bound on a hyperthermia treatment planning problem.     

Fast Computation of Optimal Contact Forces

We consider the problem of computing the smallest contact forces, with point-contact friction model, that can hold an object in equilibrium against a known external applied force and torque. It is known that the force optimization problem (FOP) can be formulated as a semidefinite programming problem (SDP) or a second-order cone problem (SOCP), and thus, can be solved using several standard algorithms for these problem classes. In this paper, we describe a custom interior-point algorithm for solving the FOP that exploits the specific structure of the problem, and is much faster than these standard methods. Our method has a complexity that is linear in the number of contact forces, whereas methods based on generic SDP or SOCP algorithms have complexity that is cubic in the number of forces. Our method is also much faster for smaller problems. We derive a compact dual problem for the FOP, which allows us to rapidly compute lower bounds on the minimum contact force and certify the infeasibility of a FOP. We use this dual problem to terminate our optimization method with a guaranteed accuracy. Finally, we consider the problem of solving a family of FOPs that are related. This occurs, for example, in determining whether force closure occurs, in analyzing the worst case contact force required over a set of external forces and torques, and in the problem of choosing contact points on an object so as to minimize the required contact force. Using dual bounds, and a warm-start version of our FOP method, we show how such families of FOPs can be solved very efficiently.     

A unified framework for two-grid methods for a class of nonlinear problems

In this article, we present a unified error analysis of two-grid methods for a class of nonlinear problems. We first study the two-grid method of Xu by recasting the methodology in the abstract framework of Brezzi, Rappaz, and Raviart (BRR) for approximation of branches of nonsingular solutions and derive a priori error estimates. Our convergence results indicate that the correct scaling between fine and coarse meshes is given by \(h={{\mathcal {O}}}(H^2)\) for all the nonlinear problems which can be written in and applied to the BRR framework. Next, a correction step can be added to the two-grid algorithm, which allows the choice \(h={\mathcal O}(H^3)\). On the other hand, the particular BRR framework with duality pairing, if it is applied to a semilinear problem, allows a higher order relation \(h={{\mathcal {O}}}(H^4)\). Furthermore, even the choice \(h={{\mathcal {O}}}(H^5)\) is possible with the correction step either on fine mesh or coarse mesh. In addition, elliptic problems with gradient nonlinearities and the Naiver–Stokes equations are considered to illustrate our unified theory. Finally, numerical experiments are conducted to confirm our theoretical findings. Numerical results indicate that the correction step used as a simple postprocessing enhances the solution accuracy, particularly for problems with layers.     

Multilevel Schwarz methods for elliptic partial differential equations

We investigate multilevel Schwarz domain decomposition preconditioners, to efficiently solve linear systems arising from numerical discretizations of elliptic partial differential equations by the finite element method. In our analysis we deal with unstructured mesh partitions and with subdomain boundaries resulting from using the mesh partitioner. We start from two-level preconditioners with either aggregative or interpolative coarse level components, then we focus on a strategy to increase the number of levels. For all preconditioners, we consider the additive residual update and its multiplicative variants within and between levels. Moreover, we compare the preconditioners behaviour, regarding scalability and rate of convergence. Numerical results are provided for elliptic boundary value problems, including a convection–diffusion problem when suitable stabilization becomes necessary.