Improved convergence theorems of modulus-based matrix splitting iteration methods for linear complementarity problems

We weaken the convergence conditions of modulus-based matrix splitting and matrix two-stage splitting iteration methods for linear complementarity problems. Thus their applied scopes are further extended.     

A CLASS OF GENERALIZED MULTISPLITTING RELAXATION METHODS FOR LINEAR COMPLEMENTARITY PROBLEMS

In this paper,a class of generalized parallel matrix multisplitting relaxation methods for solving linear complementarity problems on the high-speed multiprocessor systems is set up. This class of methods not only includes all the existing relaxation methods for the linear complementarity problems ,but also yields a lot of novel ones in the sense of multisplittlng. We establish the convergence theories of this class of generalized parallel multisplitting relaxation methods under the condition that the system matrix is an H-metrix with positive diagonal elements.     

IGAOR and multisplitting IGAOR methods for linear complementarity problems

In this paper, we propose an interval version of the generalized accelerated overrelaxation methods, which we refer to as IGAOR, for solving the linear complementarity problems, LCP (M, q), and develop a class of multisplitting IGAOR methods which can be easily implemented in parallel. In addition, in regards to the H-matrix with positive diagonal elements, we prove the convergence of these algorithms and illustrate their efficiency through our numerical results.     

A two-step modulus-based matrix splitting iteration method for horizontal linear complementarity problems

Numerical Algorithms - In this paper, for solving horizontal linear complementarity problems, a two-step modulus-based matrix splitting iteration method is established. The convergence analysis of...     

The modulus-based matrix splitting iteration methods for second-order cone linear complementarity problems

This paper presents a new computational technique for solving fractional pantograph differential equations. The fractional derivative is described in the Caputo sense. The main idea is to use Müntz-Legendre wavelet and its operational matrix of fractional-order integration. First, the Müntz-Legendre wavelet is presented. Then a family of piecewise functions is proposed, based on which the fractional order integration of the Müntz-Legendre wavelets are easy to calculate. The proposed approach is used this operational matrix with the collocation points to reduce the under study problem to a system of algebraic equations. An estimation of the error is given in the sense of Sobolev norms. The efficiency and accuracy of the proposed method are illustrated by several numerical examples.     

Accelerated modulus-based matrix splitting iteration methods for linear complementarity problem

For the large sparse linear complementarity problem, a class of accelerated modulus-based matrix splitting iteration methods is established by reformulating it as a general implicit fixed-point equation, which covers the known modulus-based matrix splitting iteration methods. The convergence conditions are presented when the system matrix is either a positive definite matrix or an H ₊-matrix. Numerical experiments further show that the proposed methods are efficient and accelerate the convergence performance of the modulus-based matrix splitting iteration methods with less iteration steps and CPU time.     

Two-step modulus-based matrix splitting iteration method for linear complementarity problems

Bai has recently presented a modulus-based matrix splitting iteration method, which is a powerful alternative for solving the large sparse linear complementarity problems. In this paper, we further present a two-step modulus-based matrix splitting iteration method, which consists of a forward and a backward sweep. Its convergence theory is proved when the system matrix is an H ₊-matrix. Moreover, for the two-step modulus-based relaxation iteration methods, more exact convergence domains are obtained without restriction on the Jacobi matrix associated with the system matrix, which improve the existing convergence theory. Numerical results show that the two-step modulus-based relaxation iteration methods are superior to the modulus-based relaxation iteration methods for solving the large sparse linear complementarity problems.     

Two-step modulus-based matrix splitting iteration methods for implicit complementarity problems

Numerical Algorithms - In this paper, a class of two-step modulus-based matrix splitting (TMMS) iteration methods are proposed to solve the implicit complementarity problems. It is proved that the...     

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.     

A modified modulus-based matrix splitting iteration method for solving implicit complementarity problems

In this paper, a modified modulus-based matrix splitting iteration method is established for solving a class of implicit complementarity problems. The global convergence conditions are given when the system matrix is a positive definite matrix or an H₊-matrix, respectively. In addition, some numerical examples show that the proposed method is efficient.

     

A generalized variant of two-sweep modulus-based matrix splitting iteration method for solving horizontal linear complementarity problems

Numerical Algorithms - Based on the two-sweep modulus-based matrix splitting iteration (TMMS) method for linear complementarity problems developed by Wu and Li (Comput. Appl. Math. 302:...     

A preconditioned general two-step modulus-based matrix splitting iteration method for linear complementarity problems of H+-matrices

Numerical Algorithms - In this paper, we present a preconditioned general two-step modulus-based iteration method to solve a class of linear complementarity problems. Its convergence theory is...     

Two class of synchronous matrix multisplitting schemes for solving linear complementarity problems

Many problems in the areas of scientific computing and engineering applications can lead to the solution of the linear complementarity problem LCP (M,q). It is well known that the matrix multisplitting methods have been found very useful for solving LCP (M,q). In this article, by applying the generalized accelerated overrelaxation (GAOR) and the symmetric successive overrelaxation (SSOR) techniques, we introduce two class of synchronous matrix multisplitting methods to solve LCP (M,q). Convergence results for these two methods are presented when M is an H-matrix (and also an M-matrix). Also the monotone convergence of the new methods is established. Finally, the numerical results show that the introduced methods are effective for solving the large and sparse linear complementary problems.     

Accelerated modulus-based matrix splitting iteration methods for a restricted class of nonlinear complementarity problems

To solve a class of nonlinear complementarity problems, accelerated modulus-based matrix splitting iteration methods are presented and analyzed. Convergence analysis and the choice of the parameters are given when the system matrix is either positive definite or an H ₊-matrix. Numerical experiments further demonstrate that the proposed methods are efficient and have better performance than the existing modulus-based iteration method in aspects of the number of iteration steps and CPU time.     

New multiplier method for solving linear complementarity problems

A new multiplier method for solving the linear complementarity problem LCP(q, M) is proposed. By introducing a Lagrangian of LCP(q, M), a new smooth merit function ϑ(x, λ) for LCP(q, M) is constructed. Based on it, a simple damped Newton-type algorithm with multiplier self-adjusting step is presented. When M is a P-matrix, the sequence {ϑ(x ^k, λ ^k)} (where {(x ^k, λ ^k)} is generated by the algorithm) is globally linearly convergent to zero and convergent in a finite number of iterations if the solution is degenerate. Numerical results suggest that the method is highly efficient and promising. Selected from Numerical Mathematics (A Journal of Chinese Universities), 2004, 26(2): 162–171     

ON THE CONVERGENCE DOMAIN OF THEMATRIX MULTISPLITTING RELAXATION METHODS FOR LINEAR SYSTEMS

The convergence of the parallel matrix multisplitting relaxation methods presented by Wang (Linear Algebra and Its Applications 154/156 (1991) 473-486) is further investigated.The investigations show that these relaxation methods really have considerably larger convergence domains.     

非对称线性互补问题的并行二级多分裂迭代法

提出了求解非对称线性互补问题的并行二级多分裂迭代算法,并证明了该算法的收敛性,最后通过数值实验验证了算法的有效性和可行性.     

Smoothing methods for convex inequalities and linear complementarity problems

A smooth approximationp (x, ) to the plus function max{x, 0} is obtained by integrating the sigmoid function 1/(1 + e^–x ), commonly used in neural networks. By means of this approximation, linear and convex inequalities are converted into smooth, convex unconstrained minimization problems, the solution of which approximates the solution of the original problem to a high degree of accuracy for sufficiently large. In the special case when a Slater constraint qualification is satisfied, an exact solution can be obtained for finite. Speedup over MINOS 5.4 was as high as 1142 times for linear inequalities of size 2000 × 1000, and 580 times for convex inequalities with 400 variables. Linear complementarity problems are converted into a system of smooth nonlinear equations and are solved by a quadratically convergent Newton method. For monotone LCPs with as many as 10 000 variables, the proposed approach was as much as 63 times faster than Lemke's method.This material is based on research supported by Air Force Office of Scientific Research Grant F49620-94-1-0036 and National Science Foundation Grants CCR-9101801 and CCR-9322479.