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

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:

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

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.

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 $⟨𝒜⟩=⟨ℳ⟩-|𝒩|$.

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.

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

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

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.

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.