Bedřich Sousedík

Bedřich Sousedík, Jakub Šístek, Jan Mandel

We combine the adaptive and multilevel approaches to the BDDC and formulate a method which allows an adaptive selection of constraints on each decomposition level. We also present a strategy for the solution of local eigenvalue problems in the adaptive algorithm using the LOBPCG method with a preconditioner based on standard components of the BDDC. The effectiveness of the method is illustrated on several engineering problems. It appears that the Adaptive-Multilevel BDDC algorithm is able to effectively detect troublesome parts on each decomposition level and improve convergence of the method. The developed open-source parallel implementation shows a good scalability as well as applicability to very large problems and core counts.

Jan Mandel, Bedřich Sousedík

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 on 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.

Jan Mandel, Bedřich Sousedík, Clark R. Dohrmann

BDDC method is the most advanced method from the Balancing family of iterative substructuring methods for the solution of large systems of linear algebraic equations arising from discretization of elliptic boundary value problems. In the case of many substructures, solving the coarse problem exactly becomes a bottleneck. Since the coarse problem in BDDC has the same structure as the original problem, it is straightforward to apply the BDDC method recursively to solve the coarse problem only approximately. In this paper, we formulate a new family of abstract Multispace BDDC methods and give condition number bounds from the abstract additive Schwarz preconditioning theory. The Multilevel BDDC is then treated as a special case of the Multispace BDDC and abstract multilevel condition number bounds are given. The abstract bounds yield polylogarithmic condition number bounds for an arbitrary fixed number of levels and scalar elliptic problems discretized by finite elements in two and three spatial dimensions. Numerical experiments confirm the theory.

Jakub Šístek, Bedřich Sousedík, Pavel Burda et al.

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.

Bedřich Sousedík, Roger G. Ghanem, Eric T. Phipps

Use of the stochastic Galerkin finite element methods leads to large systems of linear equations obtained by the discretization of tensor product solution spaces along their spatial and stochastic dimensions. These systems are typically solved iteratively by a Krylov subspace method. We propose a preconditioner which takes an advantage of the recursive hierarchy in the structure of the global matrices. In particular, the matrices posses a recursive hierarchical two-by-two structure, with one of the submatrices block diagonal. Each one of the diagonal blocks in this submatrix is closely related to the deterministic mean-value problem, and the action of its inverse is in the implementation approximated by inner loops of Krylov iterations. Thus our hierarchical Schur complement preconditioner combines, on each level in the approximation of the hierarchical structure of the global matrix, the idea of Schur complement with loops for a number of mutually independent inner Krylov iterations, and several matrix-vector multiplications for the off-diagonal blocks. Neither the global matrix, nor the matrix of the preconditioner need to be formed explicitly. The ingredients include only the number of stiffness matrices from the truncated Karhunen-Loève expansion and a good preconditioned for the mean-value deterministic problem. We provide a condition number bound for a model elliptic problem and the performance of the method is illustrated by numerical experiments.

Bedřich Sousedík, Jan Mandel

After a short historical review, we present four popular substructuring methods: FETI-1, BDD, FETI-DP, BDDC, and derive the primal versions to the two FETI methods, called P-FETI-1 and P-FETI-DP, as proposed by Fragakis and Papadrakakis. The formulation of the BDDC method shows that it is the same as P-FETI-DP and the same as a preconditioner introduced by Cros. We prove the equality of eigenvalues of a particular case of the FETI-1 method and of the BDD method by applying a recent abstract result by Fragakis.

Jakub Šístek, Jan Mandel, Bedřich Sousedík et al.

In application of the Balancing Domain Decomposition by Constraints (BDDC) to a case with many substructures, solving the coarse problem exactly becomes the bottleneck which spoils scalability of the solver. However, it is straightforward for BDDC to substitute the exact solution of the coarse problem by another step of BDDC method with subdomains playing the role of elements. In this way, the algorithm of three-level BDDC method is obtained. If this approach is applied recursively, multilevel BDDC method is derived. We present a detailed description of a recently developed parallel implementation of this algorithm. The implementation is applied to an engineering problem of linear elasticity and a benchmark problem of Stokes flow in a cavity. Results by the multilevel approach are compared to those by the standard (two-level) BDDC method.

Bedřich Sousedík, Howard C. Elman

We study the steady-state Navier-Stokes equations in the context of stochastic finite element discretizations. Specifically, we assume that the viscosity is a random field given in the form of a generalized polynomial chaos expansion. For the resulting stochastic problem, we formulate the model and linearization schemes using Picard and Newton iterations in the framework of the stochastic Galerkin method, and we explore properties of the resulting stochastic solutions. We also propose a preconditioner for solving the linear systems of equations arising at each step of the stochastic (Galerkin) nonlinear iteration and demonstrate its effectiveness for solving a set of benchmark problems.

Kookjin Lee, Howard C. Elman, Bedřich Sousedík

We study an iterative low-rank approximation method for the solution of the steady-state stochastic Navier--Stokes equations with uncertain viscosity. The method is based on linearization schemes using Picard and Newton iterations and stochastic finite element discretizations of the linearized problems. For computing the low-rank approximate solution, we adapt the nonlinear iterations to an inexact and low-rank variant, where the solution of the linear system at each nonlinear step is approximated by a quantity of low rank. This is achieved by using a tensor variant of the GMRES method as a solver for the linear systems. We explore the inexact low-rank nonlinear iteration with a set of benchmark problems, using a model of flow over an obstacle, under various configurations characterizing the statistical features of the uncertain viscosity, and we demonstrate its effectiveness by extensive numerical experiments.

Bedřich Sousedík, Howard C. Elman

We study random eigenvalue problems in the context of spectral stochastic finite elements. In particular, given a parameter-dependent, symmetric positive-definite matrix operator, we explore the performance of algorithms for computing its eigenvalues and eigenvectors represented using polynomial chaos expansions. We formulate a version of stochastic inverse subspace iteration, which is based on the stochastic Galerkin finite element method, and we compare its accuracy with that of Monte Carlo and stochastic collocation methods. The coefficients of the eigenvalue expansions are computed from a stochastic Rayleigh quotient. Our approach allows the computation of interior eigenvalues by deflation methods, and we can also compute the coefficients of multiple eigenvectors using a stochastic variant of the modified Gram-Schmidt process. The effectiveness of the methods is illustrated by numerical experiments on benchmark problems arising from vibration analysis.

Kevin Williamson, Pavel Burda, Bedřich Sousedík

The Stokes-Brinkman equations model flow in heterogeneous porous media by combining the Stokes and Darcy models of flow into a single system of equations. With suitable parameters, the equations can model either flow without detailed knowledge of the interface between the two regions. Thus, the Stokes-Brinkman equations provide an alternative to coupled Darcy-Stokes models. After a brief review of the Stokes-Brinkman problem and its discretization using Taylor-Hood finite elements, we present a residual-based a posteriori error estimate and use it to drive an adaptive mesh refinement process. We compare several strategies for the mesh refinement, and demonstrate its effectiveness by numerical experiments in both 2D and 3D.

Bedřich Sousedík

We propose a Nested BDDC for a class of saddle-point problems. The method solves for both flux and pressure variables. The fluxes are resolved in three-steps: the coarse solve is followed by subdomain solves, and last we look for a divergence-free flux correction and pressure variables using conjugate gradients with a Multilevel BDDC preconditioner. Because the coarse solve in the first step has the same structure as the original problem, we can use this procedure recursively and solve (a hierarchy of) coarse problems only approximately, utilizing the coarse problems known from the BDDC. The resulting algorithm thus first performs several upscaling steps, and then solves a hierarchy of problems that have the same structure but increase in size while sweeping down the levels, using the same components in the first and in the third step on each level, and also reusing the components from the higher levels. Because the coarsening can be quite aggressive, the number of levels can be kept small and the additional computational cost is significantly reduced due to the reuse of the components. We also provide the condition number bound and numerical experiments confirming the theory.

Kookjin Lee, Bedřich Sousedík

We study two inexact methods for solutions of random eigenvalue problems in the context of spectral stochastic finite elements. In particular, given a parameter-dependent, symmetric matrix operator, the methods solve for eigenvalues and eigenvectors represented using polynomial chaos expansions. Both methods are based on the stochastic Galerkin formulation of the eigenvalue problem and they exploit its Kronecker-product structure. The first method is an inexact variant of the stochastic inverse subspace iteration [B. Soused\'ık, H. C. Elman, SIAM/ASA Journal on Uncertainty Quantification 4(1), pp. 163--189, 2016]. The second method is based on an inexact variant of Newton iteration. In both cases, the problems are formulated so that the associated stochastic Galerkin matrices are symmetric, and the corresponding linear problems are solved using preconditioned Krylov subspace methods with several novel hierarchical preconditioners. The accuracy of the methods is compared with that of Monte Carlo and stochastic collocation, and the effectiveness of the methods is illustrated by numerical experiments.

Jakub Šístek, Jan Březina, Bedřich Sousedík

We extend the Balancing Domain Decomposition by Constraints (BDDC) method to flows in porous media discretised by mixed-hybrid finite elements with combined mesh dimensions. Such discretisations appear when major geological fractures are modelled by 1D or 2D elements inside three-dimensional domains. In this set-up, the global problem as well as the substructure problems have a symmetric saddle-point structure, containing a `penalty' block due to the combination of meshes. We show that the problem can be reduced by means of iterative substructuring to an interface problem, which is symmetric and positive definite. The interface problem can thus be solved by conjugate gradients with the BDDC method as a preconditioner. A parallel implementation of this algorithm is incorporated into an existing software package for subsurface flow simulations. We study the performance of the iterative solver on several academic and real-world problems. Numerical experiments illustrate its efficiency and scalability.

Jan Mandel, Bedřich Sousedík, Jakub Šístek

The adaptive BDDC method is extended to the selection of face constraints in three dimensions. A new implementation of the BDDC method is presented based on a global formulation without an explicit coarse problem, with massive parallelism provided by a multifrontal solver. Constraints are implemented by a projection and sparsity of the projected operator is preserved by a generalized change of variables. The effectiveness of the method is illustrated on several engineering problems.

Jan Mandel, Bedřich Sousedík

The objective of this paper is to explain the principles of the design of a coarse space in a simplified way and by pictures. The focus is on ideas rather than on a more historically complete presentation. Also, space limitation does not allow even to mention many important methods and papers that should be rightfully included.

Bedřich Sousedík, Jan Mandel

We combine the advantages of the adaptive and multilevel approaches, proposed previously by the authors, to propose a new method that preserves both, parallel scalability with increasing number of subdomains and excellent convergence properties. Performance of the method is illustrated on a two-dimensional problem of linear elasticity.