The monotone convergence of a class of parallel nonlinear relaxation methods for nonlinear complementarity problems

We set up a class of parallel nonlinear multisplitting AOR methods by directly multisplitting the nonlinear mapping involved in the nonlinear complementarity problems. The different choices of the relaxation parameters can yield all the known and a lot of new relaxation methods, as well as a lot of new relaxed parallel nonlinear multisplitting methods for solving the nonlinear complementarity problems. The two-sided approximation properties and the influences on the convergence rates from the relaxation parameters about our new methods are shown, and sufficient conditions guaranteeing the methods to converge globally are discussed. Finally, a lot of numerical results show that our new methods are feasible and efficient.     

A multiplicative multisplitting method for solving the linear complementarity problem

The convergence of the multiplicative multisplitting-type method for solving the linear complementarity problem with an H-matrix is discussed using classical and new results from the theory of splitting. This directly results in a sufficient condition for guaranteeing the convergence of the multiplicative multisplitting method. Moreover, the multiplicative multisplitting method is applied to the H-compatible splitting and the multiplicative Schwarz method, separately. Finally, we establish the monotone convergence of the multiplicative multisplitting method under appropriate conditions.     

Relaxed parallel two-stage multisplitting methods II: Asynchronous version

Two classes of asynchronous relaxed parallel two-stage multisplitting methods based on extrapolated and AOR methods are studied for the solution of nonsingular linear systems, which are called asynchronous outer relaxed or inner relaxed parallel two-stage multisplitting methods. Convergence of these methods is studied for H-matrix. Almost all methods seen in literatures can be viewed as special cases of our methods.     

A unified framework for the construction of various matrix multisplitting iterative methods for large sparse system of linear equations

A unified framework for the construction of various synchronous and asynchronous parallel matrix multisplitting iterative methods, suitable to the SIMD and MIMD multiprocessor systems, respectively, is presented, and its convergence theory is established under rather weak conditions. These afford general method models and systematical convergence criterions for studying the parallel iterations in the sense of matrix multisplitting. In addition, how the known parallel matrix multisplitting iterative methods can be classified into this new framework, and what novel ones can be generated by it are shown in detail.     

Relaxed parallel two-stage multisplitting methods ∗

Two classes of relaxed parallel two-stage multisplitting methods based on extrapolated and AOR methods are studied for the solution of nonsingular linear systems, which are called outer relaxed or inner relaxed parallel two-stage multisplitting methods. Convergence of these methods is studied for H-matrix. Furthermore, computational results about these methods on a shared memory multiprocessor are presented. The results show that the methods we proposed are better than the corresponding existed parallel (two-stage) multisplitting methods.     

A note on parallel multisplitting TOR method for H-matrices

In 2001, Chang studied the convergence of parallel multisplitting TOR method for H-matrices [D.W. Chang, The parallel multisplitting TOR(MTOR) method for linear systems, Comput. Math. Appl. 41 (2001), pp. 215–227]. In this paper, we point out some gaps in the proof of Chang's main results solving them. Moreover, we improve some of Chang's convergence results. A numerical example is presented in order to illustrate the improvement of Chang's convergence region.     

Convergence of parallel block SSOR multisplitting method for block H-matrix

In this paper we investigate block SSOR multisplittings. When the coefficient matrix is a block H-matrix or a (generalized) block strictly diagonally dominant matrix, the convergence of the parallel block SSOR multisplitting method for solving nonsingular linear systems is proved. Two numerical examples are given to illustrate the theoretical results.     

非线性互补问题的多分裂加性Schwarz迭代算法

§1.引言 非线性互补问题在科学与工程中有着广泛的应用,因此研究求解非线性互补问题的高效数值算法是非常必要的。迄今为止,人们已给出了许多各种各样的Schwarz迭代算法用来求解变分不等式和互补问题。这些方法都适合并行计算,而且计算效果也不错。     

The accelerated overrelaxation quadrant interlocking iterative method

In this paper we use a new splitting of the matrix A of the linear system A x = b introduced in [1] and we present a new version of the AOR method, more suitable for parallel processing, which involves explicit evaluation of 2 × 2 blocks.

We also obtain several convergence conditions for this new method, when the matrix A of (1.1) belongs to different classes of matrices. Some results, given in [1], are also improved and generalised.     

Comparison results on the preconditioned GAOR method for generalized least squares problems

Recently, Zhou et al. [Preconditioned GAOR methods for solving weighted linear least squares problems, J. Comput. Appl. Math. 224 (2009), pp. 242–249] have proposed the preconditioned generalized accelerated over relaxation (GAOR) methods for solving generalized least squares problems and studied their convergence rates. In this paper, we propose a new type of preconditioners and study the convergence rates of the new preconditioned GAOR methods for solving generalized least squares problems. Comparison results show that the convergence rates of the new preconditioned GAOR methods are better than those of the preconditioned GAOR methods presented by Zhou et al. whenever these methods are convergent. Lastly, numerical experiments are provided in order to confirm the theoretical results studied in this paper.     

Convergence of the interval and point TOR method

In this paper, we present the interval version of the two parameter overrelaxation iterative (TOR) method and we obtain some convergence conditions when the matrix A of the linear system Ax?=?b belongs to some classes of matrice. Similar conditions were obtained for the point TOR method.

Some results for the accelerated overrelaxation interval and point iterative (AOR) method were also obtained, which coincides with those given by Martins in Ref. [7].     

An affine scaling interior trust-region method combining with nonmonotone line search filter technique for linear inequality constrained minimization

This paper proposes an affine scaling interior trust-region method in association with nonmonotone line search filter technique for solving nonlinear optimization problems subject to linear inequality constraints. Based on a Newton step which is derived from the complementarity conditions of linear inequality constrained optimization, a trust-region subproblem subject only to an ellipsoidal constraint is defined by minimizing a quadratic model with an appropriate quadratic function and scaling matrix. The nonmonotone schemes combining with trust-region strategy and line search filter technique can bring about speeding up the convergence progress in the case of high nonlinear. A new backtracking relevance condition is given which assures global convergence without using the switching condition used in the traditional line search filter technique. The fast local convergence rate of the proposed algorithm is achieved which is not depending on any external restoration procedure. The preliminary numerical experiments are reported to show effectiveness of the proposed algorithm.     

An asynchronous parallel mixed algorithm for linear and nonlinear equations

In this paper we propose an asynchronous parallel mixed algorithm for solving linear and nonlinear equations. This algorithm can be used not only on serial and parallel computers, but also on MIMD multiprocessor systems. The convergence of the algorithm has been proved under certain conditions. This paper gives some special cases of the algorithm which are known to us as efficient iterative methods. Numerical experiments are given to illustrate the method.     

Convergence analysis of the two-stage¶multisplitting method

An example is given which shows that the asymptotic convergence rate of the two-stage multisplitting method (see D.B. Szyld and M.T. Jones, SIAM J. Matrix Anal. Appl. 13, 671–679 (1992)) with one inner iteration is, generally, either faster or slower than that with many inner iterations. When the coefficient matrix is an H-matrix and a monotone matrix, respectively, we formulate the convergence as well as the monotone convergence theories for this two-stage multisplitting method under suitable constraints on the two-stage multisplitting. Furthermore, the corresponding comparison theorem in the sense of monotonicity for this method is established and several concrete applications are discussed. Received: April 1996 / Accepted: April 1998     

Synchronous and Asynchronous Interval Newton-Schwarz Methods for a Class of Large Systems of Nonlinear Equations

We introduce a class of parallel interval arithmetic iteration methods for nonlinear systems of equations, especially of the type Ax+(x) = f, diagonal, in R ^N . These methods combine enclosure and global convergence properties of Newton-like interval methods with the computational efficiency of parallel block iteration methods: algebraic forms of Schwarz-type methods which generalize both the well-known additive algebraic Schwarz Alternating Procedure and multisplitting methods. We discuss both synchronous and asynchronous variants. Besides enclosure and convergence properties, we present numerical results from a CRAY T3E.     

On the convergence of subproper (multi)-splitting methods for solving rectangular linear systems

Abstract We give a convergence criterion for stationary iterative schemes based on subproper splittings for solving rectangular systems and show that, for special splittings, convergence and quotient convergence are equivalent. We also analyze the convergence of multisplitting algorithms for the solution of rectangular systems when the coefficient matrices have special properties and the linear systems are consistent. Keywords: Rectangular linear system, iterative method, proper splitting, subproper splitting, regularity, Hermitian positive semi-definite matrix, multi-splitting, quotient convergence AMS Subject Classification: 65F10, 65F15     

严格对角占优Z-矩阵的多级预条件AOR迭代法

为了加快线性方程组的迭代法求解速度,提出了一类新预条件子,分析了相应的预条件AOR迭代法的收敛性。给出了当系数矩阵为严格对角占优的Z-矩阵时,AOR和预条件AOR迭代法收敛速度的比较结论。同时也给出了多级预条件迭代法的相关比较结果,推广了现有的结论。数值算例验证了文中结果。     

A monotone Newton multisplitting method for the nonlinear complementarity problem with a nonlinear source term

In this paper, we develop a Newton multisplitting method for the nonlinear complementarity problem with a nonlinear source term in which the multisplitting method is used as secondary iterations to approximate the solutions for the resulting linearized subproblems. We prove the monotone convergence theorem for the proposed method under proper conditions.     

无约束最优化问题的BFGS松弛异步并行算法

为解决大规模非线性最优化问题的串行求解速度慢的问题,提出应用松弛异步并行算法求解无约束最优化问题。根据无约束最优化问题的BFGS串行算法,在PC机群环境下将其并行化。利用CHOLESKY方法分解系数为对称正定矩阵的线性方程组,运用无序松弛异步并行方法求解解向量和Wolfe-Powell非线性搜索步长,并行求解BFGS修正公式,构建BFGS松弛异步并行算法,并对算法的时间复杂性、加速比进行分析。在PC机群的实验结果表明,该算法提高了无约束最优化问题的求解速度且负载均衡,算法具有线性加速比。     

Learning and convergence analysis of neural-type structurednetworks

A class of feedforward neural networks, structured networks, has recently been introduced as a method for solving matrix algebra problems in an inherently parallel formulation. A convergence analysis for the training of structured networks is presented. Since the learning techniques used in structured networks are also employed in the training of neural networks, the issue of convergence is discussed not only from a numerical algebra perspective but also as a means of deriving insight into connectionist learning. Bounds on the learning rate are developed under which exponential convergence of the weights to their correct values is proved for a class of matrix algebra problems that includes linear equation solving, matrix inversion, and Lyapunov equation solving. For a special class of problems, the orthogonalized back-propagation algorithm, an optimal recursive update law for minimizing a least-squares cost functional, is introduced. It guarantees exact convergence in one epoch. Several learning issues are investigated.