Analysis of some projection method based preconditioners for models of incompressible flow

In this paper, several projection method based preconditioners for various incompressible flow models are studied. In the derivations of these projection method based preconditioners, we use three different types of the approximations of the inverse of the Schur complement, i.e., the exact inverse, the Cahouet–Chabard type approximation and the BFBt type approximation. We illuminate the connections and the distinctions between these projection method based preconditioners and those related preconditioners. For the preconditioners using the Cahouet–Chabard type approximation, we show that the eigenvalues of the preconditioned systems have uniform bounds independent of the parameters and most of them are equal to 1. The analysis is based on a detailed discussion of the commutator difference operator. Moreover, these results demonstrate the stability of the staggered grid discretization and reveal the effects of the boundary treatment. To further illustrate the effectiveness of these projection method based preconditioners, numerical experiments are given to compare their performances with those of the related preconditioners. Generalizations of the projection method based preconditioners to other saddle point problems are also discussed.     

Block triangular preconditioners for linearization schemes of the Rayleigh–Bénard convection problem

In this paper, we compare two block triangular preconditioners for different linearizations of the Rayleigh–Bénard convection problem discretized with finite element methods. The two preconditioners differ in the nested or nonnested use of a certain approximation of the Schur complement associated to the Navier–Stokes block. First, bounds on the generalized eigenvalues are obtained for the preconditioned systems linearized with both Picard and Newton methods. Then, the performance of the proposed preconditioners is studied in terms of computational time. This investigation reveals some inconsistencies in the literature that are hereby discussed. We observe that the nonnested preconditioner works best both for the Picard and for the Newton cases. Therefore, we further investigate its performance by extending its application to a mixed Picard–Newton scheme. Numerical results of two‐ and three‐dimensional cases show that the convergence is robust with respect to the mesh size. We also give a characterization of the performance of the various preconditioned linearization schemes in terms of the Rayleigh number.     

Local preconditioners for two‐level non‐overlapping domain decomposition methods

We consider additive two‐level preconditioners, with a local and a global component, for the Schur complement system arising in non‐overlapping domain decomposition methods. We propose two new parallelizable local preconditioners. The first one is a computationally cheap but numerically relevant alternative to the classical block Jacobi preconditioner. The second one exploits all the information from the local Schur complement matrices and demonstrates an attractive numerical behaviour on heterogeneous and anisotropic problems. We also propose two implementations based on approximate Schur complement matrices that are cheaper alternatives to construct the given preconditioners but that preserve their good numerical behaviour. Through extensive computational experiments we study the numerical scalability and the robustness of the proposed preconditioners and compare their numerical performance with well‐known robust preconditioners such as BPS and the balancing Neumann–Neumann method. Finally, we describe a parallel implementation on distributed memory computers of some of the proposed techniques and report parallel performances. Copyright © 2001 John Wiley & Sons, Ltd.     

A block preconditioning technique for the streamfunction‐vorticity formulation of the Navier‐Stokes equations

Iterative methods of Krylov‐subspace type can be very effective solvers for matrix systems resulting from partial differential equations if appropriate preconditioning is employed. We describe and test block preconditioners based on a Schur complement approximation which uses a multigrid method for finite element approximations of the linearized incompressible Navier‐Stokes equations in streamfunction and vorticity formulation. By using a Picard iteration, we use this technology to solve fully nonlinear Navier‐Stokes problems. The solvers which result scale very well with problem parameters. © 2011 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2011     

Block and joint ℋ︁-matrix preconditioners for the Oseen equations

For saddle point problems in fluid dynamics, many preconditioners in the literature exploit the block structure of the problem to construct block diagonal or block triangular preconditioners. The performance of such preconditioners depends on whether fast, approximate solvers for the linear systems on the block diagonal as well as for the Schur complement are available. We will construct these efficient preconditioners using hierarchical matrix techniques in which fully populated matrices are approximated by blockwise low rank approximations. We will compare such block preconditioners with those obtained through a completely different approach where the given block structure is not used but a domain-decomposition based ℋ︁-LU factorization is constructed for the complete system matrix. Preconditioners resulting from these two approaches will be discussed and compared through numerical results. (© 2006 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Preconditioning trace coupled 3d‐1d systems using fractional Laplacian

Multiscale or multiphysics problems often involve coupling of partial differential equations posed on domains of different dimensionality. In this work, we consider a simplified model problem of a 3d‐1d coupling and the main objective is to construct algorithms that may utilize standard multilevel algorithms for the 3d domain, which has the dominating computational complexity. Preconditioning for a system of two elliptic problems posed, respectively, in a three‐dimensional domain and an embedded one dimensional curve and coupled by the trace constraint is discussed. Investigating numerically the properties of the well‐defined discrete trace operator, it is found that negative fractional Sobolev norms are suitable preconditioners for the Schur complement of the system. The norms are employed to construct a robust block diagonal preconditioner for the coupled problem.     

Continuous preconditioners for the mixed Poisson problem

In this note, we show how to apply preconditioners designed for piecewise linear finite element discretizations of the Poisson problem as preconditioners for the mixed problem. Our preconditioner can be applied both to the original and to the reduced Schur complement problem. Combined with a suitable iterative method, the number of iterations required to solve the preconditioned system will have the same dependency on the mesh size as for the preconditioner applied to the Poisson problem. The presented theory is demonstrated by numerical examples.     

Fourier analysis of a robust multigrid method for convection-diffusion equations

Summary. We consider a two-grid method for solving 2D convection-diffusion problems. The coarse grid correction is based on approximation of the Schur complement. As a preconditioner of the Schur complement we use the exact Schur complement of modified fine grid equations. We assume constant coefficients and periodic boundary conditions and apply Fourier analysis. We prove an upper bound for the spectral radius of the two-grid iteration matrix that is smaller than one and independent of the mesh size, the convection/diffusion ratio and the flow direction; i.e. we have a (strong) robustness result. Numerical results illustrating the robustness of the corresponding multigrid -cycle are given. Received October 14, 1994     

Unified analysis of preconditioning methods for saddle point matrices

Short and unified proofs of spectral properties of major preconditioners for saddle point problems are presented. The need to sufficiently accurately construct approximations of the pivot block and Schur complement matrices to obtain real eigenvalues or eigenvalues with positive real parts and non‐dominating imaginary parts are pointed out. The use of augmented Lagrangian methods for more ill‐conditioned problems are discussed. Copyright © 2014 John Wiley & Sons, Ltd.     

A note on spectrum analysis of augmentation block Schur complement preconditioners

In this note, as a generalization of the preconditioner presented by Greif et al. (SIAM J Matrix Anal Appl 27:779–792, 2006), we consider a set of augmentation block Schur complement preconditioners for solving saddle point systems whose coefficient matrices have singular (1,1) blocks. The spectral properties of the preconditioned matrices are analyzed and an optimal preconditioner is derived.     

Effective Chorin–Temam algebraic splitting schemes for the steady Navier–stokes equations

This paper continues some recent work on the numerical solution of the steady incompressible Navier–Stokes equations. We present a new method, similar to the one presented in Rebholz et al., but with superior convergence and numerical properties. The method is efficient as it allows one to solve the same symmetric positive‐definite system for the pressure at each iteration, allowing for the simple preconditioning and the reuse of preconditioners. We also demonstrate how one can replace the Schur complement system with a diagonal matrix inversion while maintaining accuracy and convergence, at a small fraction of the numerical cost. Convergence is analyzed for Newton and Picard‐type algorithms, as well as for the Schur complement approximation.     

A spatial domain decomposition method for parabolic optimal control problems

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

Uniform preconditioners for a parameter dependent saddle point problem with application to generalized Stokes interface equations

We consider an abstract parameter dependent saddle-point problem and present a general framework for analyzing robust Schur complement preconditioners. The abstract analysis is applied to a generalized Stokes problem, which yields robustness of the Cahouet-Chabard preconditioner. Motivated by models for two-phase incompressible flows we consider a generalized Stokes interface problem. Application of the general theory results in a new Schur complement preconditioner for this class of problems. The robustness of this preconditioner with respect to several parameters is treated. Results of numerical experiments are given that illustrate robustness properties of the preconditioner.     

Preconditioning Indefinite Systems in Interior Point Methods for Optimization

Every Newton step in an interior-point method for optimization requires a solution of a symmetric indefinite system of linear equations. Most of today's codes apply direct solution methods to perform this task. The use of logarithmic barriers in interior point methods causes unavoidable ill-conditioning of linear systems and, hence, iterative methods fail to provide sufficient accuracy unless appropriately preconditioned. Two types of preconditioners which use some form of incomplete Cholesky factorization for indefinite systems are proposed in this paper. Although they involve significantly sparser factorizations than those used in direct approaches they still capture most of the numerical properties of the preconditioned system. The spectral analysis of the preconditioned matrix is performed: for convex optimization problems all the eigenvalues of this matrix are strictly positive. Numerical results are given for a set of public domain large linearly constrained convex quadratic programming problems with sizes reaching tens of thousands of variables. The analysis of these results reveals that the solution times for such problems on a modern PC are measured in minutes when direct methods are used and drop to seconds when iterative methods with appropriate preconditioners are used.     

FSAI-based parallel Mixed Constraint Preconditioners for saddle point problems arising in geomechanics

In this paper we propose and describe a parallel implementation of a block preconditioner for the solution of saddle point linear systems arising from Finite Element (FE) discretization of 3D coupled consolidation problems. The Mixed Constraint Preconditioner developed in [L. Bergamaschi, M. Ferronato, G. Gambolati, Mixed constraint preconditioners for the solution to FE coupled consolidation equations, J. Comput. Phys., 227(23) (2008), 9885-9897] is combined with the parallel FSAI preconditioner which is used here to approximate the inverses of both the structural (1, 1) block and an appropriate Schur complement matrix. The resulting preconditioner proves effective in the acceleration of the BiCGSTAB iterative solver. Numerical results on a number of test cases of size up to 2×10⁶ unknowns and 1.2×10⁸ nonzeros show the perfect scalability of the overall code up to 256 processors.     

FSAI-based parallel Mixed Constraint Preconditioners for saddle point problems arising in geomechanics

In this paper we propose and describe a parallel implementation of a block preconditioner for the solution of saddle point linear systems arising from Finite Element (FE) discretization of 3D coupled consolidation problems. The Mixed Constraint Preconditioner developed in [L. Bergamaschi, M. Ferronato, G. Gambolati, Mixed constraint preconditioners for the solution to FE coupled consolidation equations, J. Comput. Phys., 227(23) (2008), 9885–9897] is combined with the parallel FSAI preconditioner which is used here to approximate the inverses of both the structural (1, 1) block and an appropriate Schur complement matrix. The resulting preconditioner proves effective in the acceleration of the BiCGSTAB iterative solver. Numerical results on a number of test cases of size up to 2×10⁶ unknowns and 1.2×10⁸ nonzeros show the perfect scalability of the overall code up to 256 processors.     

Fast parallel solvers for symmetric boundary element domain decomposition equations

Summary. The boundary element method (BEM) is of advantage in many applications including far-field computations in magnetostatics and solid mechanics as well as accurate computations of singularities. Since the numerical approximation is essentially reduced to the boundary of the domain under consideration, the mesh generation and handling is simpler than, for example, in a finite element discretization of the domain. In this paper, we discuss fast solution techniques for the linear systems of equations obtained by the BEM (BE-equations) utilizing the non-overlapping domain decomposition (DD). We study parallel algorithms for solving large scale Galerkin BE–equations approximating linear potential problems in plane, bounded domains with piecewise homogeneous material properties. We give an elementary spectral equivalence analysis of the BEM Schur complement that provides the tool for constructing and analysing appropriate preconditioners. Finally, we present numerical results obtained on a massively parallel machine using up to 128 processors, and we sketch further applications to elasticity problems and to the coupling of the finite element method (FEM) with the boundary element method. As shown theoretically and confirmed by the numerical experiments, the methods are of algebraic complexity and of high parallel efficiency, where denotes the usual discretization parameter. Received August 28, 1996 / Revised version received March 10, 1997     

Variational theory and domain decomposition for nonlocal problems

In this article we present the first results on domain decomposition methods for nonlocal operators. We present a nonlocal variational formulation for these operators and establish the well-posedness of associated boundary value problems, proving a nonlocal Poincaré inequality. To determine the conditioning of the discretized operator, we prove a spectral equivalence which leads to a mesh size independent upper bound for the condition number of the stiffness matrix. We then introduce a nonlocal two-domain variational formulation utilizing nonlocal transmission conditions, and prove equivalence with the single-domain formulation. A nonlocal Schur complement is introduced. We establish condition number bounds for the nonlocal stiffness and Schur complement matrices. Supporting numerical experiments demonstrating the conditioning of the nonlocal one- and two-domain problems are presented.     

The condition number of the Schur complement in domain decomposition

Summary. It is shown that for elliptic boundary value problems of order 2m the condition number of the Schur complement matrix that appears in nonoverlapping domain decomposition methods is of order , where d measures the diameters of the subdomains and h is the mesh size of the triangulation. The result holds for both conforming and nonconforming finite elements. Received: January 15, 1998