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.     

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

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

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.     

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.     

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.     

Multisplitting preconditioners for a symmetric positive definite matrix

We study convergence of multisplitting method associated with a block diagonal conformable multisplitting for solving a linear system whose coefficient matrix is a symmetric positive definite matrix which is not an H-matrix. Next, we study the validity ofm-step multisplitting polynomial preconditioners which will be used in the preconditioned conjugate gradient 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.     

Parallel multisplitting two-stage iterative methods with general weighting matrices for non-symmetric positive definite systems

In this work, we propose a new parallel multisplitting iterative method for non-symmetric positive definite linear systems. Based on optimization theory, the new method has two great improvements; one is that only one splitting needs to be convergent, and the other is that the weighting matrices are not scalar and nonnegative matrices. The convergence of the new parallel multisplitting iterative method is discussed. Finally, the numerical results show that the new method is effective.     

Modulus‐based synchronous multisplitting iteration methods for linear complementarity problems

By an equivalent reformulation of the linear complementarity problem into a system of fixed‐point equations, we construct modulus‐based synchronous multisplitting iteration methods based on multiple splittings of the system matrix. These iteration methods are suitable to high‐speed parallel multiprocessor systems and include the multisplitting relaxation methods such as Jacobi, Gauss–Seidel, successive overrelaxation, and accelerated overrelaxation of the modulus type as special cases. We establish the convergence theory of these modulus‐based synchronous multisplitting iteration methods and their relaxed variants when the system matrix is an H ₊ ‐matrix. Numerical results show that these new iteration methods can achieve high parallel computational efficiency in actual implementations. Copyright © 2012 John Wiley & Sons, Ltd.     

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

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

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.     

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.     

A comparison result for multisplittings and waveform relaxation methods

We show that certain multisplitting iterative methods based on overlapping blocks yield faster convergence than corresponding nonoverlapping block iterations, provided the coefficient matrix is an M-matrix. This result can be used to compare variants of the waveform relaxation algorithm for solving initial value problems. The methods under consideration use the same discretization technique, but are based on multisplittings with different overlaps. Numerical experiments on the Intel iPSC/860 hypercube are included.     

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.     

A two-step modulus-based multisplitting iteration method for the nonlinear complementarity problem

In this paper, we construct a two-step modulus-based multisplitting iteration method based on multiple splittings of the system matrix for the nonlinear complementarity problem. And we prove its convergence when the system matrix is an $H$-matrix with positive diagonal elements. Numerical experiments show that the proposed method is efficient.     

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.     

Discretized Multisplitting AOR Waveform Relaxation Algorithms for Initial Value Problem of Systems of ODEs

1.IntroductionInthedevelopmentofnewelectricalcircuits,thesimulationofthebehaviourofthecircuithasbecomeanessentialtoolforelectricalengineers.Fromthelayoutofthecircuitanonlinearsystemofordinarydifferentialequationsisgeneratedwhichdescribesthedynamicalbehaviourofthecircuit.Inthesimulationofverylargescaleintegrated(VLSI)circuitsthedimensionofthesystemofODEscanbecomeverylarge.Moreoversincethesystemisstiff,solvingthesesystemsisaverycomputionallyintensivetaskandtheuseofsupercomputersbecomesin-evit…     

Parallel nonlinear multisplitting methods

Summary Linear multisplitting methods are known as parallel iterative methods for solving a linear systemAx=b. We extend the idea of multisplittings to the problem of solving a nonlinear system of equationsF(x)=0. Our nonlinear multisplittings are based on several nonlinear splittings of the functionF. In a parallel computing environment, each processor would have to calculate the exact solution of an individual nonlinear system belonging to his nonlinear multisplitting and these solutions are combined to yield the next iterate. Although the individual systems are usually much less involved than the original system, the exact solutions will in general not be available. Therefore, we consider important variants where the exact solutions of the individual systems are approximated by some standard method such as Newton's method. Several methods proposed in literature may be regarded as special nonlinear multisplitting methods. As an application of our systematic approach we present a local convergence analysis of the nonlinear multisplitting methods and their variants. One result is that the local convergence of these methods is determined by an induced linear multisplitting of the Jacobian ofF.Dedicated to the memory of Peter Henrici     

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.     

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…