In this paper, we first provide comparison results of preconditioned AOR methods with direct preconditioners
I
+
βL, I
+
βU
and
I
+
β
(
L
+
U
) for solving a linear system whose coefficient matrix is a large sparse irreducible Lmatrix, where
β
> 0. Next we propose how to find a near optimal parameter
β
for which Krylov subspace method with these direct preconditioners performs nearly best. Lastly numerical experiments are provided to compare the performance of preconditioned iterative methods and to illustrate the theoretical results.
AMS Mathematics Subject Classification : 65F10, 65F15.
1. Introduction
In this paper, we consider the following nonsingular linear system
where
A
= (
a_{ij}
) ∈ ℝ
^{n×n}
is a large sparse irreducible Lmatrix. Throughout the paper, we assume that
A
=
I
−
L
−
U
, where
I
is the identity matrix, and
L
and
U
are strictly lower triangular and strictly upper triangular matrices, espectively. Then the AOR iterative method
[3]
for solving the linear system (1) can be expressed as
where
x
_{0}
is an initial vector,
ω
and
r
are real parameters with
ω
≠ 0,
and
M_{r,ω}
=
ω
(
I
−
rL
)
^{−1}
. The
T_{r,ω}
is called an iteration matrix of the AOR iterative method.
In order to accelerate the convergence of iterative method for solving the linear system (1), the original linear system (1) is transformed into the following preconditioned linear system
where
P
, called a
preconditioner
, is a nonsingular matrix. Various types of preconditioners
P
, which are nonnegative matrices with unit diagonal entries, have been proposed by many researchers
[2
,
4
,
5
,
6
,
7
,
9
,
11
,
14
,
15
,
17]
. In this paper, we study comparison results of preconditioned iterative methods corresponding to direct preconditioners
P
=
P_{l}
=
I
+
βL, P
=
P_{u}
=
I
+
βU
and
P
=
P_{b}
=
I
+
β
(
L
+
U
), where
β
is a positive real number. Here, direct preconditioner means that the preconditioner can be constructed without any computational step. The preconditioner
P_{u}
was first introduced by Kotakemori et al
[4]
, and it has been studied further in
[9
,
11
,
15]
. The preconditioner
P_{l}
for
β
= 1 was first proposed by Usui et al
[11]
, so it is worth studying further
P_{l}
for
β
> 0 in this paper.
Let
A_{u}
=
P_{u}A
and
UL
= Γ +
E
+
F
, where Γ is a diagonal matrix,
E
is a strictly lower triangular matrix, and
F
is a strictly upper triangular matrix. Then, one obtains
where
D_{u}
=
I
−
β
Γ,
L_{u}
=
L
+
βE
, and
U_{u}
= (1 −
β
)
U
+
βU
^{2}
+
βF
.
Let
A_{l}
=
P_{l}A
and
LU
= Γ
_{1}
+
E
_{1}
+
F
_{1}
, where Γ
_{1}
is a diagonal matrix,
E
_{1}
is a strictly lower triangular matrix, and
F
_{1}
is a strictly upper triangular matrix. Then, one obtains
where
D_{l}
=
I
−
β
Γ
_{1}
,
L_{l}
= (1 −
β
)
L
+
βL
^{2}
+
βE
_{1}
, and
U_{l}
=
U
+
βF
_{1}
.
Recently, Wang and Song
[14]
studied convergence of the preconditioned AOR method with preconditioner
P_{b}
=
I
+
β
(
L
+
U
), where 0 <
β
≤ 1. Let
A_{b}
=
P_{b}A
.
Then, one obtains
where
D_{b}
=
I
−
β
Γ −
β
Γ
_{l}
,
L_{b}
= (1 −
β
)
L
+
βL
^{2}
+
βE
+
βE
_{1}
, and
U_{b}
= (1 −
β
)
U
+
βU
^{2}
+
βF
+
βF
_{1}
.
If we apply the AOR iterative method to the preconditioned linear system (4), then we get the
preconditioned AOR iterative method
whose iteration matrix is
Notice that the computational costs for constructing
A_{u}
,
A_{l}
and
A_{b}
will not be expensive since
A
is assumed to be a large sparse matrix.
The purpose of this paper is to provide performance comparison of preconditioned iterative methods with direct preconditioners
P_{l}
,
P_{u}
and
P_{b}
for solving a linear system whose coefficient matrix is a large sparse irreducible
L
matrix satisfying some weaker conditions than those used in the existing literature. This paper is organized as follows. In Section 2, we present some notation, definitions and preliminary results. In Section 3, we provide comparison results of preconditioned AOR methods with preconditioner
P_{u}
. In Section 4, we provide comparison results of preconditioned AOR methods with preconditioners
P_{l}
and
P_{b}
. In Section 5, we propose how to find a near optimal parameter
β
for which Krylov subspace method with the direct preconditioners
P_{l}
,
P_{u}
and
P_{b}
performs nearly best. In Section 6, numerical experiments are provided to compare the performance of preconditioned iterative methods and to illustrate the theoretical results in Sections 3 to 5. Lastly, some conclusions are drawn.
2. Preliminaries
A matrix
A
= (
a_{ij}
) ∈ ℝ
^{n×n}
is called a
Z

matrix
if
a_{ij}
≤ 0 for
i
≠
j
, an
L

matrix
if
A
is a >Zmatrix and
a_{ii}
> 0 for
i
= 1, 2, . . . ,
n
, and an
M

matrix
if
A
is a Zmatrix and
A
^{−1}
≥ 0. For a vector
x
∈ ℝ
^{n}
,
x
≥ 0 (
x
> 0) denotes that all components of
x
are nonnegative (positive). For two vectors
x, y
∈ ℝ
^{n}
,
x
≥
y
(
x
>
y
) means that
x
−
y
≥ 0 (
x
−
y
> 0). These definitions carry immediately over to matrices. For a square matrix
A, ρ
(
A
) denotes the spectral radius of
A
, and
A
is called
irreducible
if the directed graph of
A
is strongly connected
[13]
. Some useful results which we refer to later are provided below.
Theorem 2.1
(Varga
[13]
).
Let A
≥ 0
be an irreducible matrix. Then

(a)A has a positive eigenvalue equal to ρ(A).

(b)A has an eigenvector x> 0corresponding to ρ(A).

(c)ρ(A)is a simple eigenvalue of A.
Theorem 2.2
(Berman and Plemmons
[1]
).
Let A
≥ 0
be a matrix. Then the following hold.

(a)If Ax≥βx for a vector x≥ 0and x≠ 0,then ρ(A) ≥β.

(b)If Ax≤γx for a vector x> 0,then ρ(A) ≤γ.Moreover, if A is irreducible and if βx≤Ax≤γx, equality excluded, for a vector x≥ 0and x≠ 0,then β<ρ(A) <γ and x> 0.

(c)If βx 0,then β<ρ(A) <γ.
Theorem 2.3
(Li and Sun
[6]
).
Let A be an irreducible matrix, and let A
=
M
−
N be an M

splitting of A with N
≠ 0.
Then there exists a vector x
> 0
such that M
^{−1}
Nx
=
ρ
(
M
^{−1}
N
)
x and ρ
(
M
^{−1}
N
) > 0.
3. Comparison results for preconditioner Pu
We first provide a comparison result for the preconditioned GaussSeidel method with the preconditioner
P_{u}
.
Theorem 3.1.
Let A
= (
a_{ij}
) ∈ ℝ
^{n×n}
be an irreducible L

matrix. Suppose that
0 < (
UL
)
_{ii}
< 1
for all
1 ≤
i
≤
n
− 1,
where
Let T
= (
I
−
L
)
^{−1}
U and T_{u}
= (
D_{u}
−
L_{u}
)
^{−1}
U_{u}
,
where D_{u}, L_{u} and U_{u} are defined by (5). If
0 <
β
≤ 1,
then

(a)ρ(Tu) <ρ(T)if ρ(T) < 1.

(b)ρ(Tu) =ρ(T)if ρ(T) = 1.

(c)ρ(Tu) >ρ(T)if ρ(T) > 1.
Proof
. Since
A
is an
L
matrix,
D, L
and
U
are nonnegative. Since 0 <
β
≤ 1 and (
UL
)
_{ii}
< 1,
D_{u}
,
L_{u}
and
U_{u}
are nonnegative and thus
T_{u}
≥ 0. Since
A
= (
I
−
L
) −
U
is an Msplitting of
A
and
U
≠ 0, from Theorem 2.3 there exists a vector
x
> 0 such that
Tx
=
λx
, where
λ
=
ρ
(
T
). From
Tx
=
λx
, one easily obtains
Using (5) and (9),
Let
y
= (Γ +
E
+
λ
^{−1}
U
^{2}
)
x
. Since (
UL
)
_{ii}
> 0 for all 1 ≤
i
≤
n
− 1,
y
≥ 0 is a nonzero vector whose first (
n
−1) components are positive and last component is zero. Since
A
is irreducible,
L_{u}
=
L
+
βE
≥ 0 is a strictly lower triangular matrix whose last row vector is nonzero and thus (
D_{u}
−
L_{u}
)
^{−1}
y
is a positive vector. It follows that
T_{u}x
<
λx
from (10) if
λ
< 1. From Theorem 2.2,
ρ
(
T_{u}
) <
ρ
(
T
) < 1. For the cases of
λ
= 1 and
λ
> 1,
T_{u}x
=
λx
and
T_{u}x
>
λx
are obtained from (10), respectively. Hence, the theorem follows from Theorem 2.2.
We now provide a comparison result for the preconditioned AOR method with the preconditioner
P_{u}
.
Theorem 3.2.
Let A
= (
a_{ij}
) ∈ ℝ
^{n×n}
be an irreducible L

matrix. Suppose that
0 <
r
≤
ω
≤ 1 (
r
≠ 1)
and
0 < (
UL
)
_{ii}
< 1
for all
1 ≤
i
≤
n
− 1,
where
Let T_{r,ω} and T_{u,r,ω} be defined by (3) and (8), respectively. If
0 <
β
≤ 1,
then

(a)ρ(Tu,r,ω) <ρ(Tr,ω)if ρ(Tr,ω) < 1.

(b)ρ(Tu,r,ω) =ρ(Tr,ω)if ρ(Tr,ω) = 1.

(c)ρ(Tu,r,ω) >ρ(Tr,ω)if ρ(Tr,ω) > 1.
Proof
. Notice that
T_{r,ω}
can be expressed as
T_{r,ω}
= (1−
ω
)
I
+
ω
(1−
r
)
L
+
ωU
+
H
, where
H
is a nonnegative matrix. By assumptions, it can be seen that
T_{r,ω}
≥ 0 is irreducible and
T_{u,r,ω}x
≥ 0. From Theorem 2.1, there exists a vector
x
> 0 such that
T_{r,ω}x
=
λx
, where
λ
=
λ
(
T_{r,ω}x
). From
T_{r,ω}x
=
λx
, one easily obtains
Using (5) and (11),
Let
y
= (Γ +
rE
+
λ
^{−1}
((1 −
ω
)
U
+ (
ω
−
r
)
UL
+
ωU
^{2}
))
x
. Since 0 <
r
≤
ω
≤ 1 and (
UL
)
_{ii}
> 0 for all 1 ≤
i
≤
n
−1,
y
≥ 0 is a nonzero vector whose first (
n
−1) components are positive and last component is zero. Since
A
is irreducible and
r
≠ 0,
L_{u}
=
L
+
βE
≥ 0 is a strictly lower triangular matrix whose last row vector is nonzero and thus (
D_{u}
−
rL_{u}
)
^{−1}
y
is a positive vector. It follows that
T_{u,r,ω}x
<
λx
from (12) if
λ
< 1. From Theorem 2.2,
ρ
(
T_{u,r,ω}x
) <
ρ
T_{r,ω}
) < 1. For the cases of
λ
= 1 and
λ
> 1,
T_{u,r,ω}x
=
λx
and
T_{u,r,ω}x
>
λx
are obtained from (12), respectively. Hence, the theorem follows from Theorem 2.2.
If 0 <
β
< 1 in Theorem 3.2, the assumptions for (
UL
)
_{ii}
can be weakened.
Theorem 3.3.
Let A
= (
a_{ij}
) ∈ ℝ
^{n×n}
be an irreducible L

matrix. Suppose that
0 <
r
≤
ω
≤ 1 (
r
≠ 1), (
UL
)
_{ii}
< 1 (1 ≤
i
≤
n
− 1)
and
(
UL
)
_{ii}
> 0
for at least one i, where
Let T_{r,ω} and T_{u,r,ω} be defined by (3) and (8), respectively. If
0 <
β
< 1,
then

(a)ρ(Tu,r,ω) <ρ(Tr,ω)if ρ(Tr,ω) < 1.

(b)ρ(Tu,r,ω) =ρ(Tr,ω)if ρ(Tr,ω) = 1.

(c)ρ(Tu,r,ω) >ρ(Tr,ω)if ρ(Tr,ω) > 1.
Proof
. Since
A
is irreducible and
β
< 1,
A_{u}
is also irreducible. Hence it can be easily shown that both
T_{r,ω}
and
T_{u,r,ω}
are nonnegative and irreducible. From Theorem 2.1, there exists a vector
x
> 0 such that
T_{r,ω}x
=
λx
, where
λ
=
λ
(
T_{r,ω}
). From equation (12), one obtains
If
λ
< 1, then from (13)
T_{u,r,ω}x
≤
λx
and
T_{u,r,ω}x
≠
λx
. Since
T_{u,r,ω}
is irreducible, Theorem 2.2 implies that
ρ
(
T_{u,r,ω}
) <
ρ
(
T_{r,ω}
) < 1. For the cases of
λ
= 1 and
λ
> 1,
T_{u,r,ω}x
=
λx
and
T_{u,r,ω}x
≥
λx
(with
T_{u,r,ω}x
≠ =
λx
) are obtained from (13), respectively. Hence, the theorem follows from Theorem 2.2.
By combining Theorems 3.1 and 3.2, we can obtain the following theorem.
Theorem 3.4.
Let A
= (
a_{ij}
) ∈ ℝ
^{n×n}
be an irreducible L

matrix. Suppose that
0 <
r
≤
ω
≤ 1
and
0 < (
UL
)
_{ii}
< 1
for all
1 ≤
i
≤
n
 1,
where
Let T_{r,ω} and T_{u,r,ω} be defined by (3) and (8), respectively. If
0 <
β
< 1,
then

(a)ρ(Tu,r,ω) <ρ(Tr,ω)if ρ(Tr,ω) < 1.

(b)ρ(Tu,r,ω) =ρ(Tr,ω)if ρ(Tr,ω) = 1.

(c)ρ(Tu,r,ω) >ρ(Tr,ω)if ρ(Tr,ω) > 1.
Proof
. If
r
= 1, then
ω
= 1 and thus the theorem follows from Theorem 3.1. If
r
≠ 1, then the theorem follows from Theorem 3.2.
4. Comparison results for preconditioner Pland Pb
We first provide a comparison result for the preconditioned GaussSeide method with the preconditioner
P_{l}
.
Theorem 4.1.
Let A
= (
a_{ij}
) ∈ ℝ
^{n×n}
be an irreducible L

matrix. Suppose that
0 < (
LU
)
_{ii}
< 1
for all
2 ≤
i
≤
n, where
Let T
= (
I
−
L
)
^{−1}
U
and T_{l}
= (
D_{l}
−
L_{l}
)
^{−1}
U_{l}
,
where
D_{l}, L_{l}
and
U_{l}
are defined by (6). If
0 <
β
≤ 1,
then

(a)ρ(Tl) <ρ(T)if ρ(T) < 1.

(a)ρ(Tl) =ρ(T)if ρ(T) = 1.

(a)ρ(Tl) >ρ(T)if ρ(T) > 1.
Proof
. Since
A
is an
L
matrix,
D, L
and
U
are nonnegative. Since 0 <
β
≤ 1 and (
LU
)
_{ii}
< 1,
D_{l}, L_{l}
and
U_{l}
are nonnegative and thus
T_{l}
≥ 0. Since
A
= (
I
−
L
)−
U
is an Msplitting of
A
and
U
≠ 0, from Theorem 2.3 there exists a vector
x
> 0 such that
Tx
=
λx
, where
λ
=
ρ
(
T
). From
Tx
=
λx
, one easily obtains
Using (6) and (14),
Let
y
= (Γ
_{1}
+
E
_{1}
)x. Since (
LU
)
_{ii}
> 0 for all 2 ≤
i
≤
n, y
≥ 0 is a nonzero vector whose first component is zero and last (
n
− 1) components are positive. Thus
z
= (
D_{l}
−
L_{l}
)
^{−1}
y
≥ 0 is also a nonzero vector whose first component is zero and last (
n
− 1) components are positive. Let
where
z
_{2}
> 0,
T
_{12}
∈ ℝ
^{1×(n−1)}
and
T
_{12}
∈ ℝ
^{(n−1)×(n−1)}
. From (15) and (16),
Since
z
_{2}
> 0,
T
_{22}
x
_{2}
<
λx
_{2}
from (17) if
λ
< 1. From Theorem 2.2,
ρ
(
T
_{22}
) <
ρ
(
T
) < 1. Since
ρ
(
T_{l}
) =
ρ
(
T
_{22}
),
ρ
(
T_{l}
) <
ρ
(
T
) is obtained. For the cases of
λ
= 1 and
λ
> 1,
T
_{22}
x
_{2}
=
λx
_{2}
and
T
_{22}
x
_{2}
>
λx
_{2}
are obtained from (17), respectively. Hence, the theorem follows from Theorem 2.2.
We now provide a comparison result for the preconditioned AOR method with the preconditioner
P_{l}
.
Theorem 4.2.
Let A
= (
a_{ij}
) ∈ ℝ
^{n×n}
be an irreducible L

matrix. Suppose that
0 ≤
r,ω
≤ 1 (
ω
≠ 0,
r
≠ 1)
and
(
LU
)
_{ii}
< 1
for all
2 ≤ 2 ≤
i
≤
n, where
Let T_{r,ω} and T_{l,r,ω} be defined by (3) and (8), respectively. If
0 <
β
< 1,
then

(a)ρ(Tl,r,ω) <ρ(Tr,ω)if ρ(Tr,ω) < 1.

(b)ρ(Tl,r,ω) =ρ(Tr,ω)if ρ(Tr,ω) = 1.

(c)ρ(Tl,r,ω) >ρ(Tr,ω)if ρ(Tr,ω) > 1.
Proof
. By simple calculation, one can obtain
where
H
and
H_{l}
are nonnegative matrices. Since 0 ≤
r, ω
≤ 1 (
ω
≠ 0,
r
≠ 1) and 0 <
β
< 1, it can be easily shown from (18) that both
T_{r, ω}
and
T_{l,r,ω}
are nonnegative and irreducible. Hence, there exists a vector
x
> 0 such that
T_{r,ω}x
=
λx
, where
λ
=
ρ
(
T_{r,ω}
). Using (6) and
T_{r,ω}x
=
λx
, one obtains
Let
y
= (Γ
_{1}
+
rE
_{1}
+ (1 −
r
)
L
)
x
. Since
A
is irreducible and
r
≠ 1,
y
≥ 0 is a nonzero vector whose first component is zero. If
λ
< 1, then from (19)
T_{l,r,ω}x
≤
λx
and
T_{l,r,ω}x
≠
λx
. Since
T_{l,r,ω}
is irreducible, Theorem 2.2 implies that
ρ
(
T_{l,r,ω}
) <
ρ
(
T_{r,ω}
) < 1. For the cases of
λ
= 1 and
λ
> 1,
T_{l,r,ω}x
=
λx
and
T_{l,r,ω}x
≥
λx
(with
T_{l,r,ω}x
≠
λx
) are obtained from (13), respectively. Hence, the theorem follows from Theorem 2.2.
Notice that
Theorem 4.2 for preconditioner P_{l} does not require the assumptions r
≤
ω and
(
LU
)
_{ii}
> 0
as compared with Theorem 3.2 for preconditioner P_{u}
. If
β
= 1, the strict inequalities in Theorem 4.2 may not hold and only inequalities are guaranteed.
Lemma 4.3.
Let A
= (
a_{ij}
) ∈ ℝ
^{n×n}
be an L

matrix. If A
=
I
−
L
−
U is an Mmatrix, then
(
LU
)
_{ii}
< 1
and
(
UL
)
_{ii}
< 1
for all i
= 1, 2, . . . ,
n
.
Proof
. It is easy to show that (
I
+
U
)
A
and (
I
+
L
)
A
are Zmatrices. Since
A
is an Mmatrix, there exists a vector
x
> 0 such that
Ax
> 0. Thus (
I
+
L
)
Ax
> 0 and (
I
+
U
)
Ax
> 0. It follows that (
I
+
L
)
A
and (
I
+
U
)
A
are Mmatrices and so all diagonal components of (
I
+
L
)
A
and (
I
+
U
)
A
are positive. Hence 1 − (
LU
)
_{ii}
> 0 and 1 − (
UL
)
_{ii}
> 0 for all
i
= 1, 2, . . . ,
n
, which completes the proof.
From Lemma 4.3, it can be seen that if
A
is an Mmatrix, all theorems in Sections 3 and 4 do not require the assumptions (
LU
)
_{ii}
< 1 or (
UL
)
_{ii}
< 1. Lastly, we provide a comparison result of the preconditioned AOR method for preconditioner
P_{b}
.
Lemma 4.4
(
[8]
).
Suppose that A
_{1}
=
M
_{1}
−
N
_{1}
and
A
_{2}
=
M
_{2}
−
N
_{1}
are weak regular splittings of the monotone matrices
A
_{1}
and
A
_{2}
,
respectively, such that
If there exists a positive vector x such that
0 ≤
A
_{1}
x
≤
A
_{2}
x
,
then for the monotonic norm associated with x
In particular, if
has a positive Perron vector, then
Theorem 4.5.
Let A be an irreducible M

matrix. Suppose that
0 ≤
r
≤
ω
≤ 1 (
ω
≠ 0).
Let
T_{r,ω}
,
T_{l,r,ω}
and
T_{b,r,ω}
be defined by (3) and (8), respectively. If
0 <
β
≤ 1,
then
Proof
. Since
ρ
(
T_{l,r,ω}
) ≤
ρ
(
T_{r,ω}
) < 1 was shown in
[14]
, it suffices to show
ρ
(
T_{b,r,ω}
) ≤
ρ
(
T_{l,r,ω}
). Since
A
is an Mmatrix and 0 <
β
≤ 1, there exists a vector
x
> 0 such that
Ax
> 0, and
P_{l}A
and
P_{b}A
are also Zmatrices. It follows that
P_{l}A
and
P_{b}A
are Mmatrices. Notice that
P_{b}Ax
≥
P_{l}Ax
> 0 and (
D_{b}
−
rL_{b}
)
^{−1}
≥ (
D_{l}
−
rL_{l}
)
^{−1}
. Since
A
is irreducible and 0 <
β
< 1,
P_{l}A
is also irreducible. Since
is an M splitting of
P_{l}A
with
U_{l}
≠ 0,
T_{l,r,ω}
has a positive Perron vector from Theorem 2.3. Using Lemma 4.4,
ρ
(
T_{b,r,ω}
) ≤
ρ
(
T_{l,r,ω}
) for 0 <
β
< 1. By continuity of spectral radius,
ρ
(
T_{b,r,ω}
) ≤
ρ
(
T_{l,r,ω}
) is also true for
β
= 1. Therefore, the proof is complete.
5. A near optimal parameter β for Krylov subspace method
In this section, we propose how to find a near optimal parameter
β
for which Krylov subspace method with preconditioners
P_{l}, P_{u}
and
P_{b}
performs nearly best. Before proceeding to the analysis for finding a near optimal parameter
β
, we define the following notations. For
X
and
Y
in ℝ
^{n×n}
, we define the inner product ⟨
X, Y
⟩
_{F}
= tr(
X^{T}Y
), where tr(
Z
) denotes the trace of the square matrix
Z
and
X^{T}
denotes the transpose of the matrix
X
. The associated norm is the wellknown Frobenius norm denoted by ∥ · ∥
_{F}
.
If
P
is a good preconditioner for Krylov subspace method, then
PA
is close to the identity matrix
I
. Thus it would be a good idea to determine a value
β
such that ∥
PA
−
I
∥
_{F}
is minimized, where
P
is
P_{l}, P_{u}
or
P_{b}
. We call such a value
β
a near optimal parameter for the preconditioned Krylov subspace method. We first provide a near optimal parameter
β
for the preconditioner
P
=
P_{l}
.
Theorem 5.1.
Let A
=
I
−
L
−
U
be a large sparse nonsingular matrix, and let P_{l}
=
I
+
βL be a preconditioner for Krylov subspace method. Then, a near optimal parameter β is given by
Proof
. Note that (
I
+
βL
)
A
−
I
=
βLA
−(
L
+
U
). By definition of the Frobenius norm, one obtains
The equation (20) is a quadratic equation in
β
, so the minimum occurs when
Hence the proof is complete.
Similarly to the proof of Theorem 5.1, one can obtain a near optimal parameter
β
for the preconditioner
P
=
P_{u}
.
Theorem 5.2.
Let A
=
I
−
L
−
U be a large sparse nonsingular matrix, and let P_{u}
=
I
+
βU be a preconditioner for Krylov subspace method. Then, a near optimal parameter β is given by
Lastly, we provide a near optimal parameter
β
for the preconditioner
P
=
P_{b}
.
Theorem 5.3.
Let A
=
I
−
L
−
U
∈ ℝ
^{n×n}
be a large sparse nonsingular matrix, and let
P_{b}
=
I
+
β
(
L
+
U
)
be a preconditioner for Krylov subspace method. Then, a near optimal parameter β is given by
Proof
. Note that (
I
+
β
(
L
+
U
))
A
−
I
= (
β
−1)(
L
+
U
)−
β
(
L
+
U
)
^{2}
. By property of the Frobenius norm, one obtains
From (21), it is sufficient to minimize ∥(
β
−1)
I
−
β
(
L
+
U
)∥
_{F}
in order to determine a near optimal parameter
β
. Since tr(
L
+
U
) = 0, one obtains
The equation (22) is a quadratic equation in
β
, so the minimum occurs when
Hence the proof is complete.
6. Numerical experiments
In this section, we provide numerical experiments to compare the performance of preconditioned iterative methods and to illustrate the theoretical results obtained in Sections 3 to 5. All numerical experiments are carried out on a PC equipped with Intel Core i54570 3.2GHz CPU and 8GB RAM using MATLAB R2013a. The preconditioned iterative methods used for numerical experiments are the preconditioned AOR method and the right preconditioned BiCGSTAB method
[10
,
12]
.
In
Table 3
,
Iter
denotes the number of iteration steps,
CPU
denotes the elapsed CPU time in seconds,
P
denotes the preconditioner to be used, ILU(0) denotes the incomplete factorization preconditioner without fillins, and
β
denotes a near optimal value computed by the formula given in Section 5. For numerical tests using the right preconditioned BiCGSTAB, all nonzero elements of sparse matrices are stored using sparse storage format which saves a lot of CPU time, the initial vectors are set to the zero vector, and the iterations are terminated if the current approximation
x_{k}
satisfies
where ∥·∥
_{2}
refers to
L
_{2}
norm.
Example 6.1.
Consider the two dimensional convectiondiffusion equation
[15]
with the Dirichlet boundary condition on
∂
Ω which denotes the boundary of Ω. When the central difference scheme on a uniform grid with
m
×
m
interior node is applied to the discretization of the equation (23), we can obtain a linear system
Ax
=
b
whose coefficient matrix
A
∈ ℝ
^{n×n}
is of the form
where
n
=
m
^{2}
,
I_{m}
denotes the identity matrix of order
m
, ⊗ denotes the Kronecker product,
are
m
×
m
tridiagonal matrices with the step size
It is clear that this matrix
A
is an irreducible nonsymmetric
L
matrix. Numerical results of the preconditioned AOR method for
n
= 50
^{2}
= 2500 are provided in
Table 1
, and numerical results of the right preconditioned BiCGSTAB method for various values of
n
are listed in
Table 3
.
Example 6.2.
Consider the two dimensional Poisson’s equation
with the Dirichlet boundary condition on
∂
Ω. When the central difference scheme on a uniform grid with
m
×
m
interior node is applied to the discretization of the equation (24), we obtain a linear system
Ax
=
b
whose coefficient matrix
A
∈ ℝ
^{n×n}
is given by
where
n
=
m
^{2}
,
are
m
×
m
tridiagonal matrices. Note that this matrix
A
is an irreducible symmetric
L
matrix. Numerical results of the preconditioned AOR method for
n
= 50
^{2}
= 2500 are provided in
Table 2
.
In
Figure 1
, we depict the eigenvalue distributions of the preconditioned matrices corresponding to 6 different preconditioners for Examples 6.1 when
n
= 30
^{2}
. From
Figure 1
, it can be seen that eigenvalues of
P_{b}A
are more clustered than those of any other preconditioners. From
Tables 1
and
2
, it can be seen that
ρ
(
T_{l,r,ω}
) <
ρ
(
T_{r,ω}
) does not hold for
ω
> 1 and
r
> 1, and
ρ
(
T_{b,r,ω}
) ≤
ρ
(
T_{l,r,ω}
) does not hold for
β
> 1. For test problems used in this paper, the preconditioner
P_{u}
yields better optimal performance than other preconditioners
P_{l}
and
P_{b}
, and the optimal values of
β
,
ω
and
r
for the preconditioned AOR method with
P_{u}
are greater than or equal to 1 (see
Tables 1
to
2
). In other words,
ω
=
r
is around 1.3 and
β
= 1 for Examples 6.1 and 6.2. Further research is required to study how to find optimal or near optimal values of
β
,
ω
and
r
for the preconditioned AOR method.
From
Table 3
, it can be seen that the preconditioner
P_{b}
with a near optimal parameter
β
performs much better than the ILU(0) preconditioner which is one of the powerful preconditioners that are commonly used. It can be also seen that the preconditioners
P_{l}
and
P_{u}
with near optimal parameters
β
perform better than the preconditioner (
I
−
L
)
^{−1}
. The performance of BiCGSTAB with preconditioner (
I
−
U
)
^{−1}
is not provided here since its performance is similar to that with the preconditioner (
I
−
L
)
^{−1}
. Notice that a near optimal parameter
β
proposed in Section 5 can be easily computed by MATLAB.
Numerical results forρ(Tr,ω),ρ(Tu,r,ω),ρ(Tl,r,ω) andρ(Tb,r,ω) with various values ofβ,randωfor Example 6.1.
Numerical results for ρ(T_{r,ω}), ρ(T_{u,r,ω}), ρ(T_{l,r,ω}) and ρ(T_{b,r,ω}) with various values of β, r and ω for Example 6.1.
Numerical results forρ(Tr,ω),ρ(Tu,r,ω),ρ(Tl,r,ω) andρ(Tb,r,ω) with various values ofβ,randωfor Example 6.2.
Numerical results for ρ(T_{r,ω}), ρ(T_{u,r,ω}), ρ(T_{l,r,ω}) and ρ(T_{b,r,ω}) with various values of β, r and ω for Example 6.2.
Spectra of the preconditioned matrices corresponding to several preconditioners for Example 6.1 when n = 30^{2}
Numerical results of preconditioned BiCGSTAB for Example 6.1.
Numerical results of preconditioned BiCGSTAB for Example 6.1.
7. Conclusions
In this paper, we provided comparison results of preconditioned AOR methods with direct preconditioners
P_{l}
,
P_{u}
and
P_{b}
for solving a linear system whose coefficient matrix is a large sparse irreducible Lmatrix, which holds under some weaker conditions than those used in the existing literature. These theoretical results are in good agreement with the numerical results (see
Tables 1
and
2
). However, further research is required to study how to find optimal or near optimal values of
β
,
ω
and
r
for the preconditioned AOR method.
We also proposed how to find a near optimal parameter
β
for which Krylov subspace method with preconditioners
P_{l}
,
P_{u}
and
P_{b}
performs nearly best. Numerical experiments showed that BiCGSTAB with the preconditioner
P_{b}
with a near optimal parameter
β
performs much better than the ILU(0) preconditioner which is one of the powerful preconditioners that are commonly used. It was also seen that BiCGSTAB with the preconditioners
P_{l}
and
P_{u}
with near optimal parameters
β
perform better than the preconditioner (
I
−
L
)
^{−1}
(see
Table 3
). Notice that a near optimal parameter
β
proposed in Section 5 can be easily computed by MATLAB.
BIO
Jae Heon Yun received M.Sc. from Kyungpook National University, and Ph.D. from Iowa State University. He is currently a professor at Chungbuk National University since 1991. His research interests are computational mathematics and preconditioned iterative method.
Department of Mathematics, Chungbuk National University, Cheongju 361763, Korea.
email: gmjae@chungbuk.ac.kr
Hyo Jin Lim is a graduate student in Chungbuk National University. Her research interests are computational mathematics, iterative methods for solving linear and nonlinear equations.
Department of Mathematics, Chungbuk National University, Cheongju, 361763, Korea.
email: jellya@naver.com
Kyoum Sun Kim is a graduate student in Chungbuk National University. Her research interests are computational mathematics, new homotopy methods for solving functional equations.
Department of Mathematics, Chungbuk National University, Cheongju, 361763, Korea.
email: giunsun@naver.com
Berman A.
,
Plemmoms R.J.
1994
Nonnegative matrices in the mathematical sciences
SIAM
Philadelphia, PA
Gunawardena A.
,
Jain S.
,
Snyder L.
(1991)
Modified iterative methods for consistent linear systems
Linear Algebra Appl.
154
(156)
123 
143
DOI : 10.1016/00243795(91)903768
Neumann M.
,
Plemmons R.J.
(1987)
Convergence of parallel multisplitting iterative methods for Mmatrices
Linear Algebra Appl.
88/89
559 
573
DOI : 10.1016/00243795(87)90125X
Ozban A.Y.
(2002)
On accelerated iterative methods for the solution of systems of linear equations
Intern. J. Computer Math.
79
765 
773
DOI : 10.1080/00207160211290
Saad Y.
1996
Iterative methods for sparse linear systems
PWS Publishing Company
Boston
van der Vorst H.A.
(1992)
BiCGSTAB: A fast and smoothly converging variant of BiCG for the solution of nonsymmetric linear systems.
SIAM J. Sci. Statist. Comput
13
631 
644
DOI : 10.1137/0913035
Varga R.S.
2000
Matrix iterative analysis
Springer
Berlin
Young D.M.
1971
Iterative solution of large linear systems
Academic Press
New York