On local Hermitian and skew-Hermitian splitting iteration methods for generalized saddle point problems

In this paper, we first present a local Hermitian and skew-Hermitian splitting (LHSS) iteration method for solving a class of generalized saddle point problems. The new method converges to the solution under suitable restrictions on the preconditioning matrix. Then we give a modified LHSS (MLHSS) iteration method, and further extend it to the generalized saddle point problems, obtaining the so-called generalized MLHSS (GMLHSS) iteration method. Numerical experiments for a model Navier-Stokes problem are given, and the results show that the new methods outperform the classical Uzawa method and the inexact parameterized Uzawa method.     

Eigenvalue bounds for the Schur complement with a pressure convection–diffusion preconditioner in incompressible flow computations

If the stationary Navier–Stokes system or an implicit time discretization of the evolutionary Navier–Stokes system is linearized by a Picard iteration and discretized in space by a mixed finite element method, there arises a saddle point system which may be solved by a Krylov subspace method or an Uzawa type approach. For each of these resolution methods, it is necessary to precondition the Schur complement associated to the saddle point problem in question. In the work at hand, we give upper and lower bounds of the eigenvalues of this Schur complement under the assumption that it is preconditioned by a pressure convection–diffusion matrix.     

On HSS and AHSS iteration methods for nonsymmetric positive definite Toeplitz systems

Two iteration methods are proposed to solve real nonsymmetric positive definite Toeplitz systems of linear equations. These methods are based on Hermitian and skew-Hermitian splitting (HSS) and accelerated Hermitian and skew-Hermitian splitting (AHSS). By constructing an orthogonal matrix and using a similarity transformation, the real Toeplitz linear system is transformed into a generalized saddle point problem. Then the structured HSS and the structured AHSS iteration methods are established by applying the HSS and the AHSS iteration methods to the generalized saddle point problem. We discuss efficient implementations and demonstrate that the structured HSS and the structured AHSS iteration methods have better behavior than the HSS iteration method in terms of both computational complexity and convergence speed. Moreover, the structured AHSS iteration method outperforms the HSS and the structured HSS iteration methods. The structured AHSS iteration method also converges unconditionally to the unique solution of the Toeplitz linear system. In addition, an upper bound for the contraction factor of the structured AHSS iteration method is derived. Numerical experiments are used to illustrate the effectiveness of the structured AHSS iteration method.     

On nonsymmetric saddle point matrices that allow conjugate gradient iterations

Linear systems in saddle point form are usually highly indefinite,which often slows down iterative solvers such as Krylov subspace methods. It has been noted by several authors that negating the second block row of a symmetric indefinite saddle point matrix leads to a nonsymmetric matrix ${{\mathcal A}}Linear systems in saddle point form are usually highly indefinite,which often slows down iterative solvers such as Krylov subspace methods. It has been noted by several authors that negating the second block row of a symmetric indefinite saddle point matrix leads to a nonsymmetric matrix whose spectrum is entirely contained in the right half plane. In this paper we study conditions so that is diagonalizable with a real and positive spectrum. These conditions are based on necessary and sufficient conditions for positive definiteness of a certain bilinear form,with respect to which is symmetric. In case the latter conditions are satisfied, there exists a well defined conjugate gradient (CG) method for solving linear systems with . We give an efficient implementation of this method, discuss practical issues such as error bounds, and present numerical experiments. In memory of Gene Golub (1932–2007), our wonderful friend and colleague, who had a great interest in the conjugate gradient method and the numerical solution of saddle point problems. The work of J?rg Liesen was supported by the Emmy Noether-Program and the Heisenberg-Program of the Deutsche Forschungsgemeinschaft.     

A class of Uzawa-SOR methods for saddle point problems

In this paper, we consider a class of Uzawa-SOR methods for saddle point problems, and prove the convergence of the proposed methods. We solve a lower triangular system per iteration in the proposed methods, instead of solving a linear equation Az=b. Actually, the new methods can be considered as an inexact iteration method with the Uzawa as the outer iteration and the SOR as the inner iteration. Although the proposed methods cannot achieve the same convergence rate as the GSOR methods proposed by Bai et al. [Z.-Z. Bai, B.N. Parlett, Z.-Q. Wang, On generalized successive overrelaxation methods for augmented linear systems, Numer. Math. 102 (2005) 1-38], but our proposed methods have less workloads per iteration step. Experimental results show that our proposed methods are feasible and effective.     

New choices of preconditioning matrices for generalized inexact parameterized iterative methods

For large sparse saddle point problems, Chen and Jiang recently studied a class of generalized inexact parameterized iterative methods (see [F. Chen, Y.-L. Jiang, A generalization of the inexact parameterized Uzawa methods for saddle point problems, Appl. Math. Comput. 206 (2008) 765-771]). In this paper, the methods are modified and some choices of preconditioning matrices are given. These preconditioning matrices have advantages in solving large sparse linear system. Numerical experiments of a model Stokes problem are presented.     

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.     

The spectral properties of the preconditioned matrix for nonsymmetric saddle point problems

In this paper, on the basis of matrix splitting, two preconditioners are proposed and analyzed, for nonsymmetric saddle point problems. The spectral property of the preconditioned matrix is studied in detail. When the iteration parameter becomes small enough, the eigenvalues of the preconditioned matrices will gather into two clusters—one is near (0,0) and the other is near (2,0)—for the PPSS preconditioner no matter whether A is Hermitian or non-Hermitian and for the PHSS preconditioner when A is a Hermitian or real normal matrix. Numerical experiments are given, to illustrate the performances of the two preconditioners.     

A new alternating positive semidefinite splitting preconditioner for saddle point problems from time-harmonic eddy current models

Based on the special positive semidefinite splittings of the saddle point matrix, we propose a new alternating positive semidefinite splitting (APSS) iteration method for the saddle point problem arising from the finite element discretization of the hybrid formulation of the time-harmonic eddy current problem. We prove that the new APSS iteration method is unconditionally convergent for both cases of the simple topology and the general topology. The new APSS matrix can be used as a preconditioner to accelerate the convergence rate of Krylov subspace methods. Numerical results show that the new APSS preconditioner is superior to the existing preconditioners.     

Adaptive Monte Carlo methods for matrix equations with applications

This paper discusses empirical studies with both the adaptive correlated sequential sampling method and the adaptive importance sampling method which can be used in solving matrix and integral equations. Both methods achieve geometric convergence (provided the number of random walks per stage is large enough) in the sense: e_ν≤cλ^ν, where e_ν is the error at stage ν, λ∈(0,1) is a constant, c>0 is also a constant. Thus, both methods converge much faster than the conventional Monte Carlo method. Our extensive numerical test results show that the adaptive importance sampling method converges faster than the adaptive correlated sequential sampling method, even with many fewer random walks per stage for the same problem. The methods can be applied to problems involving large scale matrix equations with non-sparse coefficient matrices. We also provide an application of the adaptive importance sampling method to the numerical solution of integral equations, where the integral equations are converted into matrix equations (with order up to 8192×8192) after discretization. By using Niederreiter’s sequence, instead of a pseudo-random sequence when generating the nodal point set used in discretizing the phase space Γ, we find that the average absolute errors or relative errors at nodal points can be reduced by a factor of more than one hundred.     

Limiting accuracy of segregated solution methods for nonsymmetric saddle point problems

Nonsymmetric saddle point problems arise in a wide variety of applications in computational science and engineering. The aim of this paper is to discuss the numerical behavior of several nonsymmetric iterative methods applied for solving the saddle point systems via the Schur complement reduction or the null-space projection approach. Krylov subspace methods often produce the iterates which fluctuate rather strongly. Here we address the question whether large intermediate approximate solutions reduce the final accuracy of these two-level (inner–outer) iteration algorithms. We extend our previous analysis obtained for symmetric saddle point problems and distinguish between three mathematically equivalent back-substitution schemes which lead to a different numerical behavior when applied in finite precision arithmetic. Theoretical results are then illustrated on a simple model example.     

Another approach to multiobjective programming problems withF-convex functions

In this paper, optimality conditions for multiobjective programming problems havingF-convex objective and constraint functions are considered. An equivalent multiobjective programming problem is constructed by a modification of the objective function. Furthermore, anF—Lagrange function is introduced for a constructed multiobjective programming problem, and a new type of saddle point is introduced. Some results for the new type of a saddle point are given.     

On the augmented Lagrangian approach to Signorini elastic contact problem

Summary. The Signorini problem describes the contact of a linearly elastic body with a rigid frictionless foundation. It is transformed into a saddle point problem of some augmented Lagrangian functional and then discretized by finite element methods. Optimal error estimates are obtained for general smooth domains which are not necessarily convex. The key ingredient in the analysis is a discrete inf-sup condition which guarantees the existence of the saddle point. Received January 29, 1999 / Revised version received May 2, 2000 / Published online December 19, 2000     

On the eigenvalues of a class of saddle point matrices

We study spectral properties of a class of block 2 × 2 matrices that arise in the solution of saddle point problems. These matrices are obtained by a sign change in the second block equation of the symmetric saddle point linear system. We give conditions for having a (positive) real spectrum and for ensuring diagonalizability of the matrix. In particular, we show that these properties hold for the discrete Stokes operator, and we discuss the implications of our characterization for augmented Lagrangian formulations, for Krylov subspace solvers and for certain types of preconditioners. The work of this author was supported in part by the National Science Foundation grant DMS-0207599 Revision dated 5 December 2005.     

An alternating preconditioner for saddle point problems

Based on matrix splittings, a new alternating preconditioner with two parameters is proposed for solving saddle point problems. Some theoretical analyses for the eigenvalues of the associated preconditioned matrix are given. The choice of the parameters is considered and the quasi-optimal parameters are obtained. The new preconditioner with these quasi-optimal parameters significantly improves the convergence rate of the generalized minimal residual (GMRES) iteration. Numerical experiments from the linearized Navier-Stokes equations demonstrate the efficiency of the new preconditioner, especially on the larger viscosity parameter ν. Further extensions of the preconditioner to generalized saddle point matrices are also checked.     

Iterative algorithms for generalized mixed equilibrium problems

In this paper, we consider a generalized mixed equilibrium problem in real Hilbert space. Using the auxiliary principle, we define a class of resolvent mappings. Further, using fixed point and resolvent methods, we give some iterative algorithms for solving generalized mixed equilibrium problem. Furthermore, we prove that the sequences generated by iterative algorithms converge weakly to the solution of generalized mixed equilibrium problem. These results require monotonicity (θ-pseudo monotonicity) and continuity (Lipschitz continuity) for mappings.     

Block-iterative methods for consistent and inconsistent linear equations

Summary We shall in this paper consider the problem of computing a generalized solution of a given linear system of equations. The matrix will be partitioned by blocks of rows or blocks of columns. The generalized inverses of the blocks are then used as data to Jacobi- and SOR-types of iterative schemes. It is shown that the methods based on partitioning by rows converge towards the minimum norm solution of a consistent linear system. The column methods converge towards a least squares solution of a given system. For the case with two blocks explicit expressions for the optimal values of the iteration parameters are obtained. Finally an application is given to the linear system that arises from reconstruction of a two-dimensional object by its one-dimensional projections.     

A matrix perturbation method for computing the steady-state probability distributions of probabilistic Boolean networks with gene perturbations

Modeling genetic regulatory interactions is an important issue in systems biology. Probabilistic Boolean networks (PBNs) have been proved to be a useful tool for the task. The steady-state probability distribution of a PBN gives important information about the captured genetic network. The computation of the steady-state probability distribution involves the construction of the transition probability matrix of the PBN. The size of the transition probability matrix is 2ⁿ×2ⁿ where n is the number of genes. Although given the number of genes and the perturbation probability in a perturbed PBN, the perturbation matrix is the same for different PBNs, the storage requirement for this matrix is huge if the number of genes is large. Thus an important issue is developing computational methods from the perturbation point of view. In this paper, we analyze and estimate the steady-state probability distribution of a PBN with gene perturbations. We first analyze the perturbation matrix. We then give a perturbation matrix analysis for the captured PBN problem and propose a method for computing the steady-state probability distribution. An approximation method with error analysis is then given for further reducing the computational complexity. Numerical experiments are given to demonstrate the efficiency of the proposed methods.     

Schur complements on Hilbert spaces and saddle point systems

For any continuous bilinear form defined on a pair of Hilbert spaces satisfying the compatibility Ladyshenskaya–Babušca–Brezzi condition, symmetric Schur complement operators can be defined on each of the two Hilbert spaces. In this paper, we find bounds for the spectrum of the Schur operators only in terms of the compatibility and continuity constants. In light of the new spectral results for the Schur complements, we review the classical Babušca–Brezzi theory, find sharp stability estimates, and improve a convergence result for the inexact Uzawa algorithm. We prove that for any symmetric saddle point problem, the inexact Uzawa algorithm converges, provided that the inexact process for inverting the residual at each step has the relative error smaller than 1/3. As a consequence, we provide a new type of algorithm for discretizing saddle point problems, which combines the inexact Uzawa iterations with standard a posteriori error analysis and does not require the discrete stability conditions.     

Two class of synchronous matrix multisplitting schemes for solving linear complementarity problems

Many problems in the areas of scientific computing and engineering applications can lead to the solution of the linear complementarity problem LCP (M,q). It is well known that the matrix multisplitting methods have been found very useful for solving LCP (M,q). In this article, by applying the generalized accelerated overrelaxation (GAOR) and the symmetric successive overrelaxation (SSOR) techniques, we introduce two class of synchronous matrix multisplitting methods to solve LCP (M,q). Convergence results for these two methods are presented when M is an H-matrix (and also an M-matrix). Also the monotone convergence of the new methods is established. Finally, the numerical results show that the introduced methods are effective for solving the large and sparse linear complementary problems.