Convergence of parallel multisplitting methods using ILU factorizations

In this paper, we study the convergence of both relaxed multisplitting method and nonstationary two-stage multisplitting method associated with a multisplitting which is obtained from the ILU factorizations for solving a linear system whose coefficient matrix is anH-matrix. Also, parallel performance results of nonstaionary two-stage multisplitting method using ILU factorizations as inner splittings on the IBM p690 supercomputer are provided to analyze theoretical results.     

Convergence of SSOR multisplitting method for an M-matrix

In this paper, we study the convergence of both the multisplitting method and the relaxed multisplitting method associated with SOR or SSOR multisplittings for solving a linear system whose coefficient matrix is anM-matrix.     

Convergence of two-stage multisplitting method using AOR or SSOR multisplittings

In this paper, we study the convergence of two-stage multisplitting method using AOR or SSOR multisplittings as inner splittings and an outer splitting for solving a linear system whose coefficient matrix is an H-matrix. We also introduce an application of the two-stage multisplitting method.     

Modified parallel multisplitting iterative methods for non-Hermitian positive definite systems

In this paper we present three modified parallel multisplitting iterative methods for solving non-Hermitian positive definite systems Ax?=?b. The first is a direct generalization of the standard parallel multisplitting iterative method for solving this class of systems. The other two are the iterative methods obtained by optimizing the weighting matrices based on the sparsity of the coefficient matrix A. In our multisplitting there is only one that is required to be convergent (in a standard method all the splittings must be convergent), which not only decreases the difficulty of constructing the multisplitting of the coefficient matrix A, but also releases the constraints to the weighting matrices (unlike the standard methods, they are not necessarily be known or given in advance). We then prove the convergence and derive the convergent rates of the algorithms by making use of the standard quadratic optimization technique. Finally, our numerical computations indicate that the methods derived are feasible and efficient.     

Convergence of SSOR multisplitting method for an -matrix

In this paper, we study the convergence of both the multisplitting method and the relaxed multisplitting method associated with SSOR multisplitting for solving a linear system whose coefficient matrix is an H-matrix. We also introduce an application of the SSOR multisplitting method.     

Convergence analysis of the parallel multisplitting TOR method

In this paper, we propose the parallel multisplitting TOR method, for solving a large nonsingular systems of linear equations Ax = b. These new methods are a generalization and an improvement of the relaxed parallel multisplitting method (Formmer and Mager, 1989) and parallel multisplitting AOR Algorithm (Wang Deren, 1991). The convergence theorem of this new algorithm is established under the condition that the coefficient matrix A of linear systems is an H-matrix. Some results also yield new convergence theorem for TOR method.     

Two-Stage Multisplitting Iteration Methods Using Modulus-Based Matrix Splitting as Inner Iteration for Linear Complementarity Problems

The matrix multisplitting iteration method is an effective tool for solving large sparse linear complementarity problems. However, at each iteration step we have to solve a sequence of linear complementarity sub-problems exactly. In this paper, we present a two-stage multisplitting iteration method, in which the modulus-based matrix splitting iteration and its relaxed variants are employed as inner iterations to solve the linear complementarity sub-problems approximately. The convergence theorems of these two-stage multisplitting iteration methods are established. Numerical experiments show that the two-stage multisplitting relaxation methods are superior to the matrix multisplitting iteration methods in computing time, and can achieve a satisfactory parallel efficiency.     

关于线性互补问题的模系矩阵分裂迭代方法

模系矩阵分裂迭代方法是求解大型稀疏线性互补问题的有效方法之一.本文的目标是归纳总结模系矩阵分裂迭代方法的最新发展和已有成果,主要内容包括相应的多分裂迭代方法, 二级多分裂迭代方法和两步多分裂迭代方法, 以及这些方法的收敛理论.     

Inexact multisplitting methods for linear complementarity problems

We present an inexact multisplitting method for solving the linear complementarity problems, which is based on the inexact splitting method and the multisplitting method. This new method provides a specific realization for the multisplitting method and generalizes many existing matrix splitting methods for linear complementarity problems. Convergence for this new method is proved when the coefficient matrix is an _H+$H_{+}$-matrix. Then, two specific iteration forms for this inexact multisplitting method are presented, where the inner iterations are implemented either through a matrix splitting method or through a damped Newton method. Convergence properties for both these specific forms are analyzed, where the system matrix is either an _H+$H_{+}$-matrix or a symmetric matrix.     

Modified quasi-Chebyshev acceleration to nonoverlapping parallel multisplitting method

In this study, we propose a modified quasi-Chebyshev acceleration to the nonoverlopping multisplitting iteration method for solving the linear systems A x = b where A is a real symmetric positive definite matrix or an H-matrix. In the process of the parallel multisplitting method, the distributive tasks are parallelly computed by each processor, then a global modified acceleration is used to obtain the solution of the system A x = b for every τ steps, such that the efficiency of the computation can be improved. The convergence theory of the new algorithm is given under some reasonable conditions. Finally, numerical experiments show that the method is efficient and effective.     

Modulus-based synchronous two-stage multisplitting iteration methods for linear complementarity problems

In order to solve large sparse linear complementarity problems on parallel multiprocessor systems, we construct modulus-based synchronous two-stage multisplitting iteration methods based on two-stage multisplittings of the system matrices. These iteration methods include the multisplitting relaxation methods such as Jacobi, Gauss–Seidel, SOR and AOR of the modulus type as special cases. We establish the convergence theory of these modulus-based synchronous two-stage multisplitting iteration methods and their relaxed variants when the system matrix is an H _?+?-matrix. Numerical results show that in terms of computing time the modulus-based synchronous two-stage multisplitting relaxation methods are more efficient than the modulus-based synchronous multisplitting relaxation methods in actual implementations.     

对称正定线性方程组具有任意权矩阵的多分裂迭代求解

本文利用优化模型研究求解对称正定线性方程组Ax=6的多分裂并行算法的权矩阵.在我们的多分裂并行算法中,m个分裂仅要求其中之一为P-正则分裂而其余的则可以任意构造,这不仅大大降低了构造多分裂的难度,而且也放宽了对权矩阵的限制(不像标准的多分裂迭代方法中要求权矩阵为预先给定的非负数量矩阵).并且证明了新的多分裂迭代法是收敛的.最后,通过数值例子展示了新算法的有效性.     

Asynchronous Multisplitting GAOR Method and Asynchronous Multisplitting SSOR Method for Systems of Weakly Nonlinear Equations

In this article, we introduce two new asynchronous multisplitting methods for solving the system of weakly nonlinear equations Ax = G(x) in which A is an n × n real matrix and G(x) = (g ₁(x), g ₂(x), . . . , g _n (x)) ^T is a P-bounded mapping. First, by generalized accelerated overrelaxation (GAOR) technique, we introduce the asynchronous parallel multisplitting GAOR method (including the synchronous parallel multisplitting AOR method as a special case) for solving the system of weakly nonlinear equations. Second, asynchronous parallel multisplitting method based on symmetric successive overrelaxation (SSOR) multisplitting is introduced, which is called asynchronous parallel multisplitting SSOR method. Then under suitable conditions, we establish the convergence of the two introduced methods. The given results contain synchronous multisplitting iterations as a special case.     

Two-Step Modulus-Based Synchronous Multisplitting Iteration Methods for Linear Complementarity Problems

To reduce the communication among processors and improve the computing time for solving linear complementarity problems, we present a two-step modulus-based synchronous multisplitting iteration method and the corresponding symmetric modulus-based multisplitting relaxation methods. The convergence theorems are established when the system matrix is an $H_+$-matrix, which improve the existing convergence theory. Numerical results show that the symmetric modulus-based multisplitting relaxation methods are effective in actual implementation.     

On multisplitting methods for band matrices

Summary. We present new theoretical results on two classes of multisplitting methods for solving linear systems iteratively. These classes are based on overlapping blocks of the underlying coefficient matrix which is assumed to be a band matrix. We show that under suitable conditions the spectral radius of the iteration matrix does not depend on the weights of the method even if these weights are allowed to be negative. For a certain class of splittings we prove an optimality result for with respect to the weights provided that is an M–matrix. This result is based on the fact that the multisplitting method can be represented by a single splitting which in our situation surprisingly turns out to be a regular splitting. Furthermore we show by numerical examples that weighting factors may considerably improve the convergence. Received July 18, 1994 / Revised version received November 20, 1995     

Parallel multisplitting two-stage iterative methods for large sparse systems of weakly nonlinear equations

The finite difference or the finite element discretizations of many differential or integral equations often result in a class of systems of weakly nonlinear equations. In this paper, by reasonably applying both the multisplitting and the two-stage iteration techniques, and in accordance with the special properties of this system of weakly nonlinear equations, we first propose a general multisplitting two-stage iteration method through the two-stage multiple splittings of the system matrix. Then, by applying the accelerated overrelaxation (AOR) technique of the linear iterative methods, we present a multisplitting two-stage AOR method, which particularly uses the AOR-like iteration as inner iteration and is substantially a relaxed variant of the afore-presented method. These two methods have a forceful parallel computing function and are much more suitable to the high-speed multiprocessor systems. For these two classes of methods, we establish their local convergence theories, and precisely estimate their asymptotic convergence factors under some suitable assumptions when the involved nonlinear mapping is only directionally differentiable. When the system matrix is either an H-matrix or a monotone matrix, and the nonlinear mapping is a P-bounded mapping, we thoroughly set up the global convergence theories of these new methods. Moreover, under the assumptions that the system matrix is monotone and the nonlinear mapping is isotone, we discuss the monotone convergence properties of the new multisplitting two-stage iteration methods, and investigate the influence of the multiple splittings as well as the relaxation parameters upon the convergence behaviours of these methods. Numerical computations show that our new methods are feasible and efficient for parallel solving of the system of weakly nonlinear equations. This revised version was published online in August 2006 with corrections to the Cover Date.     

A class of asynchronous parallel nonlinear accelerated overrelaxation methods for the nonlinear complementarity problems

In accordance with the principle of using sufficiently the delayed information, and by making use of the nonlinear multisplitting and the nonlinear relaxation techniques, we present in this paper a class of asynchronous parallel nonlinear multisplitting accelerated overrelaxation (AOR) methods for solving the large sparse nonlinear complementarity problems on the high-speed MIMD multiprocessor systems. These new methods, in particular, include the so-called asynchronous parallel nonlinear multisplitting AOR-Newton method, the asynchronous parallel nonlinear multisplitting AOR-chord method and the asynchronous parallel nonlinear multisplitting AOR-Steffensen method. Under suitable constraints on the nonlinear multisplitting and the relaxation parameters, we establish the local convergence theory of this class of new methods when the Jacobi matrix of the involved nonlinear mapping at the solution point of the nonlinear complementarity problem is an H-matrix.     

PARALLEL CHAOTIC MULTISPLITTING ITERATIVE METHODS FOR THE LARGE SPARSE LINEAR COMPLEMENTARITY PROBLEM

1. IntroductionWe consider the linear complementarity problem LCP(M,q): Find a z E m such thatwhere M = (mij) E boxs and q ~ (qi) 6 m are given real matriX and vector, respectively.This problem axises in various scientific computing areas such as the Nash equilibritun poillt ofa bimatrir game (e.g., Cottle and Dantzig[4] and Lelnke[12j) and the free boundary problems offluid mechedcs (e.g., Cryer[8]). There have been a lot of researches on the approximate solutionof the linear complemeat…     

Convergence of nonstationary multisplitting methods using ILU factorizations

In this paper, we first study convergence of nonstationary multisplitting methods associated with a multisplitting which is obtained from the ILU factorizations for solving a linear system whose coefficient matrix is a large sparse H-matrix. We next study a parallel implementation of the relaxed nonstationary two-stage multisplitting method (called Algorithm 2 in this paper) using ILU factorizations as inner splittings and an application of Algorithm 2 to parallel preconditioner of Krylov subspace methods. Lastly, we provide parallel performance results of both Algorithm 2 using ILU factorizations as inner splittings and the BiCGSTAB with a parallel preconditioner which is derived from Algorithm 2 on the IBM p690 supercomputer.     

On M–multisplittings of singular M–matrices with application to Markov chains

Given a singular M–matrix of a linear system, convergent conditions under which iterative schemes based on M–multisplittings are studied. Two of those conditions, the index of the iteration matrix and its spectral radius are investigated and related to those of the M-matrix. Furthermore, a parallel multisplitting iteration scheme for solving singular linear systems is suggested which can be applied to practical problems such as Poisson and elasticity problems under certain boundary conditions, the Neumann problem, and in Markov chains. A discussion of that multisplitting scheme, based on Gauss–Seidel type splittings is given for computing the stationary distribution vector of Markov chains. In this case a computational viable algorithm can be constructed, since only the nonsingularity of one weighting matrix of the multisplitting is needed. © 1998 John Wiley & Sons, Ltd.