A class of two‐stage iterative methods for systems of weakly nonlinear equations

The discretizations of many differential equations by the finite difference or the finite element methods can often result in a class of system of weakly nonlinear equations. In this paper, by applying the two-tage iteration technique and in accordance with the special properties of this weakly nonlinear system, we first propose a general two-tage iterative method through the two-tage splitting of the system matrix. Then, by applying the accelerated overrelaxation (AOR) technique of the linear iterative methods, we present a two-tage AOR method, which particularly uses the AOR iteration as the inner iteration and is substantially a relaxed variant of the afore-presented method. 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 B-differentiable. When the system matrix is either a monotone matrix or an H-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 two-tage iteration methods, and investigate the influence of the matrix splittings as well as the relaxation parameters on the convergence behaviours of these methods. Numerical computations show that our new methods are feasible and efficient for solving the system of weakly nonlinear equations. This revised version was published online in June 2006 with corrections to the Cover Date.     

Asynchronous multisplitting two-stage iterations for systems of weakly nonlinear equations

For the large sparse systems of weakly nonlinear equations arising in the discretizations of many classical differential and integral equations, this paper presents a class of asynchronous parallel multisplitting two-stage iteration methods for getting their solutions by the high-speed multiprocessor systems. Under suitable assumptions, we study the global convergence properties of these asynchronous multisplitting two-stage iteration methods. Moreover, for this class of new methods, we establish their local convergence theories, and precisely estimate their asymptotic convergence factors under some reasonable assumptions when the involved nonlinear mapping is only assumed to be directionally differentiable. Numerical computations show that our new methods are feasible and efficient for parallely solving the system of weakly nonlinear equations.     

A class of asynchronous multisplitting two-stage iterations for large sparse block systems of weakly nonlinear equations

For the block system of weakly nonlinear equations Ax=G(x), where is a large sparse block matrix and is a block nonlinear mapping having certain smoothness properties, we present a class of asynchronous parallel multisplitting block two-stage iteration methods in this paper. These methods are actually the block variants and generalizations of the asynchronous multisplitting two-stage iteration methods studied by Bai and Huang (Journal of Computational and Applied Mathematics 93(1) (1998) 13–33), and they can achieve high parallel efficiency of the multiprocessor system, especially, when there is load imbalance. Under quite general conditions that is a block H-matrix of different types and is a block P-bounded mapping, we establish convergence theories of these asynchronous multisplitting block two-stage iteration methods. Numerical computations show that these new methods are very efficient for solving the block system of weakly nonlinear equations in the asynchronous parallel computing environment.     

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 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.     

ON MONOTONE CONVERGENCE OF NONLINEARMULTISPLITTING RELAXATION METHODS

ＯＮＭＯＮＯＴＯＮＥＣＯＮＶＥＲＧＥＮＣＥＯＦＮＯＮＬＩＮＥＡＲＭＵＬＴＩＳＰＬＩＴＴＩＮＧＲＥＬＡＸＡＴＩＯＮＭＥＴＨＯＤＳ￥ＷＡＮＧＤＥＲＥＮ；ＢＡＩＺＨＯＮＧＺＨＩ（ＤｅｐａｚａｔｍｅｎｔｏｆＭａｔｈｅｍａｔｉｃｓ，ＳｈｓｌｌｇｈａｉＵｎｉｖｅ...     

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

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

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.     

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.     

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.     

Comparison theorems for splittings of matrices

Summary. This paper investigates the comparisons of asymptotic rates of convergence of two iteration matrices. On the basis of nonnegative matrix theory, comparisons between two nonnegative splittings and between two parallel multisplitting methods are derived. When the coefficient matrix A is Hermitian positive (semi)definite, comparison theorems about two P-regular splittings and two parallel multisplitting methods are proved. Received April 4, 1998 / Revised version received October 18, 1999 / Published online November 15, 2001     

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.     

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.     

M-矩阵线性互补问题模系多分裂迭代方法的收敛性

首先证明了M-矩阵的H-相容分裂都是正则分裂,反之不成立.这表明对于M-矩阵而言,其正则分裂包含H-相容分裂.然后针对系数矩阵为M-矩阵的线性互补问题,建立了两个收敛定理:一是模系多分裂迭代方法关于正则分裂的收敛定理;二是模系二级多分裂迭代方法关于外迭代为正则分裂和内迭代为弱正则分裂的收敛定理.     

Models of Asynchronous Parallel Nonlinear Multisplitting Relaxed Iterations

In the sense of the nonlinear multisplitting and based on the principle of sufficiently using the delayed information, we propose models of asynchronous parallel accelerated overrelaxation iteration methods for solving large scale system of nonlinear equations. Under proper conditions, we set up the local convergence theories of these new method models.     

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 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.     

并行区间矩阵多分裂AOR算法及其收敛性

本文提出了一类求解大型区间线性方程组的并行区间矩阵多分裂松弛算法,并在系数矩阵是区间H-矩阵的条件下,建立了这类算法的收敛理论。     

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 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