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.     

Structured preconditioners for nonsingular matrices of block two-by-two structures

For the large sparse block two-by-two real nonsingular matrices, we establish a general framework of practical and efficient structured preconditioners through matrix transformation and matrix approximations. For the specific versions such as modified block Jacobi-type, modified block Gauss-Seidel-type, and modified block unsymmetric (symmetric) Gauss-Seidel-type preconditioners, we precisely describe their concrete expressions and deliberately analyze eigenvalue distributions and positive definiteness of the preconditioned matrices. Also, we show that when these structured preconditioners are employed to precondition the Krylov subspace methods such as GMRES and restarted GMRES, fast and effective iteration solvers can be obtained for the large sparse systems of linear equations with block two-by-two coefficient matrices. In particular, these structured preconditioners can lead to efficient and high-quality preconditioning matrices for some typical matrices from the real-world applications.

     

A general approach to analyse preconditioners for two‐by‐two block matrices

Two‐by‐two block matrices arise in various applications, such as in domain decomposition methods or when solving boundary value problems discretised by finite elements from the separation of the node set of the mesh into ‘fine’ and ‘coarse’ nodes. Matrices with such a structure, in saddle point form arise also in mixed variable finite element methods and in constrained optimisation problems. A general algebraic approach to construct, analyse and control the accuracy of preconditioners for matrices in two‐by‐two block form is presented. This includes both symmetric and nonsymmetric matrices, as well as indefinite matrices. The action of the preconditioners can involve element‐by‐element approximations and/or geometric or algebraic multigrid/multilevel methods. Copyright © 2011 John Wiley & Sons, Ltd.     

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     

Modified Block SSOR Preconditioners for Symmetric Positive Definite Linear Systems

A class of modified block SSOR preconditioners is presented for the symmetric positive definite systems of linear equations, whose coefficient matrices come from the hierarchical-basis finite-element discretizations of the second-order self-adjoint elliptic boundary value problems. These preconditioners include a block SSOR iteration preconditioner, and two inexact block SSOR iteration preconditioners whose diagonal matrices except for the (1,1)-block are approximated by either point symmetric Gauss–Seidel iterations or incomplete Cholesky factorizations, respectively. The optimal relaxation factors involved in these preconditioners and the corresponding optimal condition numbers are estimated in details through two different approaches used by Bank, Dupont and Yserentant (Numer. Math. 52 (1988) 427–458) and Axelsson (Iterative Solution Methods (Cambridge University Press, 1994)). Theoretical analyses show that these modified block SSOR preconditioners are very robust, have nearly optimal convergence rates, and especially, are well suited to difficult problems with rough solutions, discretized using highly nonuniform, adaptively refined meshes.     

Robust additive block triangular preconditioners for block two-by-two linear systems

Numerical Algorithms - In this paper, a class of additive block triangular preconditioners are constructed for solving block two-by-two linear systems with symmetric positive (semi-)definite...     

A variant of block incomplete factorization preconditioners for a symmetricH-matrix

We propose a variant of parallel block incomplete factorization preconditioners for a symmetric block-tridiagonalH-matrix. Theoretical properties of these block preconditioners are compared with those of block incomplete factorization preconditioners for the corresponding comparison matrix. Numerical results of the preconditioned CG(PCG) method using these block preconditioners are compared with those of PCG using other types of block incomplete factorization preconditioners. Lastly, parallel computations of the block incomplete factorization preconditioners are carried out on the Cray C90.     

An improved block splitting preconditioner for complex symmetric indefinite linear systems

In this paper, an improved block splitting preconditioner for a class of complex symmetric indefinite linear systems is proposed. By adopting two iteration parameters and the relaxation technique, the new preconditioner not only remains the same computational cost with the block preconditioners but also is much closer to the original coefficient matrix. The theoretical analysis shows that the corresponding iteration method is convergent under suitable conditions and the preconditioned matrix can have well-clustered eigenvalues around (0,1) with a reasonable choice of the relaxation parameters. An estimate concerning the dimension of the Krylov subspace for the preconditioned matrix is also obtained. Finally, some numerical experiments are presented to illustrate the effectiveness of the presented preconditioner.     

Minimum residual methods for augmented systems

For large systems of linear equations, iterative methods provide attractive solution techniques. We describe the applicability and convergence of iterative methods of Krylov subspace type for an important class of symmetric and indefinite matrix problems, namely augmented (or KKT) systems. Specifically, we consider preconditioned minimum residual methods and discuss indefinite versus positive definite preconditioning. For a natural choice of starting vector we prove that when the definite and indenfinite preconditioners are related in the obvious way, MINRES (which is applicable in the case of positive definite preconditioning) and full GMRES (which is applicable in the case of indefinite preconditioning) give residual vectors with identical Euclidean norm at each iteration. Moreover, we show that the convergence of both methods is related to a system of normal equations for which the LSQR algorithm can be employed. As a side result, we give a rare example of a non-trivial normal(1) matrix where the corresponding inner product is explicitly known: a conjugate gradient method therefore exists and can be employed in this case. This work was supported by British Council/German Academic Exchange Service Research Collaboration Project 465 and NATO Collaborative Research Grant CRG 960782     

Using constraint preconditioners with regularized saddle-point problems

The problem of finding good preconditioners for the numerical solution of a certain important class of indefinite linear systems is considered. These systems are of a 2 by 2 block (KKT) structure in which the (2,2) block (denoted by -C) is assumed to be nonzero. In Constraint preconditioning for indefinite linear systems, SIAM J. Matrix Anal. Appl. 21 (2000), Keller, Gould and Wathen introduced the idea of using constraint preconditioners that have a specific 2 by 2 block structure for the case of C being zero. We shall give results concerning the spectrum and form of the eigenvectors when a preconditioner of the form considered by Keller, Gould and Wathen is used but the system we wish to solve may have C ≠0. In particular, the results presented here indicate clustering of eigenvalues and, hence, faster convergence of Krylov subspace iterative methods when the entries of C are small; such a situations arise naturally in interior point methods for optimization and we present results for such problems which validate our conclusions.     

A QMR-based interior-point algorithm for solving linear programs

A new approach for the implementation of interior-point methods for solving linear programs is proposed. Its main feature is the iterative solution of the symmetric, but highly indefinite 2×2-block systems of linear equations that arise within the interior-point algorithm. These linear systems are solved by a symmetric variant of the quasi-minimal residual (QMR) algorithm, which is an iterative solver for general linear systems. The symmetric QMR algorithm can be combined with indefinite preconditioners, which is crucial for the efficient solution of highly indefinite linear systems, yet it still fully exploits the symmetry of the linear systems to be solved. To support the use of the symmetric QMR iteration, a novel stable reduction of the original unsymmetric 3×3-block systems to symmetric 2×2-block systems is introduced, and a measure for a low relative accuracy for the solution of these linear systems within the interior-point algorithm is proposed. Some indefinite preconditioners are discussed. Finally, we report results of a few preliminary numerical experiments to illustrate the features of the new approach.     

Improving the stability and robustness of incomplete symmetric indefinite factorization preconditioners

Sparse symmetric indefinite linear systems of equations arise in numerous practical applications. In many situations, an iterative method is the method of choice but a preconditioner is normally required for it to be effective. In this paper, the focus is on a class of incomplete factorization algorithms that can be used to compute preconditioners for symmetric indefinite systems. A limited memory approach is employed that incorporates a number of new ideas with the goal of improving the stability, robustness, and efficiency of the preconditioner. These include the monitoring of stability as the factorization proceeds and the incorporation of pivot modifications when potential instability is observed. Numerical experiments involving test problems arising from a range of real‐world applications demonstrate the effectiveness of our approach.     

A class of modified block SSOR preconditioners for symmetric positive definite systems of linear equations

A class of modified block SSOR preconditioners is presented for solving symmetric positive definite systems of linear equations, which arise in the hierarchical basis finite element discretizations of the second order self‐adjoint elliptic boundary value problems. This class of methods is strongly related to two level methods, standard multigrid methods, and Jacobi‐like hierarchical basis methods. The optimal relaxation factors and optimal condition numbers are estimated in detail. Theoretical analyses show that these methods are very robust, and especially well suited to difficult problems with rough solutions, discretized using highly nonuniform, adaptively refined meshes. This revised version was published online in June 2006 with corrections to the Cover Date.     

Uzawa methods for a class of block three‐by‐three saddle‐point problems

In this work, we consider numerical methods for solving a class of block three‐by‐three saddle‐point problems, which arise from finite element methods for solving time‐dependent Maxwell equations and some other applications. The direct extension of the Uzawa method for solving this block three‐by‐three saddle‐point problem requires the exact solution of a symmetric indefinite system of linear equations at each step. To avoid heavy computations at each step, we propose an inexact Uzawa method, which solves the symmetric indefinite linear system in some inexact way. Under suitable assumptions, we show that the inexact Uzawa method converges to the unique solution of the saddle‐point problem within the approximation level. Two special algorithms are customized for the inexact Uzawa method combining the splitting iteration method and a preconditioning technique, respectively. Numerical experiments are presented, which demonstrated the usefulness of the inexact Uzawa method and the two customized algorithms.     

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 modified block SSOR iteration methods for linear systems from steady incompressible viscous flow problems

In order to solve the large sparse systems of linear equations arising from numerical solutions of two-dimensional steady incompressible viscous flow problems in primitive variable formulation, we present block SSOR and modified block SSOR iteration methods based on the special structures of the coefficient matrices. In each step of the block SSOR iteration, we employ the block LU factorization to solve the sub-systems of linear equations. We show that the block LU factorization is existent and stable when the coefficient matrices are block diagonally dominant of type-II by columns. Under suitable conditions, we establish convergence theorems for both block SSOR and modified block SSOR iteration methods. In addition, the block SSOR iteration and AF-ADI method are considered as preconditioners for the nonsymmetric systems of linear equations. Numerical experiments show that both block SSOR and modified block SSOR iterations are feasible iterative solvers and they are also effective for preconditioning Krylov subspace methods such as GMRES and BiCGSTAB when used to solve this class of systems of linear equations.     

A convergence analysis for a sweeping preconditioner for block tridiagonal systems of linear equations

We study sweeping preconditioners for symmetric and positive definite block tridiagonal systems of linear equations. The algorithm provides an approximate inverse that can be used directly or in a preconditioned iterative scheme. These algorithms are based on replacing the Schur complements appearing in a block Gaussian elimination direct solve by hierarchical matrix approximations with reduced off‐diagonal ranks. This involves developing low rank hierarchical approximations to inverses. We first provide a convergence analysis for the algorithm for reduced rank hierarchical inverse approximation. These results are then used to prove convergence and preconditioning estimates for the resulting sweeping preconditioner. Copyright © 2014 John Wiley & Sons, Ltd.     

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.     

Limited memory preconditioners for symmetric indefinite problems with application to structural mechanics

This paper presents a class of limited memory preconditioners (LMP) for solving linear systems of equations with symmetric indefinite matrices and multiple right‐hand sides. These preconditioners based on limited memory quasi‐Newton formulas require a small number k of linearly independent vectors and may be used to improve an existing first‐level preconditioner. The contributions of the paper are threefold. First, we derive a formula to characterize the spectrum of the preconditioned operator. A spectral analysis of the preconditioned matrix shows that the eigenvalues are all real and that the LMP class is able to cluster at least k eigenvalues at 1. Secondly, we show that the eigenvalues of the preconditioned matrix enjoy interlacing properties with respect to the eigenvalues of the original matrix provided that the k linearly independent vectors have been prior projected onto the invariant subspaces associated with the eigenvalues of the original matrix in the open right and left half‐plane, respectively. Third, we focus on theoretical properties of the Ritz‐LMP variant, where Ritz information is used to determine the k vectors. Finally, we illustrate the numerical behaviour of the Ritz limited memory preconditioners on realistic applications in structural mechanics that require the solution of sequences of large‐scale symmetric saddle‐point systems. Numerical experiments show the relevance of the proposed preconditioner leading to a significant decrease in terms of computational operations when solving such sequences of linear systems. A saving of up to 43% in terms of computational effort is obtained on one of these applications. Copyright © 2016 John Wiley & Sons, Ltd.