Symmetric-triangular decomposition and its applications part II: Preconditioners for indefinite systems

As an application of the symmetric-triangular (ST) decomposition given by Golub and Yuan (2001) and Strang (2003), three block ST preconditioners are discussed here for saddle point problems. All three preconditioners transform saddle point problems into a symmetric and positive definite system. The condition number of the three symmetric and positive definite systems are estimated. Therefore, numerical methods for symmetric and positive definite systems can be applied to solve saddle point problems indirectly. A numerical example for the symmetric indefinite system from the finite element approximation to the Stokes equation is given. Finally, some comments are given as well. AMS subject classification (2000) 65F10     

Constraint preconditioning for linear systems in elasticity

The mixed variational formulation of elastic deformation of a material body leads to a constraint minimisation (or saddle‐point) problem. Using the PEERS finite element space to discretise the problem one gets an indefinite system of linear equations. To solve this system, preconditioners with similar saddle‐point patterns will be applied. The results of numerical tests with this preconditioning strategy show its efficiency for linear systems with up to more than half a million unknowns.     

A multilevel decoupled method for a mixed Stokes/Darcy model

This paper studies decoupled numerical methods for a mixed Stokes/Darcy model for coupling fluid and porous media flows. A two-level algorithm is proposed and analyzed in Mu and Xu (2007) [10]. We generalize the two-level algorithm to a multilevel algorithm in this paper and present numerical analysis on the error estimates for the multilevel algorithm. The multilevel algorithm solves the mixed Stokes/Darcy system by applying efficient legacy code for single model solvers to solve two decoupled Stokes and Darcy subproblems on all the subsequently refined meshes, except for a much smaller global problem only on a very coarse initial mesh. Numerical experiments are conducted for both the two-level and multilevel algorithms to illustrate their effectiveness and efficiency, and validate the related theoretical analysis.     

A class of generalized shift-splitting preconditioners for nonsymmetric saddle point problems

In this paper, a class of generalized shift-splitting preconditioners with two shift parameters are implemented for nonsymmetric saddle point problems with nonsymmetric positive definite (1, 1) block. The generalized shift-splitting (GSS) preconditioner is induced by a generalized shift-splitting of the nonsymmetric saddle point matrix, resulting in an unconditional convergent fixed-point iteration. By removing the shift parameter in the (1, 1) block of the GSS preconditioner, a deteriorated shift-splitting (DSS) preconditioner is presented. Some useful properties of the DSS preconditioned saddle point matrix are studied. Finally, numerical experiments of a model Navier–Stokes problem are presented to show the effectiveness of the proposed preconditioners.     

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)     

On parameterized block triangular preconditioners for generalized saddle point problems

In this paper, we discuss two classes of parameterized block triangular preconditioners for the generalized saddle point problems. These preconditioners generalize the common block diagonal and triangular preconditioners. We will give distributions of the eigenvalues of the preconditioned matrix and provide estimates for the interval containing the real eigenvalues. Numerical experiments of a model Stokes problem are presented.     

Shift-splitting preconditioners for a class of block three-by-three saddle point problems

In this paper, shift-splitting preconditioners are studied for a special class of block three-by-three saddle point problems, which arise from many practical problems and are different from the traditional saddle point problems. It is proved that the block three-by-three saddle point matrix is positive stable and the corresponding shift-splitting stationary iteration method is unconditionally convergent, which leads to a nice clustering property of the eigenvalues of the shift-splitting preconditioned matrix. Numerical results show that the proposed shift-splitting preconditioners outperform much better than some existing block diagonal preconditioners studied recently.     

广义鞍点问题的块三角预条件子

本文对Golub和Yuan(2002)中给出的ST分解推广到广义鞍点问题上,给出了三种块预条件子,并重点分析了其中两种预条件子应用到广义鞍点问题上所得到的对称正定阵,得出了其一般的性质并重点研究了预处理矩阵条件数的上界,最后给出了数值算例.     

Partitioned time stepping schemes for the non-stationary dual-fracture-matrix fluid flow model

This paper presents the coupled, and decoupled schemes for the naturally fractured reservoir consists of the triple-porosity medium. More specifically, the triple-porosity medium contains three contagious porous medium with more permeable macrofractures, less permeable microfractures, and matrix region which is often known as dual-fracture-matrix fluid flow model. Since the matrix has fluid communication with less permeable microfractures, and macrofratures are fed by the microfractures only, the global domain is divided into two subdomains by considering the traditional dual-porosity region and more permeable macrofractures region respectively. The flow and mass exchange between less permeable microfractures and more permeable macrofractures are modeled by two-fluid communication interface conditions while no-communication interface condition is imposed on between matrix and macrofractures region. The weak formulation and the well-posedness of the dual-fracture-matrix model are derived. Furthermore, coupled, implicit-explicit and data-passing partitioned schemes are proposed. The stability and the optimal convergence analysis are derived for both decoupled schemes. Five numerical examples are presented to illustrate the accuracy of the numerical methods and the applicability of the dual-fracture-matrix fluid flow model. Moreover, the parameter sensitivity analysis is performed in the fourth numerical example.     

Optimal error estimates of a decoupled scheme based on two-grid finite element for mixed Stokes–Darcy model

Although the numerical results suggest the optimal convergence order of the two-grid finite element decoupled scheme for mixed Stokes–Darcy model with Beavers–Joseph–Saffman interface condition in literatures, the numerical analysis only gets the optimal error order for porous media flow and a non-optimal error order that is half order lower than the optimal one in fluid flow. The purpose of this paper is to fill in the gap between the numerical results and the theoretical analysis.     

Evaluation of ST preconditioners for saddle point problems

The general block ST decomposition of the saddle point problem is used as a preconditioner to transform the saddle point problem into an equivalent symmetric and positive definite system. Such a decomposition is called a block ST preconditioner. Two general block ST preconditioners are proposed for saddle point problems with symmetric and positive definite (1,1)-block. Some estimations of the condition number of the preconditioned system are given. The same study is done for singular (1,1)-block.     

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.     

Uniform preconditioners for the time dependent Stokes problem

Summary. Implicit time stepping procedures for the time dependent Stokes problem lead to stationary singular perturbation problems at each time step. These singular perturbation problems are systems of saddle point type, which formally approach a mixed formulation of the Poisson equation as the time step tends to zero. Preconditioners for discrete analogous of these systems are discussed. The preconditioners uses standard positive definite elliptic preconditioners as building blocks and lead to condition numbers which are bounded uniformly with respect to the time step and the spatial discretization. The construction of the discrete preconditioners is related to the mapping properties of the corresponding continuous system. Mathematics Subject Classification: 65M55, 65 Revised version received September 18, 2003 An erratum to this article is availabel at .     

An improved lower bound on a positive stable block triangular preconditioner for saddle point problems

In this paper, a new lower bound on a positive stable block triangular preconditioner for saddle point problems is derived; it is superior to the corresponding result obtained by Cao [Z.-H. Cao, Positive stable block triangular preconditioners for symmetric saddle point problems, Appl. Numer. Math. 57 (2007) 899–910]. A numerical example is reported to confirm the presented result.     

Spectral Analysis for HSS Preconditioners

In this paper,we are interested in HSS preconditioners for saddle point lin- ear systems with a nonzero(2,2)-th block.We study an approximation of the spectra of HSS preconditioned matrices and use these results to illustrate and explain the spectra obtained from numerical examples,where the previous spectral analysis of HSS precon- ditioned matrices does not cover.     

Combination preconditioning of saddle point systems for positive definiteness

Amongst recent contributions to preconditioning methods for saddle point systems, standard iterative methods in nonstandard inner products have been usefully employed. Krzy?anowski (Numerical Linear Algebra with Applications 2011; 18 :123–140) identified a two‐parameter family of preconditioners in this context and Stoll and Wathen (SIAM Journal on Matrix Analysis and Applications 2008; 30 :582–608) introduced combination preconditioning, where two preconditioners, self‐adjoint with respect to different inner products, can lead to further preconditioners and associated bilinear forms or inner products. Preconditioners that render the preconditioned saddle point matrix nonsymmetric but self‐adjoint with respect to a nonstandard inner product always allow a MINRES‐type method (‐PMINRES) to be applied in the relevant inner product. If the preconditioned matrix is also positive definite with respect to the inner product, a more efficient CG‐like method (‐PCG) can be reliably used. We establish eigenvalue expressions for Krzy?anowski preconditioners and show that for a specific choice of parameters, although the Krzy?anowski preconditioned saddle point matrix is self‐adjoint with respect to an inner product, it is never positive definite. We provide explicit expressions for the combination of certain preconditioners and prove the rather counterintuitive result that the combination of two specific preconditioners for which only ‐PMINRES can be reliably used leads to a preconditioner for which, for certain parameter choices, ‐PCG is reliably applicable. That is, combining two indefinite preconditioners can lead to a positive definite preconditioner. This combination preconditioner outperforms either of the two preconditioners from which it is formed for a number of test problems. Copyright © 2012 John Wiley & Sons, Ltd.     

Numerical Simulation of Two-Phase Flow through Heterogeneous Porous Media

A mixed finite element method is combined to finite volume schemes on structured and unstructured grids for the approximation of the solution of incompressible flow in heterogeneous porous media. A series of numerical examples demonstrates the effectiveness of the methodology for a coupled system which includes an elliptic equation and a nonlinear degenerate diffusion–convection equation arising in modeling of flow and transport in porous media.     

Optimization of the parameterized Uzawa preconditioners for saddle point matrices

The parameterized Uzawa preconditioners for saddle point problems are studied in this paper. The eigenvalues of the preconditioned matrix are located in (0, 2) by choosing the suitable parameters. Furthermore, we give two strategies to optimize the rate of convergence by finding the suitable values of parameters. Numerical computations show that the parameterized Uzawa preconditioners can lead to practical and effective preconditioned GMRES methods for solving the saddle point problems.     

An efficient numerical method for preconditioned saddle point problems

In this paper, we consider the solution of linear systems of saddle point type by a preconditioned numerical method. We first transform the original linear system into two sub-systems with small size by a preconditioning strategy, then employ the conjugate gradient (CG) method to solve the linear system with a SPD coefficient matrix, and a splitting iteration method to solve the other sub-system, respectively. Numerical experiments show that the new method can achieve faster convergence than several effective preconditioners published in the recent literature in terms of total runtime and iteration steps.     

Optimal error estimates of a decoupled scheme based on two-grid finite element for mixed Navier-Stokes/Darcy Model

Although the two-grid finite element decoupled scheme for mixed Navier-Stokes/Darcy model in literatures has given the numerical results of optimal convergence order, the theoretical analysis only obtain the optimal error order for the porous media flow and a non-optimal error order for the fluid flow. In this article, we give a more rigorous of the error analysis for the fluid flow and obtain the optimal error estimates of the velocity and the pressure.