# The Block Principal Pivoting Algorithm for the Linear Complementarity Problem with anM-Matrix

Authors: Xi-Ming Fang; Zhi-Jun Qiao; Heng-Jun Zhao
Journal: Advances in Mathematical Physics
 (2019)

---

## Abstract

The principal pivoting algorithm is a popular direct algorithm in solving the linear complementarity problem, and its block forms had also been studied by many authors. In this paper, relying on the characteristic of block principal pivotal transformations, a block principal pivoting algorithm is proposed for solving the linear complementarity problem with anM-matrix. By this algorithm, the linear complementarity problem can be solved in some block principal pivotal transformations. Besides, both the lower-order and the higher-order experiments are presented to show the effectiveness of this algorithm.


---

## Body

## 1. Introduction

For a given matrixA∈Rn×n and a given vector q∈Rn, the linear complementarity problem is to find a vector x∈Rn such that(1)xTw=0,x≥0,w=Ax+q≥0,where the superscript “T” denotes the transpose of a vector. This problem is usually abbreviated as LCP(A,q) and many problems can be converted into (1) under some conditions, such as the linear and quadratic programming problems, the free boundary problems of journal bearings, and Black-Scholes American option pricing problems (see [1–10] and the references therein).To obtain the numerical solution of (1), many authors have presented all kinds of methods in recent decades. Some authors discussed the single principal pivoting algorithms based on the complementarity pivot idea (see [3, 11–18]). In [3], the authors presented the principal pivoting algorithm for the case that the matrix A was an M-matrix, and the concrete matrices were the tridiagonal matrix and the block tridiagonal matrix, which were derived from the free boundary problems of journal bearings. This algorithm was a direct algorithm, and the principal pivoting procedure was carried out element by element in a cycle. So, there needs to be many cycles when the LCP(A,q) was solved in the end. There were some papers to discuss the block principal pivoting algorithms for (1), such as [19–25]. In [20], the authors presented two block principal pivoting algorithms for the LCP(A,q) and the BLCP(A,q), respectively, and the system matrix A is the P-matrix. About the two block principal pivoting algorithms, the authors gave many numerical experiments to show the effectiveness in [20]. The two block principal pivoting algorithms were designed for the general P-matrix and there was a predetermined constant p involved in the block principle pivoting algorithms, which was related to the number of the block principal pivotal transformations. Besides the direct algorithms introduced above, there are many iteration methods, in which the modulus-based matrix splitting iteration methods were studied by many authors recently, and a series of related methods had been presented gradually (see [1, 9, 26–34] and the references therein). Other solving methods, such as the nonstationary extrapolated modulus algorithms, the projection type iteration methods, and the interior-point iteration methods, can refer to [2, 7, 35–41] and the references therein.The iteration methods are affected by many factors, for instance, the parameter matrixΩ and the matrix splitting forms in the modulus-based matrix splitting related iteration methods and the parameter α in the projection type iteration methods. The forms of the direct methods are very simple sometimes, and the solving processes are only determined by the matrix A and the vector q. Moreover, the solutions obtained by the direct methods are the exact solutions, which are different from the approximate solutions obtained by the iteration methods. In this paper, we further discuss the direct methods for the LCP(A,q). We consider a particular linear complementarity problem that the system matrix A is an M-matrix. Utilizing the characteristic of the M-matrix’s block principal pivotal transformation, that is, any block principal pivotal transformation of an M-matrix can produce four particular submatrices, we provide a concrete block principal pivoting algorithm based on [3, 6, 7, 11, 20]. The numerical experiments show the effectiveness of this algorithm.This paper is organized as follows. We introduce the block principal pivoting algorithm idea and present the concrete algorithm in Sections2 and 3, respectively. Numerical experiments are shown and discussed in Section 4. Finally, we end this paper by the concluding remark in Section 5.


## 2. Block Principal Pivoting Algorithm

We first briefly review some definitions and notations in the following. The matrixA∈Rn×n is denoted by A≥0 if aij≥0,i,j=1,2,…,n. A matrix A∈Rn×n is called a Z-matrix if aij≤0(i≠j),i,j=1,2,…,n. A matrix A∈Rn×n is called an M-matrix if it is a Z-matrix and satisfies A-1≥0. The real vector v is denoted by v≥0(>0) if vi≥0(>0) holds for i=1,2,…,n. All these definitions and notations can refer to [1, 3, 7, 28] and the references therein.Lemma 1 (see [11]).
IfA∈Rn×n is a Z-matrix and x¯ satisfies conditions (1)  q+Ax¯≥0 and (2)  x¯≥0 in (1), then x¯i>0 whenever qi<0.
For the LCP(A,q), since the condition wixi=0 with wi≥0 and xi≥0,i=1,2,…,n are required, it is easy to establish the following conclusion from Lemma 1.Lemma 2.
IfA∈Rn×n is a Z-matrix and x¯ is a solution of (1), then x¯i>0 and w¯i=0 whenever qi<0.
In [3], the authors introduced the two concepts, that is, the basic variable wi and the nonbasic variable xi,i=1,2,…,n based on (1), and give Table 1.Table 1
The table of the LCP(A,q).
x 1 x 2 ⋯ x n w 1 q1 a11 a12 ⋯ a1n w 2 q 2 a 21 a 22 ⋯ a 2 n ⋮ ⋮ ⋮ ⋮  ⋮ w n q n a n 1 a n 2 ⋯ a n nFrom the theory ofLCP(A,q), we know that if the problem is solved, there must exist an equivalent converted LCP(A(i),q(i)) corresponding to the solution x∗ with w∗, as shown in the form of Table 2, where the LCP(A(i),q(i)) is obtained from the LCP(A,q) by the same computation transformations for both the rows and the columns of A. The index set Swnonbasic=i1,i2,…,ir corresponds to both the nonbasic variable set of wis and the basic variable set of xis; meanwhile, the index set Swbasic=ir+1,ir+2,…,in corresponds to both the basic variable set of wis and the nonbasic variable set of xis. Moreover, if the solution is unique, the solution of LCP(A(i),q(i)) as well as the solution of LCP(A,q) can be constructed from(2)xi1∗xi2∗⋮xir∗=-a11ia12i⋯a1ria21ia22i⋯a2ri⋮⋮⋮ar1iar2i⋯arri-1q1iq2i⋮qri≥0andxir+1∗xir+2∗⋮xin∗=00⋮0.At the same time, w∗ can be constructed from(3)wi1∗wi2∗⋮wir∗=00⋮0andwir+1∗wir+2∗⋮win∗=-ar+11iar+12i⋯ar+1riar+21iar+22i⋯ar+2ri⋮⋮⋮an1ian2i⋯anrixi1∗xi2∗⋮xir∗+qr+1iqr+2i⋮qni≥0.So, if the LCP(A,q) has a unique solution and the sets Swnonbasic and Swbasic are obtained, it can be solved easily from (2) and (3). It is well known that LCP(A,q) with an M-matrix A has a unique solution for any q∈Rn (see [1, 3, 28]); thus the main task is to find the above two sets. Besides, we remark here that Table 2 is only a representation form for the sake of later discussion, which has other representation forms, where {wi1,wi2,…,wir} and {xi1,xi2,…,xir} are exchanged, and both A(i) and q(i) are difference from Table 2 and it is enough to note the index set in the solving process of the LCP(A,q).Table 2
The table of the convertedLCP(Ai,qi).
x i 1 x i 2 ⋯ x i r x i r + 1 x i r + 2 ⋯ xin wi1 q1(i) a 11 ( i ) a 12 ( i ) ⋯ a1r(i) a 1 r + 1 ( i ) a1r+2(i) ⋯ a1n(i) wi2 q2(i) a 21 ( i ) a 22 ( i ) ⋯ a2r(i) a 2 r + 1 ( i ) a 2 r + 2 ( i ) ⋯ a 2 n ( i ) ⋮ ⋮ ⋮ ⋮  ⋮ ⋮ ⋮  ⋮ wir qr(i) a r 1 ( i ) a r 2 ( i ) ⋯ arr(i) a r r + 1 ( i ) a r r + 2 ( i ) ⋯ a r n ( i ) wir+1 qr+1(i) a r + 11 ( i ) a r + 12 ( i ) ⋯ a r + 1 r ( i ) a r + 1 r + 1 ( i ) a r + 1 r + 2 ( i ) ⋯ ar+1n(i) wir+2 qr+2(i) a r + 21 ( i ) a r + 22 ( i ) ⋯ ar+2r(i) a r + 2 r + 1 ( i ) a r + 2 r + 2 ( i ) ⋯ a r + 2 n ( i ) ⋮ ⋮ ⋮ ⋮  ⋮ ⋮ ⋮  ⋮ win qn(i) a n 1 ( i ) a n 2 ( i ) ⋯ anr(i) a n r + 1 ( i ) a n r + 2 ( i ) ⋯ a n n ( i )Problem LCP(A(i), q(i)) is equivalent to the original LCP(A,q). Of course, both the equivalent LCP(A(i), q(i)) and the above corresponding table are not unique and even the original LCP(A,q) has a unique solution. Moreover, if we obtain Table 2, from the first two columns and the first row of which, we can construct the solution x∗ with w∗ of the LCP(A,q).From Lemma2, we know that if qi<0, then i∈Swnonbasic. However, if qi>0 or qi=0, we need to judge whether i∈Swnonbasic. For an M-matrix A with order n, if we set U=1,2,…,n and set a nonempty set N=i1,i2,…,ir⊆U with P=U-N, then through the block principal pivotal transformation, we can obtain a matrix(4)ANN-1-ANN-1ANPAPNANN-1APP-APNANN-1ANP,where(5)ANN-1≥0,-ANN-1ANP≥0,APNANN-1≤0and(6)APP-APNANN-1ANPis Schur complement matrix of ANN, which is a lower-order M-matrix. From (5) and (6), combining with the characteristic of the linear complementarity problem, a block principal pivoting algorithm can be presented to search for the set Swnonbasic and solve the LCP(A,q). The basic idea of this algorithm is that we set a small Swnonbasic according to the original q and then amplify Swnonbasic by adding the new indices until the size of Swnonbasic keeps unchanged; thus we construct the solution of the LCP(A,q) by (2). We show the concrete solving process of block principal pivoting algorithm in the following paragraph.We denote the negative entry index set ofq by Swnonbasic=N with N≠U and N≠Φ, the other entry index set by P, where U=1,2,…,.,n and Φ denotes the empty set. Then from Lemma 2 we set wN=0 and carry out the block principal pivotal transformation to the submatrix ANN of A, and then we have xN=-ANN-1(ANPxP+qN) and(7)wP=APP-APNANN-1ANPxP-APNANN-1qN+qP,wPTxP=0.The equation in (7) is an established complementarity problem and the system matrix is still an M-matrix with lower-order than the matrix A from (6). Then we can select the negative entry index set of the constant vector in the right side of wP and add it to Swnonbasic. At the same time, according to the negative entry index set, we carry out the block principal pivotal transformation to the lower-order complementarity problem (7). These processes can be continued until the constant vector in the last lower-order complementarity problem has no negative element and then Swnonbasic keeps unchanged. Once the last Swnonbasic is obtained, then we can apply (2) to construct the unique solution of (1).About the above block principal pivoting algorithm, we have the following discussions.(1) At the beginning of block principal pivoting algorithm, the solution can be obtained easily ifSwnonbasic=N or Swnonbasic=Φ, that is, x∗=A-1(-q) and x∗=0, respectively.(2) The block principal pivoting algorithm can be divided into two parts: the searching process ofSwnonbasic and the constructing process of x∗.(3) The orders of the linear complementarity problems in the block principal pivoting algorithm are decreasing gradually, and the total number of the block principal pivotal transformations is no more thann when the LCP(A,q) is solved.


## 3. Algorithm

In this section, based on the discussion in the above section, we present the pseudocodes of the block principal pivoting algorithm as Algorithm1.Algorithm 1:Block-Principal-Pivoting-Algorithm.
Require: MatrixA,VectorQ Ensure: SolutionX 1: function  SolutionX = blockpivotingalgorithm(MatrixA,VectorQ) 2: NegativeLocation = Location(MatrixA,VectorQ) 3: if  NegativeLocation equals to {1,2,…,n}  then 4: SolutionX←inv(MatrixA)∗(-VectorQ) 5: return 6: end if 7: if  NegativeLocation equals to an empty set  then 8: SolutionX←0 9: return 10: end if 11: extract MatrixAnn from MatrixA according to NegativeLocation 12: split VectorQ into VectorQn and VectorQp according to NegativeLocation 13: SolutionXPositivePart←inv(MatrixAnn)∗(-VectorQn) 14: SolutionXNegativePart←0 15: construct SolutionX with SolutionXPositivePart and SolutionXNegativePart 16: end function 17: function  negativelocation = location(MatrixA, VectorQ) 18: NegativeLocation← according to the sign of each element of VectorQ 19: if  NegativeLocation=={1,2,…,n}  then 20: return 21: end if 22: if  NegativeLocation==Φ  then 23: return 24: end if 25: extract MatrixAnn,MatrixApn,MatrixApp and MatrixAnp from MatrixA according to NegativeLocation 26: split VectorQ into VectorQn and VectorQp according to NegativeLocation 27: MatrixA←MatrixApp-MatrixApn∗inv(MatrixAnn)∗MatrixAnp 28: VectorQ←-MatrixApn∗inv(MatrixAnn)∗VectorQn+VectorQp 29: addNegativeLocation← Location(MatrixA,VectorQ) 30: construct NegativeLocation by NegativeLocation and addNegativeLocation 31: return 32: end function


## 4. Numerical Experiment

In this section, we present three examples. In the first example, we illustrate the solving process of the block principal pivoting algorithm by two lower-order cases. In the second example, we apply the block principal pivoting algorithm to deal with a practical problem, that is, the free boundary value problem about the flow of water through a porous dam, which is a higher-order case. In the third example, we mainly investigate the relationship between the running time and the number of the block principal pivotal transformations in the block principal pivoting algorithm.Example 1.
We set the system matrixA in the LCP(A,q) to be (8)A=10-10-1-120-1-10-13-10-10-14-10-1-105,and consider the variable q to be two cases: (9)q¯=-1,2,-1,2,1T,q^=-1,1,-1,0,1T.Thus, the matrix A is an M-matrix and the LCP(A,q¯) and the LCP(A,q^) have the same U=1,2,3,4,5 and the original negative element index set (10)S¯wnonbasic=S^wnonbasic=1,3,which corresponds to the the nonbasic variable set of wis and the basic variable set of xis. Applying the block principal pivoting algorithm to the LCP(A,q¯) and the LCP(A,q^), respectively, then we have the last negative element index sets (11)S¯wnonbasic=1,3andS^wnonbasic=1,2,3,4,5and the solutions are (12)x¯∗=43,0,13,0,0Twithw¯∗=0,23,0,13,23Tand (13)x^∗=167,1714,2928,2528,14Twithw^∗=0,0,0,0,0T,respectively. Besides, the numbers of the block principal pivoting transformations for the LCP(A,q¯) and the LCP(A,q^) are 1 and 2, respectively.Example 2.
In this example, we consider the higher-order case and setA in the LCP(A,q) to be a block tridiagonal M-matrix, that is, A=Tridiag(-I,S,-I)∈Rn×n, where(14)S=tridiag-1,4,-1=4-1⋯00-14⋯00⋮⋮⋮⋮00⋯4-100⋯-14∈Rm×mand I is an identity matrix of order m. We set (15)q¯=-1,1,-1,1,…T,q^=-1,1,0,-1,1,0,…T∈Rnwith n=m2 and perform five experiments for m=20,30,40,50,60, respectively. This problem arises from the finite difference discretization on equidistant grid of a free boundary value problem about the flow of water through a porous dam (see [26] and the references therein). We consider three quantities, that is, the running time (CPU), the number of block principal pivotal transformations (NUM), and the error of the residual vector (ERROR). ERROR is defined as (16)ERROR=normmin⁡x,Ax+q,where both “norm” and “min” are the functions in Matlab software (see [1, 26]). Then the numerical results are shown in Table 3.Table 3
The block principal pivoting algorithm for solving the LCP(A,q).
L C P ( A , q - ) L C P ( A , q ^ ) n 400 900 1600 2500 3600 400 900 1600 2500 3600 CPU 0.005 0.025 0.094 0.298 0.732 0.007 0.038 0.122 0.341 1.012 NUM 1 1 1 1 1 2 2 2 2 2 ERROR 2e-15 3e-15 4e-15 5e-15 6e-15 2e-15 5e-15 4e-15 4e-15 1e-14From Table3, we can find that the block principal pivoting algorithm is effective and the number of the block principal pivotal transformations is very small in this example. Besides, the precision of the solution is very high and the running time will be increased when the model’s size is enlarged.Example 3.
In this example, we consider the relationship between the running time and the number of block principal pivotal transformations. Set the system matrixA to be a tridiagonal M-matrix, that is, (17)A=tridiag-1,2,-1∈Rn×n,and set q to be an arbitrary vector, that is, q=randn(n,1), and carry out 10 experiments; then we obtain Table 4.Table 4
Comparison between the running time and the number of block principal pivotal transformations.
L C P ( A , q ) , A = t r i d i a g ( - 1,2 , - 1 ) , q = r a n d n ( n , 1 ) , n = 1000 q q1 q2 q3 q4 q5 q 6 q7 q8 q9 q10 CPU 0.121 0.105 0.087 0.089 0.068 0.102 0.086 0.088 0.072 0.065 NUM 21 20 21 17 22 22 18 27 35 21 ERROR 3e-12 2e-12 4e-12 5e-13 3e-11 3e-12 2e-12 3e-12 3e-11 9e-12From Table4, we can observe that when the number of block principal pivotal transformations is larger, the running time usually increases slightly. However, the relationship between the number of block principal pivotal transformations and the running time is not entirely consistent, which can be found from q1,q2,q8, and q9. In addition, although the precision of the solution decreases slightly compared with Example 2 with the increasing number of block principal pivotal transformations, we can see that the precision is still very high.At the end of this section, we remark that since the LCP(A,q) is equivalent to the linear complementarity problem(18)wTx=0,w≥0,x=A-1w+A-1-q≥0,which is denoted by LCP(A-1,A-1(-q)) here, if A-1 is an M-matrix (A is called an inverse M-matrix), then the original LCP(A,q) can be solved through solving the LCP(A-1,A-1(-q)) by the block principal pivoting algorithm. In addition, besides the free boundary value problem about the flow of water through a porous dam mentioned in Example 2, there are other two applications where the block principal pivoting algorithm can be utilized: one is Black-Scholes American option pricing problem and the other is the free boundary problem of journal bearings. The discretized approximation models of the two problems are the LCP(A,q)s with M-matrices and the details can be found in [8, 9] and [3], respectively.


## 5. Concluding Remark

In this paper, we provide a block principal pivoting algorithm for solving the LCP(A,q) with an M-matrix. By this algorithm, the LCP(A,q) can be solved in the limited block principal pivotal transformations. The numerical experiments show that this algorithm is effective in practical applications and the numerical solutions possess very high precision.



---

*Source: 2976768-2019-07-30.xml*