# A Preconditioned Multisplitting and Schwarz Method for Linear Complementarity Problem

Authors: Cuiyu Liu; Chen-liang Li
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

The preconditioner presented by  Hadjidimos et al. (2003) can improve on the convergence rate of the classical iterative methods to solve linear systems. In this paper, we extend this preconditioner to solve linear complementarity problems whose coefficient matrix isM-matrix or H-matrix and present a multisplitting and Schwarz method. The convergence theorems are given. The numerical experiments show that the methods are efficient.


---

## Body

## 1. Introduction

Many science and engineering problems are usually induced as linear complementarity problems (LCP): find anx
∈
R
n such that
(1)
x
≥
0
,
A
x
-
f
≥
0
,
x
⊤
(
A
x
-
f
)
=
0
,
where A
=
[
a
i
j
]
∈
R
n
×
n is a given matrix and f
∈
R
n is a vector. It is necessary to establish an efficient algorithm to solve the complementarity problem. Numerical methods for complementarity problems fall in two major kinds, direct and iterative methods. There have been lots of works on the solution of the linear complementarity problem ([1–4], etc.), which presented feasible and essential techniques for LCP. Recently some parallel multisplitting iterative methods for solving the large sparse linear complementarity problems are presented ([5–11], etc.). These methods are based on several splittings of the system matrix A and are constructed with a suitable weighting combination of the solution of the sublinear complementarity problems.For the large sparse linear complementarity problem, some accelerated modulus-based matrix splitting iteration methods and modulus-based synchronous two-stage multisplitting iteration methods are constructed [7, 11]. Numerical results show that these methods are more efficient.Many researchers have studied preconditioners applied to linear system(2)
A
x
=
b
,
so that the corresponding iterative methods, such as Jacobi or GS, converge faster than the classical ones. Hadjidimos et al. [12] considered the following preconditioner:
(3)
P
1
(
α
)
≡
I
+
S
1
(
α
)
=
(
1
-
α
2
a
21
1
⋮
⋱
-
α
i
a
i
1
1
⋮
⋱
-
α
n
a
n
1
1
)
,
where α
=
[
0
,
α
2
,
…
,
α
i
,
…
,
α
n
]
∈
R
n with constants α
i
≥
0
,
i
=
2
(
1
)
n.Consider(4)
S
1
(
α
)
=
(
0
-
α
2
a
21
0
⋮
⋱
-
α
i
a
i
1
0
⋮
⋱
-
α
n
a
n
1
0
)
.In (3), let α
i
=
1
,
i
=
2
(
1
)
n; P
1
(
α
) is a preconditioner presented by Milaszewicz [13]. It eliminates the elements of the first column of A below the diagonal. Reference [12] shows that the new modifications and improvements of the original preconditioners can improve on the convergence rates of the classical iterative methods (Jacobi, GS, etc.).In this paper, with multisplitting technique, we will extend the preconditioner to solve the linear complementarity problem (1) and present a new multisplitting and Schwarz method. The new method is parallel and has high computational efficiency.In Section2, some preliminaries for the new method are presented. A multisplitting and Schwarz method is given in Section 3. Convergence analysis is given in Section 4. Section 5 presents the numerical experiments results.


## 2. Preliminaries

At first we briefly describe the notations. InR
n and R
n
×
n, the relation ≥ denotes the natural components partial ordering. In addition, for x
,
y
∈
R
n, we write x
>
y if x
i
>
y
i
,
i
=
1,2
,
…
,
n. A nonsingular matrix A
=
(
a
i
j
)
∈
R
n
×
n is termed M-matrix, if a
i
j
≤
0 for i
≠
j and A
-
1
≥
0. Or the nonsingular matrix A
=
(
a
i
j
)
∈
R
n
×
n is called M-matrix, if A
=
s
I
-
C, C
≥
0, and ρ
(
C
)
<
s. Its comparison matrix 〈
A
〉
=
(
α
i
j
) is defined by α
i
i
=
|
a
i
i
| and α
i
j
=
-
|
a
i
i
|
(
i
≠
j
). A is said to be an H-matrix if 〈
A
〉 is an M-matrix. To simplify the notation, we may assume that a
i
i
=
1
,
i
=
1
(
1
)
n.Lemma 1 (see [2]).
LetA be an M-matrix and let x be a solution of (1).(1)
Iff
i
>
0, then x
i
>
0 and therefore ∑
j
=
1
n
‍
a
i
j
x
j
-
f
i
=
0.
(2)
Iff
≤
0, then x
=
0 is the solution of (1).If the problem (1) has a nonzero solution, there at least exists an index k, f
k
>
0. In this paper, let us assume that f
1
>
0. By Lemma 1, we have the following conclusion.Lemma 2 (see [14]).
LetA be an M-matrix, A
~
(
α
)
=
P
1
(
α
)
A
≡
[
a
~
i
j
], and f
~
(
α
)
=
P
1
(
α
)
f
≡
f
~. If f
1
>
0, then the following linear complementarity problem
(5)
x
≥
0
,
A
~
(
α
)
x
-
f
~
(
α
)
≥
0
,
x
⊤
(
A
~
(
α
)
x
-
f
~
(
α
)
)
=
0
is equivalent to the problem (1).Lemma 3 (see [15]).
LetA
=
[
a
i
j
]
∈
R
n
×
n and a
i
j
≤
0 for i
≠
j. A is an M-matrix if and only if there exists a positive vector y such that A
y
>
0.Definition 4 (see [16]).
(1)A splitting A
=
M
-
N is termed a regular splitting of matrix A if M
-
1
≥
0 and N
≥
0.
(2)A splitting A
=
M
-
N is termed M-splitting of matrix A if M is an M-matrix and N
≥
0.
(3)A splitting A
=
M
-
N is termed H-compatible splitting of matrix A if 〈
A
〉
=
〈
M
〉
-
|
N
|.Lemma 5 (see [16]).
LetA
=
M
1
-
N
1
=
M
2
-
N
2 be two regular splittings of A, where A
-
1
≥
0.(1)
IfN
2
≥
N
1
≥
0, then
(6)
0
≤
ρ
(
M
1
-
1
N
1
)
≤
ρ
(
M
2
-
1
N
2
)
<
1
.
(2)
IfM
1
-
1
≥
M
2
-
1, then
(7)
0
≤
ρ
(
M
1
-
1
N
1
)
≤
ρ
(
M
2
-
1
N
2
)
<
1
.
By Lemma5, we have the following lemma.Lemma 6.
LetA
=
M
-
N
=
D
-
B be two M-splittings of A, and
(8)
D
=
diag
⁡
{
a
11
,
a
22
,
…
,
a
n
n
}
.
If M
≤
D, then ρ
(
M
-
1
N
)
≤
ρ
(
D
-
1
B
)
<
1.Lemma 7 (see [14]).
IfA is an M-matrix, then A
~
(
α
) is a Z-matrix and A
~
(
α
) is also an M-matrix.Lemma 8 (see [15]).
A is a nonsingular M-matrix if and only if all the principal minors of A are positive.By (4), we have
(9)
S
1
(
α
)
U
=
(
0
0
0
⋯
0
0
α
2
a
21
a
12
α
2
a
21
a
13
⋯
α
2
a
21
a
1
n
0
α
3
a
31
a
12
α
3
a
31
a
13
⋯
α
3
a
31
a
1
n
⋮
⋮
⋮
⋱
⋮
0
α
n
a
n
1
a
12
α
n
a
n
1
a
13
⋯
α
n
a
n
1
a
1
n
)
.Define the following matrices:(10)
D
α
=
diag
⁡
(
0
,
α
2
a
21
a
12
,
α
3
a
31
a
13
,
…
,
α
n
a
n
1
a
1
n
)
,
L
α
=
(
0
0
⋯
0
0
0
0
⋯
0
0
0
α
3
a
31
a
12
⋯
0
0
⋮
⋮
⋱
⋮
⋮
0
α
n
a
n
1
a
12
⋯
α
n
a
n
1
a
1
,
n
-
1
0
)
,
U
α
=
(
0
0
0
⋯
0
0
0
α
2
a
21
a
13
⋯
α
2
a
21
a
1
n
⋮
⋮
⋮
⋱
⋮
0
0
0
⋯
α
n
-
1
a
n
-
1,1
a
1
n
0
0
0
⋯
0
)
.Consider the following splittings [12]:
(11)
A
~
(
α
)
=
{
M
1
(
α
)
-
N
1
(
α
)
=
(
I
+
S
1
(
α
)
)
-
(
I
+
S
1
(
α
)
)
(
L
+
U
)
,
M
2
(
α
)
-
N
2
(
α
)
=
I
-
(
L
+
L
α
-
S
1
(
α
)
+
U
+
U
α
+
D
α
)
,
M
3
(
α
)
-
N
3
(
α
)
=
(
I
-
D
α
)
-
(
L
+
L
α
-
S
1
(
α
)
+
U
+
U
α
)
,
M
4
(
α
)
-
N
4
(
α
)
=
(
I
-
(
L
-
S
1
(
α
)
)
)
-
(
D
α
+
L
α
+
U
+
U
α
)
,
M
5
(
α
)
-
N
5
(
α
)
=
(
I
-
(
L
-
S
1
(
α
)
)
-
L
α
)
-
(
D
α
+
U
+
U
α
)
,
M
6
(
α
)
-
N
6
(
α
)
=
(
I
-
(
L
-
S
1
(
α
)
)
-
D
α
-
L
α
)
-
(
U
+
U
α
)
.Define the following matrices with the above splittings:(i)
B
≡
M
1
-
1
(
α
)
N
1
(
α
)
=
L
+
U;
(ii)
B
′
≡
M
2
-
1
(
α
)
N
2
(
α
)
=
L
+
L
α
+
U
+
U
α
+
D
α
-
S
1
(
α
);
(iii)
B
′′
≡
M
3
-
1
(
α
)
N
3
(
α
)
=
(
I
-
D
α
)
-
1
(
L
+
L
α
+
U
+
U
α
-
S
1
(
α
)
);
(iv)
H
≡
(
I
-
L
)
-
1
U;
(v)
H
′
≡
M
5
-
1
(
α
)
N
5
(
α
)
=
(
I
-
(
L
-
S
1
(
α
)
)
-
L
α
)
-
1
(
D
α
+
U
+
U
α
);
(vi)
H
′′

≡

M
6
-
1
(
α
)
N
6
(
α
)

=

(
I

-

(
L

-

S
1
(
α
)
)

-

D
α

-

L
α
)
-
1
(
U

+

U
α
).Theorem 9 (see [12]).
Under the notation so far, ifA is an M-matrix, then, for any α
i
∈
[
0,1
]
(
i
=
1,2
,
…
,
n
), there exists y
∈
R
n, y
≥
0, such that
(12)
B
′
y
≤
B
y
,
ρ
(
B
′′
)
≤
ρ
(
B
′
)
<
1
,
ρ
(
H
′′
)
≤
ρ
(
H
′
)
≤
ρ
(
H
)
<
1
,
ρ
(
H
′′
)
≤
ρ
(
B
′′
)
,
ρ
(
H
′
)
≤
ρ
(
B
′
)
,
ρ
(
H
)
≤
ρ
(
B
)
<
1
.


## 3. Synchronous Multisplitting and Schwarz Method

By Theorem9, ρ
(
H
′′
)
≤
ρ
(
H
)
≤
ρ
(
B
)
<
1. It means that the Gauss-Seidel iterative methods associated with the new preconditional matrix A
~
(
α
)
=
P
1
(
α
)
A will be no worse than the ones corresponding to A. Similar to [6], we present a synchronous multisplitting and Schwarz algorithm corresponding to A
~
(
α
).Algorithm 10 (synchronous multisplitting and Schwarz method).
(1) Give an initial vectorx
0
,
k
=
0.
(2) Let(13)
x
k
+
1
=
∑
i
=
1
m
E
i
y
k
,
i
,
where ∑
i
=
1
m
E
i
=
I, E
i is a nonnegative diagonal matrix, and y
k
,
i is the solution of the following LCP:
(14)
y
k
,
i
≥
0
,
M
i
y
k
,
i
≥
F
k
,
(
y
k
,
i
)
⊤
(
M
i
y
k
,
i
-
F
k
)
=
0
,
where F
k
=
f
+
N
i
x
k, A
~
(
α
)
=
M
i
-
N
i.
(3) Considerk
:
=
k
+
1; if the iteration solution is convergent, stop; else, return to step (2).LetD
=
diag
⁡
{
a
11
,
a
22
,
…
,
a
n
n
}, I
i
=
{
j
:
j
∈
S
i
}, and J
i
=
S
∖
I
i. Define M
~
i as
(15)
M
~
i
=
{
(
M
~
i
)
I
i
=
A
I
i
,
(
M
~
i
)
J
i
=
D
J
i
,
(
M
~
i
)
I
i
J
i
=
0
,
(
M
~
i
)
J
i
I
i
=
0
,
where A
I
J denotes (
a
k
j
)
k
∈
I
,
j
∈
J and A
I denotes (
a
k
j
)
k
,
j
∈
I.Then the following lemma is obviously true.Lemma 11.
For each splittingA
~
(
α
)
=
M
~
i
-
N
~
i
(
i
=
1,2
,
…
,
m
), let M
~
i be defined by (15). Then the subproblem (14) is equivalent to the following problem: find y
k
,
i
∈
R
n, such that
(16)
y
k
,
i
≥
0
,
A
I
i
y
I
i
k
,
i
≥
F
I
i
k
,
D
J
i
y
J
i
k
,
i
≥
F
J
i
k
,
(
y
I
i
k
,
i
)
⊤
(
A
I
i
y
I
i
k
,
i
-
F
I
i
k
)
=
0
,
(
y
J
i
k
,
i
)
⊤
(
D
J
i
y
J
i
k
,
i
-
F
J
i
k
)
=
0
.


## 4. Convergence Analysis

In this section, we give the convergence analysis of the algorithm.Lemma 12 (see [6]).
Letx
* be the solution of (1), and y
k
,
i is the solution of (14); then
(17)
|
y
k
,
i
-
x
*
|
≤
M
i
-
1
N
i
|
x
*
-
x
k
|
.Theorem 13.
LetA be an M-matrix; the sequence {
x
k
} generated by Algorithm 10 converges to the solution of (1).Proof.
The conclusion easily resulted from Lemma2, Lemma 12, and Theorem 9.In Lemma7, if i
≠
1
,
0
≤
α
i
≤
1, then A
~
(
α
) is an M-matrix. If i
≠
1, α
i
≥
1, then a
~
i
j
=
(
1
-
α
i
)
a
i
1
≥
0 and A
~
(
α
) is not an M-matrix. In the sequel we will examine that A
~
(
α
) is an H-matrix with positive diagonal elements, where α
i
(
i
≠
1
) satisfies some conditions.Lemma 14 (see [16]).
LetA be either a strictly diagonally dominant or an irreducibly dominant matrix. Then A is an H-matrix.Lemma 15.
LetA be a diagonally dominant M-matrix. If i
≠
1 and for a
i
1
≠
0, 1
≤
α
i
≤
(
∑
j
=
1
n
a
i
j
-
2
a
i
1
)
/
(
-
a
i
1
(
2
-
∑
j
=
1
n
a
1
j
)
), then A
~
(
α
) is an H-matrix with positive diagonal elements.Proof.
Note thata
i
i
=
1
,
0
≤
-
a
i
j
≤
1, and ∑
j
=
1
n
a
i
j
≥
0. We have
(18)
1
a
i
1
a
1
i
-
∑
j
=
1
n
a
i
j
-
2
a
i
1
-
a
i
1
(
2
-
∑
j
=
1
n
a
1
j
)
=
(
2
-
∑
j
=
1
n
a
1
j
)
+
a
1
i
(
∑
j
=
1
n
a
i
j
-
2
a
i
1
)
a
i
1
a
1
i
(
2
-
∑
j
=
1
n
a
1
j
)
=
(
(
1
-
a
i
1
a
1
i
)
+
(
1
-
∑
j
=
1
n
‍
a
1
j
)
VVVVVVI
+
a
1
i
(
∑
j
=
1
n
‍
a
i
j
-
a
i
1
)
)
V
V
V
V
×
(
a
i
1
a
1
i
(
2
-
∑
j
=
1
n
‍
a
1
j
)
)
-
1
≥
(
1
-
a
i
1
a
1
i
)
+
(
-
∑
j
≠
1
a
1
j
)
+
a
1
i
a
i
1
a
1
i
(
2
-
∑
j
=
1
n
a
1
j
)
=
(
1
-
a
i
1
a
1
i
)
+
(
-
∑
j
≠
1
,
i
a
1
j
)
a
i
1
a
1
i
(
2
-
∑
j
=
1
n
a
1
j
)
>
0
,
∑
j
=
1
n
a
i
j
-
2
a
i
1
-
a
i
1
(
2
-
∑
j
=
1
n
a
1
j
)
≥
-
2
a
i
1
-
a
i
1
(
2
-
∑
j
=
1
n
a
1
j
)
∑
j
=
1
n
‍
a
i
j
-
2
a
i
1
-
a
i
1
(
2
-
∑
j
=
1
n
‍
a
1
j
)
V
I
=
2
(
2
-
∑
j
=
1
n
a
1
j
)
>
1
.
α
i is well defined. By the definition of A
~
(
α
), and for i
≠
1, 1
≤
α
i
≤
(
∑
j
=
1
n
‍
a
i
j
-
2
a
i
1
)
/
(
-
a
i
1
(
2
-
∑
j
=
1
n
‍
a
1
j
)
), we have that(1)
∑
j
=
1
n
‍
a
~
1
j
=
∑
j
=
1
n
‍
a
1
j
>
0;
(2)
a
~
i
i
=
1
-
α
i
a
i
1
a
1
i
>
0;
(3)
ifi
≠
1,
(19)
a
~
i
i
-
∑
j
≠
i
‍
|
a
~
i
j
|
=
1
-
α
i
a
i
1
a
1
i
-
(
1
-
α
i
)
a
i
1
+
∑
j
≠
i
,
1
‍
(
a
i
j
-
α
i
a
i
1
)
a
1
j
=
(
∑
j
=
1
n
‍
a
i
j
-
2
a
i
1
)
-
α
i
(
2
-
∑
j
=
1
n
‍
a
1
j
)
a
i
1
>
0
.
It implies thatA
~
(
α
) is a diagonally dominant matrix; then it is an H-matrix with positive diagonal elements by Lemma 14.SinceA
~
(
α
) is an H-matrix, according to [8], we can solve the problem (5) using Algorithm 10, where A
~
(
α
)
=
M
i
-
N
i maybe an H-compatible splitting of matrix A
~
(
α
).Lemma 16 (see [6]).
Letx
* be the solution of (1), and y
k
,
i is the solution of (14); then
(20)
|
y
k
,
i
-
x
*
|
≤
〈
M
i
〉
-
1
|
N
i
|
|
x
*
-
x
k
|
.Similar to the proof in Theorem  2.1 in [8], we have the following convergence theorem.Theorem 17.
LetA be an M-matrix; the sequence {
x
k
} generated by Algorithm 10 converges to the solution of the problem (1).


## 5. Numerical Experiments

In this section, we give two numerical examples to show that the new methods are efficient. In the numerical experiments, the stop criterion is∥
x
k
+
1
-
x
k
∥
<
1
0
-
8. In the tables, MMS denotes Algorithm 10 with preconditioner, and GSOR denotes Algorithm 10, in which m
=
1.Example 1.
We consider a linear complementarity problem, whose coefficient matrix is(21)
A
=
(
1.0000
-
0.0301
-
0.1632
-
0.0280
-
0.1875
-
0.0189
-
0.1504
-
0.2652
-
0.1088
-
0.0926
1.0000
-
0.0382
-
0.1213
-
0.1520
-
0.1037
-
0.1835
-
0.1276
-
0.1509
-
0.1081
-
0.0901
1.0000
-
0.0965
-
0.0948
-
0.1823
-
0.0263
-
0.2096
-
0.1733
-
0.2045
-
0.1359
-
0.2263
1.0000
-
0.2379
-
0.0352
-
0.0117
-
0.0395
-
0.0929
-
0.2401
-
0.0800
-
0.0773
-
0.1115
1.0000
-
0.0511
-
0.1132
-
0.2230
-
0.0753
-
0.2245
-
0.2053
-
0.0534
-
0.0652
-
0.1381
1.0000
-
0.1080
-
0.0979
-
0.0898
-
0.1181
-
0.0751
-
0.0095
-
0.1791
-
0.1056
-
0.1595
1.0000
-
0.0879
-
0.1874
-
0.1773
-
0.0097
-
0.1900
-
0.1973
-
0.0891
-
0.0420
-
0.1320
1.0000
-
0.1504
-
0.1180
-
0.1129
-
0.1054
-
0.1694
-
0.0715
-
0.1706
-
0.0727
-
0.1085
1.0000
)
,
f
=
(
1
,
-
1,1
,
-
1,1
,
-
1,1
,
-
1,1
)
⊤
.
The results are shown as Table1.Table 1
Comparison of MMS and GSOR with unpreconditioned and preconditioned method.
Methods
Iterative steps
GSOR
Unpreconditioned
311
Preconditioned
267
MMS
Unpreconditioned
488
Preconditioned
397Example 2.
Let us consider the following problem:(22)
x
≥
0
,
A
x
-
q
≥
0
,
x
⊤
(
A
x
-
q
)
=
0
,
where A
=
(
B
-
I
-
I
B
-
I
⋱
⋱
⋱
-
I
B
-
I
-
I
B
), B
=
(
4
-
1
-
1
4
-
1
⋱
⋱
⋱
-
1
4
-
1
-
1
4
)
,
I is a unit matrix, q
=
(
q
i
)
i
=
1
n, and q
i
=
(
-
1
)
i
+
1.
Fora
i
1
≠
0, let us choose α
i
=
0.5; then A
(
α
) is an H-matrix. In Algorithm 10
A
~
(
α
)
=
M
i
-
N
i maybe an H-compatible splitting for each splitting. The corresponding results are shown in Tables 2 and 3.
An accelerated modulus-based accelerated overrelaxation (AMAOR) iteration method is presented by Zheng and Yin [11]. Same as in [11], we choose α
=
1.2, μ
=
4, and γ
=
2. In Example 2, A
=
A
+
μ
I. In Table 4, iter denotes iterative step and cputime denotes time (seconds). Table 4 shows that our preconditioned method MMS spends less time than the AMAOR.Table 2
Comparison of MMS and GSOR with preconditioned methods (M-matrix).
N * N
MMS
GSOR
Iterative steps
Iterative steps
32 * 32
18
30
64 * 64
20
31
128 * 128
21
33Table 3
Comparison of MMS and GSOR with preconditioned methods (H-matrix).
N * N
MMS
GSOR
Iterative steps
Iterative steps
32 * 32
21
30
64 * 64
21
31
128 * 128
22
33Table 4
Comparison of MMS and AMAOR.
N * N
MMS
AMAOR
10 * 10
cputime
0.51
0.42
iter
7
5
20 * 20
cputime
5.49
8.53
iter
7
6
30 * 30
cputime
24.88
52.76
iter
8
7
40 * 40
cputime
79.34
192.68
iter
8
7
50 * 50
cputime
205.94
589.48
iter
8
7
60 * 60
cputime
447.80
1402.20
iter
8
7



---

*Source: 519017-2014-06-23.xml*