A relaxed positive semi-definite and skew-Hermitian splitting preconditioner for non-Hermitian generalized saddle point problems

For non-Hermitian saddle point linear systems, Pan, Ng and Bai presented a positive semi-definite and skew-Hermitian splitting (PSS) preconditioner (Pan et al. Appl. Math. Comput. 172, 762–771 2006), to accelerate the convergence rate of the Krylov subspace iteration methods like the GMRES method. In this paper, a relaxed positive semi-definite and skew-Hermitian (RPSS) splitting preconditioner based on the PSS preconditioner for the non-Hermitian generalized saddle point problems is considered. The distribution of eigenvalues and the form of the eigenvectors of the preconditioned matrix are analyzed. Moreover, an upper bound on the degree of the minimal polynomial is also studied. Finally, numerical experiments of a model Navier-Stokes equation are presented to illustrate the efficiency of the RPSS preconditioner compared to the PSS preconditioner, the block diagonal preconditioner (BD), and the block triangular preconditioner (BT) in terms of the number of iteration and computational time.     

A generalized variant of the deteriorated PSS preconditioner for nonsymmetric saddle point problems

Based on the variant of the deteriorated positive-definite and skew-Hermitian splitting (VDPSS) preconditioner developed by Zhang and Gu (BIT Numer. Math. 56:587–604, 2016), a generalized VDPSS (GVDPSS) preconditioner is established in this paper by replacing the parameter α in (2,2)-block of the VDPSS preconditioner by another parameter β. This preconditioner can also be viewed as a generalized form of the VDPSS preconditioner and the new relaxed HSS (NRHSS) preconditioner which has been exhibited by Salkuyeh and Masoudi (Numer. Algorithms, 2016). The convergence properties of the GVDPSS iteration method are derived. Meanwhile, the distribution of eigenvalues and the forms of the eigenvectors of the preconditioned matrix are analyzed in detail. We also study the upper bounds on the degree of the minimum polynomial of the preconditioned matrix. Numerical experiments are implemented to illustrate the effectiveness of the GVDPSS preconditioner and verify that the GVDPSS preconditioned generalized minimal residual method is superior to the DPSS, relaxed DPSS, SIMPLE-like, NRHSS, and VDPSS preconditioned ones for solving saddle point problems in terms of the iterations and computational times.     

Two new modified Gauss–Seidel methods for linear system with -matrices

In 2002, H. Kotakemori et al. proposed the modified Gauss–Seidel (MGS) method for solving the linear system with the preconditioner [H. Kotakemori, K. Harada, M. Morimoto, H. Niki, A comparison theorem for the iterative method with the preconditioner () J. Comput. Appl. Math. 145 (2002) 373–378]. Since this preconditioner is constructed by only the largest element on each row of the upper triangular part of the coefficient matrix, the preconditioning effect is not observed on the nth row. In the present paper, to deal with this drawback, we propose two new preconditioners. The convergence and comparison theorems of the modified Gauss–Seidel methods with these two preconditioners for solving the linear system are established. The convergence rates of the new proposed preconditioned methods are compared. In addition, numerical experiments are used to show the effectiveness of the new MGS methods.     

On the convergence rate improvement of a primal-dual splitting algorithm for solving monotone inclusion problems

We present two modified versions of the primal-dual splitting algorithm relying on forward–backward splitting proposed in V\(\tilde{\mathrm{u}}\) (Adv Comput Math 38(3):667–681, 2013) for solving monotone inclusion problems. Under strong monotonicity assumptions for some of the operators involved we obtain for the sequences of iterates that approach the solution orders of convergence of \(\mathcal{{O}}(\frac{1}{n})\) and \(\mathcal{{O}}(\omega ^n)\), for \(\omega \in (0,1)\), respectively. The investigated primal-dual algorithms are fully decomposable, in the sense that the operators are processed individually at each iteration. We also discuss the modified algorithms in the context of convex optimization problems and present numerical experiments in image processing and pattern recognition in cluster analysis.     

A new iterative method for solving a class of complex symmetric system of linear equations

We present a new stationary iterative method, called Scale-Splitting (SCSP) method, and investigate its convergence properties. The SCSP method naturally results in a simple matrix splitting preconditioner, called SCSP-preconditioner, for the original linear system. Some numerical comparisons are presented between the SCSP-preconditioner and several available block preconditioners, such as PGSOR (Hezari et al. Numer. Linear Algebra Appl. 22, 761–776, 2015) and rotate block triangular preconditioners (Bai Sci. China Math. 56, 2523–2538, 2013), when they are applied to expedite the convergence rate of Krylov subspace iteration methods for solving the original complex system and its block real formulation, respectively. Numerical experiments show that the SCSP-preconditioner can compete with PGSOR-preconditioner and even more effective than the rotate block triangular preconditioners.     

Semi-convergence analysis of preconditioned deteriorated PSS iteration method for singular saddle point problems

In this paper, we propose a two-parameter preconditioned variant of the deteriorated PSS iteration method (J. Comput. Appl. Math., 273, 41–60 (2015)) for solving singular saddle point problems. Semi-convergence analysis shows that the new iteration method is convergent unconditionally. The new iteration method can also be regarded as a preconditioner to accelerate the convergence of Krylov subspace methods. Eigenvalue distribution of the corresponding preconditioned matrix is presented, which is instructive for the Krylov subspace acceleration. Note that, when the leading block of the saddle point matrix is symmetric, the new iteration method will reduce to the preconditioned accelerated HSS iteration method (Numer. Algor., 63 (3), 521–535 2013), the semi-convergence conditions of which can be simplified by the results in this paper. To further improve the effectiveness of the new iteration method, a relaxed variant is given, which has much better convergence and spectral properties. Numerical experiments are presented to investigate the performance of the new iteration methods for solving singular saddle point problems.     

Convergence Analysis of Modified Iterative Methods to Solve Linear Systems

In the past years, a growing interest to solve linear systems with modified iterative methods has been shown by researchers. Recently, Dehghan and Hajarian (J Vib Control, doi:10.1177/10775463124, 2012)based on preconditioned methods, introduced modified accelerated overrelaxation methods for solving linear systems. These authors stated that the best property of the mentioned methods is that they can be used under mild conditions than the Milaszewicz’s (Linear Algebra Appl 93:161–170, 1987) preconditioner. In this paper, we show that the Milaszewicz’s preconditioner is applicable under mild conditions and also, under these conditions, Milaszewicz’s preconditioner is superior to the Dehghan and Hajarian’s preconditioner. Numerical examples are also given to illustrate our results.     

A modified generalized shift-splitting preconditioner for nonsymmetric saddle point problems

For the nonsymmetric saddle point problems with nonsymmetric positive definite (1,1) parts, the modified generalized shift-splitting (MGSS) preconditioner as well as the MGSS iteration method is derived in this paper, which generalize the modified shift-splitting (MSS) preconditioner and the MSS iteration method newly developed by Huang and Su (J. Comput. Appl. Math. 317:535–546, 2017), respectively. The convergent and semi-convergent analyses of the MGSS iteration method are presented, and we prove that this method is unconditionally convergent and semi-convergent. Meanwhile, some spectral properties of the preconditioned matrix are carefully analyzed. Numerical results demonstrate the robustness and effectiveness of the MGSS preconditioner and the MGSS iteration method and also illustrate that the MGSS iteration method outperforms the generalized shift-splitting (GSS) and the generalized modified shift-splitting (GMSS) iteration methods, and the MGSS preconditioner is superior to the shift-splitting (SS), GSS, modified SS (M-SS), GMSS and MSS preconditioners for the generalized minimal residual (GMRES) method for solving the nonsymmetric saddle point problems.     

Mann type iterative methods for finding a common solution of split feasibility and fixed point problems

The purpose of this paper is to study and analyze three different kinds of Mann type iterative methods for finding a common element of the solution set ?? of the split feasibility problem and the set Fix(S) of fixed points of a nonexpansive mapping S in the setting of infinite-dimensional Hilbert spaces. By combining Mann??s iterative method and the extragradient method, we first propose Mann type extragradient-like algorithm for finding an element of the set ${{{\rm Fix}}(S) \cap \Gamma}$ ; moreover, we derive the weak convergence of the proposed algorithm under appropriate conditions. Second, we combine Mann??s iterative method and the viscosity approximation method to introduce Mann type viscosity algorithm for finding an element of the ${{{\rm Fix}}(S)\cap \Gamma}$ ; moreover, we derive the strong convergence of the sequences generated by the proposed algorithm to an element of set ${{{\rm Fix}}(S) \cap \Gamma}$ under mild conditions. Finally, by combining Mann??s iterative method and the relaxed CQ method, we introduce Mann type relaxed CQ algorithm for finding an element of the set ${{{\rm Fix}}(S)\cap \Gamma}$ . We also establish a weak convergence result for the sequences generated by the proposed Mann type relaxed CQ algorithm under appropriate assumptions.     

Special issue: recent progress on iterative methods for large systems of equations

Let A x = b be a large and sparse system of linear equations where A is a nonsingular matrix. An approximate solution is frequently obtained by applying preconditioned iterations. Consider the matrix B = A + P Q ^T where \(P, Q \in \mathbb {R}^{n \times k}\) are full rank matrices. In this work, we study the problem of updating a previously computed preconditioner for A in order to solve the updated linear system B x = b by preconditioned iterations. In particular, we propose a method for updating a Balanced Incomplete Factorization preconditioner. The strategy is based on the computation of an approximate Inverse Sherman-Morrison decomposition for an equivalent augmented linear system. Approximation properties of the preconditioned matrix and an analysis of the computational cost of the algorithm are studied. Moreover, the results of the numerical experiments with different types of problems show that the proposed method contributes to accelerate the convergence.     

Localization of the eigenvalues of a pencil of positive definite matrices

Let A and B be real square positive definite matrices close to each other. A domain S on the complex plane that contains all the eigenvalues λ of the problem Az = λBz is constructed analytically. The boundary ?S of S is a curve known as the limacon of Pascal. Using the standard conformal mapping of the exterior of this curve (or of the exterior of an enveloping circular lune) onto the exterior of the unit disc, new analytical bounds are obtained for the convergence rate of the minimal residual method (GMRES) as applied to solving the linear system Ax = b with the preconditioner B.     

A note on the implementation of an interior-point algorithm for nonlinear optimization with inexact step computations

This paper describes an implementation of an interior-point algorithm for large-scale nonlinear optimization. It is based on the algorithm proposed by Curtis et?al. (SIAM J Sci Comput 32:3447?C3475, 2010), a method that possesses global convergence guarantees to first-order stationary points with the novel feature that inexact search direction calculations are allowed in order to save computational expense. The implementation follows the proposed algorithm, but includes many practical enhancements, such as functionality to avoid the computation of a normal step during every iteration. The implementation is included in the IPOPT software package paired with an iterative linear system solver and preconditioner provided in PARDISO. Numerical results on a large nonlinear optimization test set and two PDE-constrained optimization problems with control and state constraints are presented to illustrate that the implementation is robust and efficient for large-scale applications.     

A preconditioned general modulus-based matrix splitting iteration method for linear complementarity problems of <Emphasis Type="Italic">H</Emphasis>-matrices

In this paper, we propose a preconditioned general modulus-based matrix splitting iteration method for solving modulus equations arising from linear complementarity problems. Its convergence theory is proved when the system matrix is an H₊-matrix, from which some new convergence conditions can be derived for the (general) modulus-based matrix splitting iteration methods. Numerical results further show that the proposed methods are superior to the existing methods.     

KP<Subscript>1</Subscript> acceleration scheme for inner iterations consistent with the weighted diamond differencing scheme for the transport equation in three-dimensional geometry

For the transport equation in three-dimensional (r, ?, z) geometry, a KP₁ acceleration scheme for inner iterations that is consistent with the weighted diamond differencing (WDD) scheme is constructed. The P ₁ system for accelerating corrections is solved by an algorithm based on the cyclic splitting method (SM) combined with Gaussian elimination as applied to auxiliary systems of two-point equations. No constraints are imposed on the choice of the weights in the WDD scheme, and the algorithm can be used, for example, in combination with an adaptive WDD scheme. For problems with periodic boundary conditions, the two-point systems of equations are solved by the cyclic through-computations method elimination. The influence exerted by the cycle step choice and the convergence criterion for SM iterations on the efficiency of the algorithm is analyzed. The algorithm is modified to threedimensional (x, y, z) geometry. Numerical examples are presented featuring the KP₁ scheme as applied to typical radiation transport problems in three-dimensional geometry, including those with an important role of scattering anisotropy. A reduction in the efficiency of the consistent KP₁ scheme in highly heterogeneous problems with dominant scattering in non-one-dimensional geometry is discussed. An approach is proposed for coping with this difficulty. It is based on improving the monotonicity of the difference scheme used to approximate the transport equation.     

Iterative processes based on block <Emphasis Type="Italic">H</Emphasis>-splittings

Block H-splittings of block square matrices (which, in general, have complex entries) are examined. It is shown that block H-matrices are the only ones that admit this type of splittings. Iterative processes corresponding to these splittings are proved to be convergent. The concept of a simple splitting of a block matrix is introduced, and the convergence of iterative processes related to simple splittings of block H-matrices is investigated. Multisplitting and nonstationary iterative processes based on block H-splittings are considered. Sufficient conditions for their convergence are derived, and some estimates for the asymptotic convergence rate are given.     

The preconditioned Gauss–Seidel method faster than the SOR method

In recent years, a number of preconditioners have been applied to linear systems [A.D. Gunawardena, S.K. Jain, L. Snyder, Modified iterative methods for consistent linear systems, Linear Algebra Appl. 154–156 (1991) 123–143; T. Kohno, H. Kotakemori, H. Niki, M. Usui, Improving modified Gauss–Seidel method for Z-matrices, Linear Algebra Appl. 267 (1997) 113–123; H. Kotakemori, K. Harada, M. Morimoto, H. Niki, A comparison theorem for the iterative method with the preconditioner (I+_Smax)$(I+S_{\mathit{max}})$, J. Comput. Appl. Math. 145 (2002) 373–378; H. Kotakemori, H. Niki, N. Okamoto, Accelerated iteration method for Z$Z$-matrices, J. Comput. Appl. Math. 75 (1996) 87–97; M. Usui, H. Niki, T.Kohno, Adaptive Gauss-Seidel method for linear systems, Internat. J. Comput. Math. 51(1994)119–125 [10]]. Since these preconditioners are constructed from the elements of the upper triangular part of the coefficient matrix, the preconditioning effect is not observed on the n$n$th row of matrix A. In the present paper, in order to deal with this drawback, we propose a new preconditioner. In addition, the convergence and comparison theorems of the proposed method are established. Simple numerical examples are also given, and we show that the convergence rate of the proposed method is better than that of the optimum SOR.     

Fast structured LU factorization for nonsymmetric matrices

In this paper, an approximate LU factorization algorithm is developed for nonsymmetric matrices based on the hierarchically semiseparable matrix techniques. It utilizes a technique involving orthogonal transformations and approximations to avoid the explicit computation of the Schur complement in each factorization step. A modified compression method is further developed for the case when some diagonal blocks have small singular values. The complexity of the methods proposed in this paper is analyzed and shown to be $O(N^2k)$ , where $N$ is the dimension of matrix and $k$ is the maximum off-diagonal (numerical) rank. Depending on the accuracy and efficiency requirements in the approximation, this factorization can be used either as a direct solver or a preconditioner. Numerical results from applications are included to show the efficiency of our method.     

A modified positive-definite and skew-Hermitian splitting preconditioner for generalized saddle point problems from the Navier-Stokes equation

In this paper, we extend the relaxed positive-definite and skew-Hermitian splitting preconditioner (RPSS) for generalized saddle-point problems in [J.-L. Zhang, C.-Q. Gu and K. Zhang, Appl. Math. Comput. 249(2014)468-479] by introducing an additional parameter. The spectral properties of the presented new preconditioned matrix for generalized saddle-point problem are investigated, meanwhile, the infinite termination merit of the iterative step is also discussed if the Krylov subspace method preconditioned by the modified positive-definite and skew-Hermitian splitting preconditioner (MPSS) is applied. Some numerical experiments illustrate that the efficiency of the proposed new preconditioner.     

Semilocal convergence of multi-point improved super-Halley-type methods without the second derivative under generalized weak condition

In this paper, we consider the semilocal convergence of multi-point improved super-Halley-type methods in Banach space. Different from the results of super-Halley method studied in reference Gutiérrez, J.M. and Hernández, M.A. (Comput. Math. Appl. 36,1–8, 1998) these methods do not require second derivative of an operator, the R-order is improved and the convergence condition is also relaxed. We prove a convergence theorem to show existence and uniqueness of the solution.