On preconditioned Uzawa methods and SOR methods for saddle-point problems

This paper studies convergence analysis of a preconditioned inexact Uzawa method for nondifferentiable saddle-point problems. The SOR-Newton method and the SOR-BFGS method are special cases of this method. We relax the Bramble-Pasciak-Vassilev condition on preconditioners for convergence of the inexact Uzawa method for linear saddle-point problems. The relaxed condition is used to determine the relaxation parameters in the SOR-Newton method and the SOR-BFGS method. Furthermore, we study global convergence of the multistep inexact Uzawa method for nondifferentiable saddle-point problems.     

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.     

Superlinearly convergent PCG algorithms for some nonsymmetric elliptic systems

A preconditioned conjugate gradient method is applied to finite element discretizations of some nonsymmetric elliptic systems. Mesh independent superlinear convergence is proved, which is an extension of a similar earlier result from a single equation to systems. The proposed preconditioning method involves decoupled preconditioners, which yields small and parallelizable auxiliary problems.     

Two-level Additive Schwarz Preconditioners for Nonconforming Finite Element Methods

Two-level additive Schwarz preconditioners are developed for the nonconforming P1 finite element approximation of scalar second-order symmetric positive definite elliptic boundary value problems, the Morley finite element approximation of the biharmonic equation, and the divergence-free nonconforming P1 finite element approximation of the stationary Stokes equations. The condition numbers of the preconditioned systems are shown to be bounded independent of mesh sizes and the number of subdomains in the case of generous overlap.

     

Multilevel preconditioners for a quadrature Galerkin solution of a biharmonic problem

Efficient multilevel preconditioners are developed and analyzed for the quadrature finite element Galerkin approximation of the biharmonic Dirichlet problem. The quadrature scheme is formulated using the Bogner–Fox–Schmit rectangular element and the product two‐point Gaussian quadrature. The proposed additive and multiplicative preconditioners are uniformly spectrally equivalent to the operator of the quadrature scheme. The preconditioners are implemented by optimal algorithms, and they are used to accelerate convergence of the preconditioned conjugate gradient method. Numerical results are presented demonstrating efficiency of the preconditioners. © 2005 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 2006     

Block diagonally preconditioned PIU methods of saddle point problem

For large sparse saddle point problems, we firstly introduce the block diagonally preconditioned Gauss-Seidl method (PBGS) which reduces to the GSOR method [Z.-Z. Bai, B.N. Parlett, Z.-Q. Wang, On generalized successive overrelaxation methods for augmented linear systems, Numer. Math. 102 (2005) 1-38] and PIU method [Z.-Z. Bai, Z.-Q. Wang, On parameterized inexact Uzawa methods for generalized saddle point problems, Linear Algebra Appl. 428 (2008) 2900-2932] when the preconditioners equal to different matrices, respectively. Then we generalize the PBGS method to the PPIU method and discuss the sufficient conditions such that the spectral radius of the PPIU method is much less than one. Furthermore, some rules are considered for choices of the preconditioners including the splitting method of the (1, 1) block matrix in the PIU method and numerical examples are given to show the superiority of the new method to the PIU method.     

Preconditioners and their analyses for edge element saddle-point systems arising from time-harmonic Maxwell’s equations

Numerical Algorithms - We derive and propose a family of new preconditioners for the saddle-point systems arising from the edge element discretization of the time-harmonic Maxwell’s equations...     

Two-level hierarchically preconditioned conjugate gradient methods for solving linear elasticity finite element equations

In this paper we study and compare some preconditioned conjugate gradient methods for solving large-scale higher-order finite element schemes approximating two- and three-dimensional linear elasticity boundary value problems. The preconditioners discussed in this paper are derived from hierarchical splitting of the finite element space first proposed by O. Axelsson and I. Gustafsson. We especially focus our attention to the implicit construction of preconditioning operators by means of some fixpoint iteration process including multigrid techniques. Many numerical experiments confirm the efficiency of these preconditioners in comparison with classical direct methods most frequently used in practice up to now.     

Preconditioning indefinite discretization matrices

Summary The finite element discretization of many elliptic boundary value problems leads to linear systems with positive definite and symmetric coefficient matrices. Many efficient preconditioners are known for these systems. We show that these preconditioning matrices can also be used for the linear systems arising from boundary value problems which are potentially indefinite due to lower order terms in the partial differential equation. Our main tool is a careful algebraic analysis of the condition numbers and the spectra of perturbed matrices which are preconditioned by the same matrices as in the unperturbed case.     

Eigenvalue estimates for preconditioned saddle point matrices

New accurate eigenvalue bounds for symmetric matrices of saddle point form are derived and applied for both unpreconditioned and preconditioned versions of the matrices. The estimates enable a better understanding of how preconditioners should be chosen. The preconditioners provide efficient iterative solution of the corresponding linear systems with, for some important applications, an optimal order of computational complexity. The methods are applied for Stokes problem and for linear elasticity problems. Copyright © 2005 John Wiley & Sons, Ltd.     

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.     

Modified block preconditioners for the discretized time-harmonic Maxwell equations in mixed form

In this paper, building on the previous work by Greif and Schötzau [Preconditioners for the discretized time-harmonic Maxwell equations in mixed form, Numer. Linear Algebra Appl. 14 (2007) 281–297] and Benzi and Olshanskii [An augmented lagrangian-based approach to the Oseen problem, SIAM J. Sci. Comput. 28 (2006) 2095–2113], we present the improved preconditioning techniques for the iterative solution of the saddle point linear systems, which arise from the finite element discretization of the mixed formulation of the time-harmonic Maxwell equations. The modified block diagonal and triangular preconditioners considered are based on augmentation with using the symmetric nonsingular weighted matrix. We discuss the spectral properties of the preconditioned matrix in detail and generalize the results of the above-mentioned paper by Greif and Schötzau. Numerical experiments are given to demonstrate the efficiency of the presented preconditioners.     

Spectral estimates for unreduced symmetric KKT systems arising from Interior Point methods

We consider symmetrized Karush–Kuhn–Tucker systems arising in the solution of convex quadratic programming problems in standard form by Interior Point methods. Their coefficient matrices usually have 3 × 3 block structure, and under suitable conditions on both the quadratic programming problem and the solution, they are nonsingular in the limit. We present new spectral estimates for these matrices: the new bounds are established for the unpreconditioned matrices and for the matrices preconditioned by symmetric positive definite augmented preconditioners. Some of the obtained results complete the analysis recently given by Greif, Moulding, and Orban in [SIAM J. Optim., 24 (2014), pp. 49‐83]. The sharpness of the new estimates is illustrated by numerical experiments. Copyright © 2016 John Wiley & Sons, Ltd.     

On HSS-based constraint preconditioners for generalized saddle-point problems

For the generalized saddle-point problems with non-Hermitian (1,1) blocks, we present an HSS-based constraint preconditioner, in which the (1,1) block of the preconditioner is constructed by the HSS method for solving the non-Hermitian positive definite linear systems. We analyze the invertibility of the HSS-based constraint preconditioner and prove the convergence of the preconditioned iteration method. Numerical experiments are used to demonstrate the efficiency of the preconditioner as well as the corresponding preconditioned iteration method, especially when the (1,1) block of the saddle-point matrix is essentially non-Hermitian.     

Additive block diagonal preconditioning for block two-by-two linear systems of skew-Hamiltonian coefficient matrices

For a class of block two-by-two systems of linear equations with certain skew-Hamiltonian coefficient matrices, we construct additive block diagonal preconditioning matrices and discuss the eigen-properties of the corresponding preconditioned matrices. The additive block diagonal preconditioners can be employed to accelerate the convergence rates of Krylov subspace iteration methods such as MINRES and GMRES. Numerical experiments show that MINRES preconditioned by the exact and the inexact additive block diagonal preconditioners are effective, robust and scalable solvers for the block two-by-two linear systems arising from the Galerkin finite-element discretizations of a class of distributed control problems.     

Algebraic multilevel iteration method for Stieltjes matrices

The numerical solution of elliptic selfadjoint second-order boundary value problems leads to a class of linear systems of equations with symmetric, positive definite, large and sparse matrices which can be solved iteratively using a preconditioned version of some algorithm. Such differential equations originate from various applications such as heat conducting and electromagnetics. Systems of equations of similar type can also arise in the finite element analysis of structures. We discuss a recursive method constructing preconditioners to a symmetric, positive definite matrix. An algebraic multilevel technique based on partitioning of the matrix in two by two matrix block form, approximating some of these by other matrices with more simple sparsity structure and using the corresponding Schur complement as a matrix on the lower level, is considered. The quality of the preconditioners is improved by special matrix polynomials which recursively connect the preconditioners on every two adjoining levels. Upper and lower bounds for the degree of the polynomials are derived as conditions for a computational complexity of optimal order for each level and for an optimal rate of convergence, respectively. The method is an extended and more accurate algebraic formulation of a method for nine-point and mixed five- and nine-point difference matrices, presented in some previous papers.     

on hybrid preconditioning methods for large sparse saddle-point problems

Based on the block-triangular product approximation to a 2-by-2 block matrix, a class of hybrid preconditioning methods is designed for accelerating the MINRES method for solving saddle-point problems. The appropriate values for the parameters involved in the new preconditioners are estimated, so that the numerical conditioning and the spectral property of the saddle-point matrix of the linear system can be substantially improved. Several practical hybrid preconditioners and the corresponding preconditioning iterative methods are constructed and studied, too.     

Preconditioned iterative algorithms for large sparse unsymmetric problems

A numerical study of the efficiency of the generalized conjugate residual methods (GCR) is performed using three different preconditioners all based upon an incomplete LU factorization. The GCR behavior is evaluated in connection with the solution of large, sparse unsymmetric systems of equations, arising from the finite element integration of the diffusion-convection equation for 2-dimensional (2-D) and 3-D problems with different Peclet and Courant numbers. The order of the test matrices ranges from 450 to 1700. Results from a set of numerical experiments are presented and comparisons with preconditioned GCR methods and with direct method are carried out.     

Optimality of multilevel preconditioning for nonconforming P1 finite elements

We prove the optimality of hierarchical and BPX-type preconditioners for finite element discretizations with nonconforming P1 finite elements. Such preconditioners were proposed about 15 years ago, and until now only suboptimal estimates of their preconditioning properties have been available. The main new tool is an improved Bernstein type inequality for an associated subdivision process generated by the prolongations which allows us to give an asymptotically optimal upper bound for the spectrum of the preconditioned systems.     

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.