New Accelerated Modulus-Based Iteration Method
for Solving Large and Sparse
Linear Complementarity Problem

Abstract.

For the large and sparse linear complementarity problem, we provide a family of new accelerated modulus-based iteration methods in this article. We provide some sufficient criteria for the convergence analysis when the system matrix is a $P$-matrix or an $H_{+}$-matrix. In addition, we provide some numerical examples of the different parameters to illustrate the efficacy of our proposed methods. These methods help us reduce the number of iterations and the time required by the CPU, which improves convergence performance.

1. Introduction

The large and sparse matrices are matrices that have a large number of rows and columns but a small number of non-zero elements. In other words, they are matrices where the majority of the elements are zero. Sparse matrices are commonly used to represent complex systems or large datasets in fields such as computer science, mathematics, physics and engineering. The sparsity of the matrix means that it is not practical to store each element individually and specialized data structures and algorithms must be used to efficiently store and manipulate the matrix.

Let us assume that the matrix $𝒜\in {ℝ}^{n\times n}$ is large and sparse and that it is associated with the vector $\sigma \in {ℝ}^n$. The objective of the linear complementarity problem, referred to as LCP$(\sigma ,𝒜)$, is to determine the solution $\lambda \in {ℝ}^n$ to the following system:

(1) $\lambda \ge 0,\omega =𝒜\lambda +\sigma \ge 0,{\lambda }^T(𝒜\lambda +\sigma )=0.$

Applications of the linear complementarity problem that have received significant study in the literature on mathematical programming include the free boundary problem, the Nash equilibrium point of the bimatrix game, operations research, control theory, mathematical economics, optimization theory, stochastic optimal control, and the American option pricing problem.

The methods available for solving the linear complementarity problems are into two groups namely the pivotal method [26], [18] and the iterative method [12], [4], [7] and [8]. The objective behind the iterative method is to produce a sequence of iterates that lead to a solution, but the pivotal method develops a series of pivot steps that lead to a basic feasible complementary vector through a series of pivot steps.

Reformulating the LCP$(\sigma ,𝒜)$ into an equation whose solution must be the same as the LCP $(\sigma ,𝒜)$ is one of the most well-known and attractive methods of constructing fast and inexpensive iteration methods. Consequently, certain useful LCP$(\sigma ,𝒜)$ equivalent forms have arisen. Mangasarian [22] presented three methods: projected Jacobi over-relaxation, projected SOR and projected symmetric SOR. For additional details regarding developing iteration methods based on Mangasarian’s notion, see also [6], [35] and [10]. Bai has offered the following equivalent form in [34]:

(2) $$({\mathrm{\Theta }}_1+ℳ)\varkappa =𝒩\varkappa +({\mathrm{\Theta }}_1-𝒜)|\varkappa |-r\sigma ,$$

where $r>0$ and ${\mathrm{\Theta }}_1\in {ℝ}^{n\times n}$ is a positive diagonal matrix and developed a class of modulus-based matrix splitting iteration methods. The Equation (2) covers the published works in [2], [28], [20], [13] and [5]. This kind of modulus-based matrix splitting iteration method has been considered efficient for solving the LCP$(\sigma ,𝒜)$. For other formulations of Equation (2), see [21], [16], [29], [31] and [17] for more details. Furthermore, this concept has been successfully applied to other complementarity problems, including the horizontal linear complementarity problem [11], the implicit complementarity problem [19], the nonlinear complementarity problem [9] and [33], [14] and the quasi-complementarity problem [27].

Bai [34] solved linear complementarity problems using modulus-based matrix splitting methods. However, the number of iterations in these methods is large enough to accomplish the optimal approximate solution to the numerical instances. In this paper, we introduce a class of new accelerated modulus-based iteration techniques for solving the large and sparse LCP$(\sigma ,𝒜)$. These methods are based on the work of Shilang [30] and Bai [34]. We demonstrate that the linear complementarity problem and the fixed point equation are equivalent and both have the same solution. In addition, we present several convergence conditions for the method that we proposed.

The article is structured as follows: In Section 2, we provide necessary definitions, notations and well-known lemmas. All of these things will be used in the discussions in the subsequent sections of this work. A new accelerated modulus-based iteration method is presented in Section 3 and it makes use of the new equivalent fixed point form of the LCP$(\sigma ,𝒜)$. In Section 4, we define certain convergence domains for the proposed approach. Section 5 gives some examples of the numerical comparison that is made between the methods that have been suggested and the modulus-based matrix splitting methods that were presented by Bai [34]. Section 6 provides the conclusion.

2. Preliminaries

In this section, we introduce some basic notations, definitions and lemmas, most of which may be found in [32], [3], [25], that will be used throughout the article to examine the convergence analysis of the proposed methods.

The following is a list of related notations that are used for a given large and sparse matrix $𝒜$:

• Let $𝒜=(a_{ij})\in {ℝ}^{n\times n}$ and $ℬ=(b_{ij})\in {ℝ}^{n\times n}$. We use $𝒜>$ $(\ge )$ $ℬ$ to denotes $a_{ij}>(\ge )$ $b_{ij}$, $\forall$ $1\le i,j\le n$;

• ${(\star )}^T$ denotes the transpose of the given matrix or vector;

• We use $𝒜=0\in {ℝ}^{n\times n}$ to denotes $a_{ij}=0,\forall i,j$;

• $|𝒜|=(|a_{ij}|)$, $\forall i,j$;

• ${𝒜}^{-1}$ represents the inverse of the matrix $𝒜$;

• ${\mathrm{\Theta }}_1$ is a real positive diagonal matrix of order $n$;

• $\parallel \star {\parallel }_2$ is euclidean norm of a vector i.e. let $x=(x_i)\in {ℝ}^n,$ then ${\Vert x\Vert }_2=\sqrt{{\sum }_{i=1}^n{x}_i^2}$;

• Let $x,y\in {ℝ}^n,$ $\min (x,y)$ is the vector whose $i^{th}$ component is
  $\min (x_i,y_i)$;

• Assume $𝒜=𝒟-ℒ-𝒰$ where $𝒟=\mathrm{diag}(𝒜)$ and $ℒ$, $𝒰$ are the strictly lower, upper triangular matrices of $𝒜$, respectively.

Let $𝒜=(a_{ij})\in {ℝ}^{n\times n}$ and $ℬ=(b_{ij})\in {ℝ}^{n\times n}$ be square matrices. The comparison matrix of $𝒜$ is defined as $⟨a_{ij}⟩=|a_{ij}|$ if $i=j$ and $⟨a_{ij}⟩=-|a_{ij}|$ if $i\ne j$; a $Z$-matrix if all of its non-diagonal elements are less than equal to zero; an $M$-matrix if ${𝒜}^{-1}\ge 0$ as well as $Z$-matrix; an $H$-matrix, if $⟨𝒜⟩$ is an $M$-matrix and an $H_{+}$-matrix if $𝒜$ is an $H$-matrix as well as $a_{ii}>0\forall i\in \{1,2,\mathrm{\dots },n\}$; a $P$-matrix if all its principle minors are positive such that $det({𝒜}_{{\alpha }_1{\alpha }_1})>0$ $\forall$ ${\alpha }_1\subseteq \{1,2,\mathrm{\dots },n\}$. The splitting $𝒜=ℳ-𝒩$ is called an $M$-splitting if $ℳ$ is a nonsingular $M$-matrix and $𝒩\ge 0$; an $H$-splitting if $⟨ℳ⟩-|𝒩|$ is an $M$-matrix; an $H$-compatible splitting if $⟨𝒜⟩=⟨ℳ⟩-|𝒩|$.

Lemma 1 ([23]).

Let $x,y\in {ℝ}^n$. $x\ge 0$, $y\ge 0$, $x^{T}y=0$ if and only if $x+y=|x-y|$.

Lemma 2 ([3]).

Let $𝒜,ℬ\in {ℝ}^{n\times n}$. If $𝒜$ and $ℬ$ are $M$ and $Z$-matrices, respectively, with $𝒜\le ℬ$ then $ℬ$ is an $M$-matrix. If $𝒜$ is an $H$-matrix then $|{𝒜}^{-1}|\le {⟨𝒜⟩}^{-1}$.

Lemma 3 ([32]).

Let $𝒜\in {ℝ}^{n\times n}$ be an $M$-matrix and $𝒜=ℳ-𝒩$ be an $M$-splitting, then  $\rho ({ℳ}^{-1}𝒩)$ $<$ $1$.

Lemma 4 ([3]).

Suppose $𝒜\ge 0\in {ℝ}^{n\times n}$, if there exist $v>0\in {ℝ}^n$ and a scalar ${\alpha }_1>0$ such that $𝒜v\le {\alpha }_{1}v$, then $\rho (𝒜)\le {\alpha }_1$. Moreover, if $𝒜v<v$, then $\rho (𝒜)<1$.

3. Main results

Suppose vector $\varkappa \in {ℝ}^n$ and $𝒜=(ℳ+I-ℒ)-(𝒩+I-ℒ)$, where $I$ is the identity matrix of order $n$ and $ℒ$ is the strictly lower triangular matrix of $𝒜$. In the following result, we convert the LCP$(\sigma ,𝒜)$ into a fixed point formulation.

Theorem 5.

Suppose $𝒜\in {ℝ}^{n\times n}$ with the splitting $𝒜=(ℳ+I-ℒ)-(𝒩+I-ℒ)$ and $\sigma \in {ℝ}^n$. Let $\lambda =\tau (|\varkappa |+\varkappa )$, $\omega ={\mathrm{\Theta }}_1(|\varkappa |-\varkappa )$, where $\tau \ge 0$, $r\ge 0$ and ${\mathrm{\Theta }}_1$ is a positive diagonal matrix and the matrix $(ℳ+{\mathrm{\Theta }}_1+I-ℒ)$ be a nonsingular. Then the equivalent formulation of the LCP$(\sigma ,𝒜)$ in form of fixed point equation is

(3) $\varkappa ={(ℳ+{\mathrm{\Theta }}_1+I-ℒ)}^{-1}[(𝒩+I-ℒ)\varkappa +({\mathrm{\Theta }}_1-𝒜)|\varkappa |-r\sigma ]$

Proof.

We have $\lambda =\tau (|\varkappa |+\varkappa )$ and $\omega ={\mathrm{\Theta }}_1(|\varkappa |-\varkappa )$, from Equation (1) we obtain

${\mathrm{\Theta }}_1(|\varkappa |-\varkappa )$ $=𝒜\tau (|\varkappa |+\varkappa )+\sigma$

Since $𝒜=(ℳ+I-ℒ)-(𝒩+I-ℒ)$, this is implies that

$$((ℳ+I-ℒ)\tau +{\mathrm{\Theta }}_1)\varkappa =(𝒩+I-ℒ)\tau \varkappa +({\mathrm{\Theta }}_1-𝒜\tau )|\varkappa |-\sigma .$$

Let $\tau =\frac{1}{r}$, the above equation can be rewritten as,

$$\varkappa ={(ℳ+I-ℒ+{\mathrm{\Theta }}_1)}^{-1}[(𝒩+I-ℒ)\varkappa +({\mathrm{\Theta }}_1-𝒜)|\varkappa |-r\sigma ].$$

Hence, this is the equivalent form of the LCP$(\sigma ,𝒜)$ as a fixed point equation. $\mathrm{■}$

In the following, based on Equation (3), we propose an iteration method which is referred to as a “new accelerated modulus-based iteration method” to solve the LCP$(\sigma ,𝒜)$. Let the Euclidean norm of the error vector be denoted by the term ”residual,” which is defined as follows:

$$\mathrm{Res}({\lambda }^{(\eta )})={\Vert \min ({\lambda }^{(\eta )},𝒜{\lambda }^{(\eta )}+\sigma )\Vert }_2.$$

Let’s assume that ${\lambda }^{(0)}\in {ℝ}^n$ is an initial vector that is not negative. When the sequence ${\{{\lambda }^{(\eta )}\}}_{\eta =0}^{+\mathrm{\infty }}\subset {ℝ}^n$ converges or $Res({\lambda }^{(\eta )})$ $<$ ${10}^{-5}$, the iteration process stops. To calculate ${\lambda }^{(\eta +1)}\in {ℝ}^n$, we apply an algorithm that is shown here.

Algorithm 1 (New Accelerated Modulus-Based Iteration Method)

Step 1. Given an initial vector ${\varkappa }^{(0)}\in {ℝ}^n$, $ϵ>0$ and set $\eta =0$;                                  
Step 2. Generate the sequence ${\lambda }^{(\eta )}$ using the following scheme:

(4) $${\varkappa }^{(\eta +1)}={(ℳ+{\mathrm{\Theta }}_1+I-ℒ)}^{-1}[(𝒩+I-ℒ){\varkappa }^{(\eta )}+({\mathrm{\Theta }}_1-𝒜)|{\varkappa }^{(\eta )}|-r\sigma ]$$

and set ${\lambda }^{(\eta +1)}=\frac{1}{r}(|{\varkappa }^{(\eta +1)}|+{\varkappa }^{(\eta +1)})$, where ${\lambda }^{(\eta )}$ is a ${\eta }^{th}$ approximate solution of LCP$(\sigma ,𝒜)$ and ${\varkappa }^{(\eta )}$ is a ${\eta }^{th}$ approximate solution of Equation (4);

Step 3. Stop if $Res({\lambda }^{(\eta )})$ $<$ $ϵ$; otherwise, set $\eta =\eta +1$ and return to Step 2.

Furthermore, the proposed new accelerated modulus-based iteration method offers a generic framework for solving LCP$(\sigma ,𝒜)$. We created a new family of accelerated modulus based relaxation methods using matrix splitting. In specifically, the system matrix A is expressed as follows: $𝒜$ as $𝒜=(ℳ+I-ℒ)-(𝒩+I-ℒ)$. Then

1. when $ℳ=𝒜$, $𝒩=0$, ${\mathrm{\Theta }}_1=I$ and $r=1$, Equation (4) gives the new accelerated modulus iteration method is

   ${\varkappa }^{(\eta +1)}={(𝒜+2I-ℒ)}^{-1}[(I-ℒ){\varkappa }^{(\eta )}+(I-𝒜)|{\varkappa }^{(\eta )}|-\sigma ].$

2. when $ℳ=𝒜$, $𝒩=0$, ${\mathrm{\Theta }}_1={\alpha }_{1}I$ and $r=1$, Equation (4) gives the new accelerated modified modulus-based iteration method is

   ${\varkappa }^{(\eta +1)}={(𝒜+({\alpha }_1+1)I-ℒ)}^{-1}[(I-ℒ){\varkappa }^{(\eta )}+({\alpha }_{1}I-𝒜)|{\varkappa }^{(\eta )}|-\sigma ].$

3. when $ℳ=𝒟$, $𝒩=ℒ+𝒰$ and $r=2$, Equation (4) gives the new accelerated modulus-based Jacobi iteration method is

   ${\varkappa }^{(\eta +1)}={(𝒟+{\mathrm{\Theta }}_1+I-ℒ)}^{-1}[(𝒰+I){\varkappa }^{(\eta )}+({\mathrm{\Theta }}_1-𝒜)|{\varkappa }^{(\eta )}|-2\sigma ].$

4. when $ℳ=𝒟-ℒ$, $𝒩=𝒰$ and $r=2$, Equation (4) gives the new accelerated modulus-based Gauss-Seidel iteration (NAMGS) method is

   ${\varkappa }^{(\eta +1)}={(𝒟-2ℒ+{\mathrm{\Theta }}_1+I)}^{-1}[(𝒰+I-ℒ){\varkappa }^{(\eta )}+({\mathrm{\Theta }}_1-𝒜)|{\varkappa }^{(\eta )}|-2\sigma ].$

5. when $ℳ=(\frac{1}{{\alpha }_1}𝒟-ℒ)$ and $𝒩=(\frac{1}{{\alpha }_1}-1)𝒟+𝒰$, Equation (4) gives the new accelerated modulus-based successive over-relaxation iteration (NAMSOR) method is

   ${\varkappa }^{(\eta +1)}$ $=(𝒟-2{\alpha }_1ℒ+{\alpha }_1{\mathrm{\Theta }}_1+{\alpha }_{1}I)){}^{-1}[((1-{\alpha }_1)𝒟+{\alpha }_1𝒰$

   $+{\alpha }_{1}I-ℒ){\varkappa }^{(\eta )}+({\alpha }_1{\mathrm{\Theta }}_1-{\alpha }_1𝒜)|{\varkappa }^{(\eta )}|-2{\alpha }_1\sigma ].$

6. when $ℳ=(\frac{1}{{\alpha }_1})(𝒟-{\beta }_1ℒ)$ and $𝒩=(\frac{1}{{\alpha }_1})[(1-{\alpha }_1)𝒟+({\alpha }_1-{\beta }_1)ℒ+{\alpha }_1𝒰]$, Equation (4) gives the new accelerated modulus-based accelerated over-relaxation iteration (NAMAOR) method is

The NAMAOR method clearly converts into the following methods:

1. New accelerated modulus-based successive over-relaxation (NAMSOR) method when $({\alpha }_1,{\beta }_1)$ takes the values $({\alpha }_1,{\alpha }_1)$.

2. New accelerated Gauss-Seidel (NAMGS) method when ${\alpha }_1={\beta }_1=1$.

3. New accelerated Jacobi method when ${\alpha }_1=1$ and ${\beta }_1=0$.

4. Convergence analysis

In the following result, we prove the convergence conditions when the system matrix $𝒜$ is a $P$-matrix. When $A$ is a $P$-matrix, Equation (1) has a unique solution for every $\sigma \in {ℝ}^n$ [15].

Theorem 6.

Let $𝒜=(ℳ+I-ℒ)-(𝒩+I-ℒ)\in {ℝ}^{n\times n}$ be a $P$-matrix and ${\varkappa }^{\ast }$ be the solution of Equation (3). Suppose $\rho (|{(ℳ+I-ℒ+{\mathrm{\Theta }}_1)}^{-1}|(|𝒩+I-ℒ|+|{\mathrm{\Theta }}_1-𝒜|))<1$. Then the sequence ${\{{\varkappa }^{(\eta )}\}}_{\eta =1}^{+\mathrm{\infty }}$ generated by Algorithm 1 converges to the solution ${\varkappa }^{\ast }$ for any starting vector ${\varkappa }^{(0)}\in {ℝ}^n$.

Proof.

Let ${\varkappa }^{\ast }$ be the solution of Equation (3), then error is

${\varkappa }^{(\eta +1)}-{\varkappa }^{\ast }$ $={(ℳ+I-ℒ+{\mathrm{\Theta }}_1)}^{-1}[(𝒩+I-ℒ)({\varkappa }^{(\eta )}-{\varkappa }^{\ast })$

$+({\mathrm{\Theta }}_1-𝒜)(|{\varkappa }^{(\eta )}|-|{\varkappa }^{\ast }|)].$

Using absolute value, both sides

$|{\varkappa }^{(\eta +1)}-{\varkappa }^{\ast }|$ $=|{(ℳ+I-ℒ+{\mathrm{\Theta }}_1)}^{-1}[(𝒩+I-ℒ)({\varkappa }^{(\eta )}-{\varkappa }^{\ast })+({\mathrm{\Theta }}_1$

$-𝒜)(|{\varkappa }^{(\eta )}|-|{\varkappa }^{\ast }|)]|$

We have $|{\varkappa }^{(\eta )}|-|{\varkappa }^{\ast }|\le |{\varkappa }^{(\eta )}-{\varkappa }^{\ast }|$, therefore

This implies that

$$|{\varkappa }^{(\eta +1)}-{\varkappa }^{\ast }|<|{\varkappa }^{(\eta )}-{\varkappa }^{\ast }|.$$

Therefore the sequence ${\{{\varkappa }^{(\eta )}\}}_{\eta =1}^{+\mathrm{\infty }}$ for any starting vector ${\varkappa }^{(0)}\in {ℝ}^n$ is converges.

Since ${\lambda }^{(\eta )}=\frac{1}{r}(|{\varkappa }^{(\eta )}|+{\varkappa }^{(\eta )})$, when the sequence ${\{{\varkappa }^{(\eta )}\}}_{\eta =1}^{+\mathrm{\infty }}$ generated by Algorithm 1 converges to the solution ${\varkappa }^{\ast }$, then the sequence ${\{{\lambda }^{(\eta )}\}}_{\eta =1}^{+\mathrm{\infty }}$ also converges. $\mathrm{■}$

When the system matrix $𝒜$ is an $H_{+}$-matrix, the following result discusses the convergence domain of ${\mathrm{\Theta }}_1$ for a new accelerated modulus based iteration method.

Theorem 7.

Let $𝒜$ be an $H_{+}$-matrix and $𝒜=ℳ-𝒩=(ℳ+I-ℒ)-(𝒩+I-ℒ)$ be an $H$-compatible splitting of the matrix $𝒜$, such that $⟨𝒜⟩=⟨ℳ+I-ℒ⟩-|N+I-ℒ|$ and either one of the following conditions holds:
(1) ${\mathrm{\Theta }}_1\ge 𝒟$;
(2) ${\mathrm{\Theta }}_1<𝒟$ and $2{\mathrm{\Theta }}_1-𝒟-|B|$, is an $M$- matrix, $B=ℒ+𝒰$. Then the sequence ${\{{\varkappa }^{(\eta )}\}}_{\eta =1}^{+\mathrm{\infty }}$ generated by Algorithm 1 converges to the solution ${\varkappa }^{\ast }$ for any starting vector ${\varkappa }^{(0)}\in {ℝ}^n$.

Proof.

Let $𝒜=ℳ-𝒩=(ℳ+I-ℒ)-(𝒩+I-ℒ)$ and it holds that
$⟨𝒜⟩\le ⟨ℳ+I-ℒ⟩\le \mathrm{diag}(ℳ+I-ℒ)$, $(ℳ+I-ℒ)$ is an $H_{+}$-matrix. and it holds that

$$|{({\mathrm{\Theta }}_1+ℳ+I-ℒ)}^{-1}|\le {({\mathrm{\Theta }}_1+⟨ℳ⟩+I-ℒ)}^{-1}.$$

From Theorem 6, let $T=|{(ℳ+I-ℒ+{\mathrm{\Theta }}_1)}^{-1}|(|𝒩+I-ℒ|+|{\mathrm{\Theta }}_1-𝒜|)$, then

$T$ $=|{(ℳ+{\mathrm{\Theta }}_1+I-ℒ)}^{-1}|[|𝒩+I-ℒ|+|{\mathrm{\Theta }}_1-𝒜|]$

$\le {(⟨ℳ⟩+{\mathrm{\Theta }}_1+I-ℒ)}^{-1}[|𝒩+I-ℒ|+|{\mathrm{\Theta }}_1-𝒜|]$

$\le {(⟨ℳ⟩+{\mathrm{\Theta }}_1+I-ℒ)}^{-1}[|𝒩+I-ℒ|+|{\mathrm{\Theta }}_1-𝒟+ℒ+𝒰|]$

$\le {(⟨ℳ⟩+{\mathrm{\Theta }}_1+I-ℒ)}^{-1}[(⟨ℳ⟩+{\mathrm{\Theta }}_1+I-ℒ)-(⟨ℳ⟩+{\mathrm{\Theta }}_1+I-ℒ)$

$+|𝒩+I-ℒ|+|{\mathrm{\Theta }}_1-𝒟|+|ℒ+𝒰|].$

Case 1. ${\mathrm{\Theta }}_1\ge 𝒟$,

Since $⟨𝒜⟩$ is an $M$-matrix, then there exists a positive vector $v>0$ such that

$$⟨𝒜⟩v>0.$$

Therefore

$$Tv\le (I-2{({\mathrm{\Theta }}_1+⟨ℳ⟩+I-ℒ)}^{-1}⟨𝒜⟩)v<v.$$

Now, we are able to establish that $\rho (T)<1$ by making use of the 4.

Case 2. ${\mathrm{\Theta }}_1<𝒟$ and $⟨𝒜⟩+2{\mathrm{\Theta }}_1-𝒟-|B|$ is an $M$-matrix. Then,

$T$ $\le {(⟨ℳ⟩+{\mathrm{\Theta }}_1+I-ℒ)}^{-1}[(⟨ℳ⟩+{\mathrm{\Theta }}_1+I-ℒ)-(⟨ℳ⟩+{\mathrm{\Theta }}_1+I-ℒ)$

$+|𝒩+I-ℒ|+|{\mathrm{\Theta }}_1-𝒟|+|ℒ+𝒰|]$

$\le I-{(⟨ℳ⟩+{\mathrm{\Theta }}_1+I-ℒ)}^{-1}[(⟨ℳ⟩+I-ℒ)-|𝒩+I-ℒ|$

$+2{\mathrm{\Theta }}_1-𝒟-|ℒ+𝒰|].$

Since $[⟨𝒜⟩+2{\mathrm{\Theta }}_1-|𝒟|-|ℒ+𝒰|]$ is an $M$-matrix. Then there exists a positive vector $v>0$ such that

$$[⟨𝒜⟩+2{\mathrm{\Theta }}_1-|𝒟|-|ℒ+𝒰|]v>0.$$

Therefore

$$Tv\le I-{({\mathrm{\Theta }}_1+⟨ℳ⟩+I-ℒ)}^{-1}[⟨𝒜⟩+2{\mathrm{\Theta }}_1-𝒟-|ℒ+𝒰|]v<v.$$

We are able to establish that $\rho (T)<1$ by making use of the 4. Due to this, the Theorem 6 states that the iteration sequence ${\{{\varkappa }^{(\eta )}\}}_{\eta =1}^{+\mathrm{\infty }}$ generated by the Algorithm 1 converges to ${\varkappa }^{\ast }$ for any starting vector ${\varkappa }^{(0)}.$ $\mathrm{■}$

5. Numerical examples

In this section, several numerical examples are provided to demonstrate how effective our suggested methods are. IT stands for the number of iteration steps, while CPU represents the amount of time utilized on the CPU in seconds. Consider the LCP ($\sigma ,𝒜$), which always provides a unique solution. Let $𝒜=P_1+{\delta }_{1}I$ and $\sigma =-𝒜{\lambda }^{\ast }$, where ${\lambda }^{\ast }={(1,2,\mathrm{\dots },1,2,\mathrm{\dots })}^T\in {ℝ}^n$ is the unique solution of Equation (1). Let ${\varkappa }^{(0)}={(1,0,\mathrm{\dots }1,0,\mathrm{\dots })}^T\in {ℝ}^n$ be initial vector. The proposed methods (NAMGS and NAMSOR) are compared to the modulus-based Gauss-Seidel (MGS) method and the successive over-relaxation (MSOR) method [34], which are effective in solving LCP$(\sigma ,𝒜)$. For all computations, Matlab version 2021a is used on an Acer desktop equipped with an Intel Core i7-8700 processor running at 3.2 GHz 3.19 GHz, and 16.00 GB of RAM. Tables 1, 2 and 3 provide the numerical results of the new accelerated modulus-based iteration methods and the modulus-based matrix splitting method described in [34].

Example 8.

$𝒜$ is the system matrix and it is formed by the expression $𝒜=P_1+{\delta }_{1}I$, where ${\delta }_1$ is the positive real parameter, the identity matrix of order $m$ is denoted by the symbol $I_1$ and
, ,
where $P_1\in {ℝ}^{n\times n}$, $𝒯\in {ℝ}^{m\times m}$.

	n	$10000$	$40000$	$160000$	$640000$	$1000000$
MGS	IT	42	43	44	45	45
$\alpha =1$	CPU	0.026006	0.071892	0.36788	0.9905	1.59
	Res	8.391e-06	8.630e-06	8.768e-06	8.855e-06	9.9128e-06
NAMGS	IT	18	18	19	19	19
${\alpha }_1=1$	CPU	0.013853	0.033635	0.12218	0.47709	0.70497
	Res	5.098e-06	7.3423e-06	4.272e-06	6.069e-06	6.7921e-06
MSOR	IT	19	19	20	21	21
$\alpha =0.85$	CPU	0.013312	0.034213	0.12642	0.473	0.73996
	Res	4.325e-06	8.943e-06	6.945e-06	5.351e-06	6.7001e-06
NAMSOR	IT	13	14	14	15	15
${\alpha }_1=0.91$	CPU	0.010234	0.027824	0.090817	0.34313	0.52105
	Res	5.763e-06	2.763e-06	5.265e-06	2.561e-06	3.1766e-06

Table 1. Results for MGS and MSOR methods [34] and NAMGS and NAMSOR methods, ${\delta }_1=4$.

Example 9.

$𝒜$ is the system matrix and it is formed by the expression $𝒜=P_1+{\delta }_{1}I$, where ${\delta }_1$ is the positive real parameter, the identity matrix of order $m$ is denoted by the symbol $I_1$ and
,
$P_1\in {ℝ}^{n\times n}$, $𝒯\in {ℝ}^{m\times m}$.

	n	$10000$	$40000$	$160000$	$640000$	$1000000$
MGS	IT	27	28	28	29	29
$\alpha =1$	CPU	0.015293	0.04906	0.26455	0.63857	0.9857
	Res	7.385e-06	6.193e-06	8.809e-06	7.332e-06	8.2027e-06
NAMGS	IT	13	13	14	14	15
${\alpha }_1=1$	CPU	0.010722	0.026676	0.091557	0.32604	0.54924
	Res	5.291e-06	9.578e-06	4.257e-06	8.154e-06	2.3597e-06
MSOR	IT	15	16	16	16	17
$\alpha =0.88$	CPU	0.012181	0.028711	0.10672	0.36204	0.58685
	Res	6.344e-06	3.485e-06	5.645e-06	9.671e-06	3.7163e-06
NAMSOR	IT	9	10	10	10	10
${\alpha }_1=0.88$	CPU	0.0072254	0.019398	0.066067	0.23302	0.34536
	Res	5.874e-06	1.640e-06	3.335e-06	6.727e-06	8.4226e-06

Table 2. Results for MGS and MSOR methods [34] and NAMGS and NAMSOR methods, ${\delta }_1=4$.

Example 10.

$𝒜$ is the system matrix and it is formed by the expression $𝒜=P_1+{\delta }_{1}I$, where ${\delta }_1$ is the positive real parameter, the identity matrix of order $m$ is denoted by the symbol $I_1$ and
$\in {ℝ}^{n\times n}$,
$\in {ℝ}^{m\times m}$.

	n	$10000$	$40000$	$160000$	$640000$	$1000000$
MGS	IT	44	46	47	48	48
$\alpha =1$	CPU	0.021707	0.075858	0.38078	1.0475	1.6284
	Res	9.7023e-06	7.152e-06	7.306e-06	7.414e-06	8.3004e-06
NAMGS	IT	21	22	22	23	23
${\alpha }_1=1$	CPU	0.013821	0.038337	0.13761	0.50668	0.79966
	Res	8.262e-06	5.740e-06	8.187e-06	5.625e-06	6.2949e-06
MSOR	IT	20	21	21	22	22
$\alpha =0.87$	CPU	0.014358	0.039287	0.12957	0.48699	0.7618
	Res	5.683e-06	4.798e-06	9.742e-06	7.990e-06	9.9999e-06
NAMSOR	IT	17	17	18	19	19
${\alpha }_1=.94$	CPU	0.01243	0.029982	0.11366	0.42354	0.66273
	Res	4.841e-06	8.427e-06	5.388e-06	3.473e-06	4.2525e-06

Table 3. Results for MGS and MSOR methods [34] and NPGS and NPSOR methods, when ${\delta }_1=4$.

From Tables 1, 2 and 3, we can observe that the iteration steps required by our proposed NAMGS and NAMSOR methods have lesser number of iteration steps, faster processing (CPU time), and greater computational efficiency than the MGS and MSOR methods in [34] respectively.

6. Conclusion

The article introduces a class of new accelerated modulus-based iteration methods for the solution of large and sparse LCP$(\sigma ,𝒜)$ problems using matrix splitting. This iteration form maintains the sparsity and size of the matrix $𝒜$ during the iteration process. Additionally, when system matrix $𝒜$ is an $H_{+}$-matrix, we demonstrate some convergence conditions. At last, the efficacy of the proposed methods is demonstrated through the presentation of various numerical instances.

Acknowledgements.

The first author would like to thank the University Grants Commission (UGC), Government of India, for funding the SRF fellowship program No. 1068 /(CSIR-UGC NET DEC. 2017).