# Spectral Properties of the Iteration Matrix of the HSS Method for Saddle Point Problem

Authors: Qun-Fa Cui; Cui-Xia Li; Shi-Liang Wu
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

We discuss spectral properties of the iteration matrix of the HSS method for saddle point problems and derive estimates for the region containing both the nonreal and real eigenvalues of the iteration matrix of the HSS method for saddle point problems.


---

## Body

## 1. Introduction

Consider the following saddle point problem:(1)
𝒜
x
≡
[
A
B
T
-
B
0
]
[
u
v
]
=
[
f
-
g
]
≡
b
,
with symmetric positive definite A
∈
ℝ
n
×
n and B
∈
ℝ
m
×
n with rank (
B
)
=
m
≤
n. Without loss of generality, we assume that the coefficient matrix of (1) is nonsingular so that (1) has a unique solution. Systems of the form (1) arise in a variety of scientific and engineering applications, such as linear elasticity, fluid dynamics, electromagnetics, and constrained quadratic programming. One can see [1] for more applications and numerical solution techniques of (1).Recently, based on the Hermitian and skew-Hermitian splitting of𝒜: 𝒜
=
H
+
S, where
(2)
H
=
[
A
0
0
0
]
,
S
=
[
0
B
T
-
B
0
]
,
the HSS method [2] has been extended by Benzi and Golub [3] to solve the saddle point problem (1) and it is as follows.The HSS Method. Let x
(
0
)
∈
ℂ
n be an arbitrary initial guess. For k
=
0,1
,
2
,
… until the sequence of iterates {
x
(
k
)
}
k
=
0
∞ converges, compute the next iterate x
(
k
+
1
) according to the following procedure:
(3)
(
α
I
+
H
)
x
(
k
+
(
1
/
2
)
)
=
(
α
I
-
S
)
x
(
k
)
+
b
,
(
α
I
+
S
)
x
(
k
+
1
)
=
(
α
I
-
H
)
x
(
k
+
(
1
/
2
)
)
+
b
,
where α is a given positive constant.By eliminating the intermediate vectorx
(
k
+
(
1
/
2
)
), we obtain the following iteration in fixed point form as
(4)
x
(
k
+
1
)
=
M
α
x
(
k
)
+
N
α
b
,
k
=
0,1
,
2
,
…
,
where M
α
=
(
α
I
+
S
)
-
1
(
α
I
-
H
)
(
α
I
+
H
)
-
1
(
α
I
-
S
) and N
α
=
2
α
(
α
I
+
S
)
-
1
(
α
I
+
H
)
-
1. Obviously, M
α is the iteration matrix of the HSS iteration method.In addition, if we introduce matrices(5)
B
α
=
1
2
α
(
α
I
+
H
)
(
α
I
+
S
)
,
C
α

=

1
2
α
(
α
I
-
H
)
(
α
I
-
S
)
,
then 𝒜
=
B
α
-
C
α and M
α
=
B
α
-
1
C
α. Therefore, one can readily verify that the HSS method is also induced by the matrix splitting 𝒜
=
B
α
-
C
α.The following theorem established in [3] describes the convergence property of the HSS method.Theorem 1 (see [3]).
Consider problem (1) and assume that A is positive real and B has full rank. Then the iteration (3) is unconditionally convergent; that is, ρ
(
M
α
)
<
1 for all α
>
0.In fact, one can see [4] for a comprehensive survey on the HSS method. As is known, the iteration method (3) converges to the unique solution of the linear system (1) if and only if the spectral radius ρ
(
M
α
) of the iteration matrix M
α is less than 1. The spectral radius of the iteration matrix is decisive for the convergence and stability, and the smaller it is, the faster the iteration method converges when the spectral radius is less than 1. In this paper, we will discuss the spectral properties of the iteration matrix M
α of the HSS method for saddle point problems and derive estimates for the region containing both the nonreal and real eigenvalues of the iteration matrix M
α of the HSS method for saddle point problems.Throughout the paper,B
T denotes the transpose of a matrix B and u
* indicates its transposed conjugate. λ
n, λ
1
≥
0 are the smallest and largest eigenvalues of symmetric positive semidefinite A, respectively. We denote by σ
1
,
…
,
σ
m the decreasing ordered singular values of B. ℜ
(
θ
) and ℑ
(
θ
), respectively, denote the real part and imaginary part of θ
∈
ℂ.


## 2. Main Results

In fact, the iteration matrixM
α can be written as
(6)
M
α
′
=
(
α
I
+
S
)
-
1
(
α
I
+
H
)
-
1
(
α
I
-
H
)
(
α
I
-
S
)
.
Therefore, we are just thinking about the spectral properties of matrix M
α
′. That is, we consider the following eigenvalue problem:
(7)
(
α
I
-
H
)
(
α
I
-
S
)
x
=
λ
(
α
I
+
H
)
(
α
I
+
S
)
x
,
where (
λ
,
x
) is any eigenpair of M
α
′. From (7), we have
(8)
(
1
-
λ
)
(
α
2
I
+
H
S
)
x
=
(
1
+
λ
)
α
𝒜
x
.
Note that ρ
(
M
α
)
<
1 for all α
>
0. From (8), we have
(9)
𝒜
x
=
(
1
-
λ
)
α
(
1
+
λ
)
(
I
+
1
α
2
H
S
)
x
.
Let
(10)
θ
=
(
1
-
λ
)
α
(
1
+
λ
)
,
from
which
λ
=
α
-
θ
α
+
θ
=
1
-
2
θ
α
+
θ
.
Obviously, θ
≠
0. Therefore, (9) can be written as
(11)
(
H
+
S
)
x
=
θ
(
I
+
1
α
2
H
S
)
x
.
That is,
(12)
[
A
B
T
-
B
0
]
x
=
θ
[
I
1
α
2
A
B
T
0
I
]
x
,
which is equal to
(13)
ℬ
x
≡
[
A
+
1
α
2
A
B
T
B
B
T
-
B
0
]
x
=
θ
x
.
It is easy to see that the two eigenproblems (7) and (13) have the same eigenvectors, while the eigenvalues are related by (10). Obviously, if the spectrum of ℬ can be obtained, then the spectrum of (7) can be also derived.From [5, Lemma  2.1], we have the following result.Lemma 2.
Assume thatA is symmetric and positive definite and K
=
I
+
(
1
/
α
2
)
B
T
B. For each eigenpair (
λ
,
x
) of (7), all the eigenvalues λ of the iteration matrix M
α are λ
=
(
α
-
θ
)
/
(
α
+
θ
), where θ
≠
0 satisfies the following. (1)
Ifℑ
(
θ
)
≠
0, then
(14)
ℜ
(
θ
)
=
1
2
u
*
K
A
K
u
u
*
K
u
,
|
θ
|
2
=
u
*
K
B
T
B
u
u
*
K
u
.
(2)
Ifℑ
(
θ
)
=
0, then
(15)
min
⁡
{
λ
n
,
α
2
σ
m
2
λ
1
(
α
2
+
σ
m
2
)
}
≤
θ
≤
λ
1
(
1
+
σ
1
2
α
2
)
.From (14), it is easy to verify that 0
≤
|
θ
|
2
≤
σ
1
2, and if m
=
n, then λ
n
(
1
+
(
σ
m
2
/
α
2
)
)
≤
2
ℜ
(
θ
)
≤
λ
1
(
1
+
(
σ
1
2
/
α
2
)
), or if m
<
n, then λ
n
≤
2
ℜ
(
θ
)
≤
λ
1
(
1
+
(
σ
1
2
/
α
2
)
).In the sequel, we will present the main result, that is, Theorem3.Theorem 3.
Under the hypotheses and notation of Lemma2, all the eigenvalues λ of the iteration matrix M
α are such that the following hold. (1)
Ifℑ
(
θ
)
≠
0, then
(16)
|
λ
|
2
≤
1
-
2
λ
n
(
1
+
(
σ
m
2
/
α
2
)
)
α
α
2
+
λ
n
(
1
+
(
σ
m
2
/
α
2
)
)
α
+
σ
1
2
.
(2)
Ifℑ
(
θ
)
=
0, then
(17)
α
-
λ
1
(
1
+
(
σ
1
2
/
α
2
)
)
α
+
λ
1
(
1
+
(
σ
1
2
/
α
2
)
)
≤
λ
≤
α
-
min
⁡
⁡
{
λ
n
,
α
2
σ
m
2
/
λ
1
(
α
2
+
σ
m
2
)
}
α
+
min
⁡
⁡
{
λ
n
,
α
2
σ
m
2
/
λ
1
(
α
2
+
σ
m
2
)
}
.Proof.
Letx
=
[
u
*
,
v
*
]
* be an eigenvector with respect to θ. From (13), we get
(18)
A
K
u
+
B
T
v
=
θ
u
,
(19)
-
B
u
=
θ
v
.
By (19), we get v
=
-
θ
-
1
B
u. Substituting it into (18) yields
(20)
θ
A
K
u
-
B
T
B
u
=
θ
2
u
.
Multiplying (20) from the left by u
*
K, we arrive at
(21)
θ
2
u
*
K
u
-
θ
u
*
K
A
K
u
+
u
*
K
B
T
B
u
=
0
.
Let θ
=
ℜ
(
θ
)
+
i
ℑ
(
θ
). For symmetric matrix A, the quadratic equation (21) has real coefficients so that its roots are given by
(22)
θ
±
=
1
2
u
*
K
A
K
u
u
*
K
u
±
1
4
(
u
*
K
A
K
u
u
*
K
u
)
2
-
u
*
K
B
T
B
u
u
*
K
u
.
Eigenvalues with nonzero imaginary part arise if the discriminant is negative.
Ifℑ
(
θ
)
≠
0, from (14) we have
(23)
2
ℜ
(
θ
)
=
u
*
K
A
K
u
u
*
K
u
>
0
,
|
θ
|
2
=
u
*
K
B
T
B
u
u
*
K
u
.
In this case, from (23) we have
(24)
|
λ
|
2
=
α
-
θ
α
+
θ
·
α
-
θ
α
+
θ
¯
=
α
-
θ
α
+
θ
·
α
-
θ
-
α
+
θ
-
=
α
2
-
2
ℜ
(
θ
)
α
+
|
θ
|
2
α
2
+
2
ℜ
(
θ
)
α
+
|
θ
|
2
(
<


1
)
=
1
-
2
2
ℜ
(
θ
)
α
α
2
+
2
ℜ
(
θ
)
α
+
|
θ
|
2
=
1

-

2
(
u
*
K
A
K
u
/
u
*
K
u
)
α
α
2

+

(
u
*
K
A
K
u
/
u
*
K
u
)
α

+

(
u
*
K
B
T
B
u
/
u
*
K
u
)
≤
1
-
2
λ
n
(
1
+
(
σ
m
2
/
α
2
)
)
α
α
2
+
λ
n
(
1
+
(
σ
m
2
/
α
2
)
)
α
+
σ
1
2
.
Ifℑ
(
θ
)
=
0, then θ
>
0 from (22). Combing (10) with (15), we have
(25)
min
⁡
{
λ
n
,
α
2
σ
m
2
λ
1
(
α
2
+
σ
m
2
)
}
≤
(
1
-
λ
)
α
(
1
+
λ
)
≤
λ
1
(
1
+
σ
1
2
α
2
)
.
That is,
(26)
1
α
min
⁡
{
λ
n
,
α
2
σ
m
2
λ
1
(
α
2
+
σ
m
2
)
}
≤
1
-
λ
1
+
λ
≤
1
α
λ
1
(
1
+
σ
1
2
α
2
)
.
Further, we have
(27)
-
1
α
λ
1
(
1
+
σ
1
2
α
2
)
≤
λ
-
1
λ
+
1
≤
-
1
α
min
⁡
{
λ
n
,
α
2
σ
m
2
λ
1
(
α
2
+
σ
m
2
)
}
.
Therefore,
(28)
-
1
α
λ
1
(
1
+
σ
1
2
α
2
)
≤
1
-
2
λ
+
1
≤
-
1
α
min
⁡
{
λ
n
,
α
2
σ
m
2
λ
1
(
α
2
+
σ
m
2
)
}
.
So, we have
(29)
1
α
min
⁡
{
λ
n
,
α
2
σ
m
2
λ
1
(
α
2
+
σ
m
2
)
}
≤
2
λ
+
1
-
1
≤
1
α
λ
1
(
1
+
σ
1
2
α
2
)
.
That is,
(30)
1
+
1
α
min
⁡
{
λ
n
,
α
2
σ
m
2
λ
1
(
α
2
+
σ
m
2
)
}
≤
2
λ
+
1
≤
1
+
1
α
λ
1
(
1
+
σ
1
2
α
2
)
.
By the simple computations, we have
(31)
1
1
+
(
1
/
α
)
λ
1
(
1
+
(
σ
1
2
/
α
2
)
)
≤
λ
+
1
2
≤
1
1
+
(
1
/
α
)
min
⁡
{
λ
n
,
α
2
σ
m
2
/
λ
1
(
α
2
+
σ
m
2
)
}
.
Obviously, we also have
(32)
2
1
+
(
1
/
α
)
λ
1
(
1
+
(
σ
1
2
/
α
2
)
)
≤
λ
+
1
≤
2
1
+
(
1
/
α
)
min
⁡
{
λ
n
,
α
2
σ
m
2
/
λ
1
(
α
2
+
σ
m
2
)
}
.
That is to say,
(33)
1
-
(
1
/
α
)
λ
1
(
1
+
(
σ
1
2
/
α
2
)
)
1
+
(
1
/
α
)
λ
1
(
1
+
(
σ
1
2
/
α
2
)
)
≤
λ
≤
1
-
(
1
/
α
)
min
⁡
⁡
{
λ
n
,
α
2
σ
m
2
/
λ
1
(
α
2
+
σ
m
2
)
}
1
+
(
1
/
α
)
min
⁡
⁡
{
λ
n
,
α
2
σ
m
2
/
λ
1
(
α
2
+
σ
m
2
)
}
.


## 3. Numerical Experiments

In this section, we consider the following two examples to illustrate the above result.Example 1 (see [6–9]).
Consider the following classic incompressible steady Stokes problem:(34)
-
Δ
u
+
grad
p
=
f
,
in
Ω
,
-
div
⁡
u
=
0
,
in
Ω
,
with suitable boundary condition on ∂
Ω. That is to say, the boundary conditions are u
x
=
u
y
=
0 on the three fixed walls (x
=
0, x
=
1, and y
=
0) and u
x
=
1, u
y
=
0 on the moving wall (y
=
1). The test problem is a “leaky” two-dimensional lid-driven cavity problem in square (0
≤
x
≤
1, 0
≤
y
≤
1). Using the IFISS software [10] to discretize (34), the finite element subdivision is based on 8
×
8 and 16
×
16 uniform grids of square elements and the mixed finite element used is the bilinear-constant velocity pressure: Q
1
-
P
0 pair with stabilization (the stabilization parameter is zero). The coefficient matrix generated by this package is singular because B corresponding to the discrete divergence operator is rank deficient. The nonsingular matrix 𝒜 is obtained by dropping the first two rows of B and the first two rows and columns of matrix C. Note that matrix C is a null matrix, which is the corresponding (2,2) block of (1). In this case, n
=
162 and  m
=
62 correspond to 8
×
8, and n
=
578 and m
=
254 correspond to 16
×
16. For the Stokes problem, the (1, 1) block of the coefficient matrix corresponding to the discretization of the conservative term is symmetric positive definite.
By calculations, the values given in Tables1 and 2 are obtained, which are to verify the results of Theorem 3. In Tables 1 and 2, L
min
⁡
,
U
max
⁡, respectively, denote the lower and upper bounds of all the eigenvalues of M
α. E
min
⁡
=
|
L
min
⁡
-
λ
min
⁡
| and E
max
⁡
=
|
U
max
⁡
-
λ
max
⁡
|.Table 1
The region for all the eigenvalues ofM
α with ℑ
(
θ
)
=
0 and 8
×
8.
α
E
min
⁡
L
min
⁡
λ
min
⁡
λ
max
⁡
U
max
⁡
E
max
⁡
0.1
0
−0.9978
−0.9978
0.9957
0.9971
0.0014
0.2
0
−0.9846
−0.9846
0.9977
0.9985
0.0008
0.3
0.0001
−0.9568
−0.9567
0.9985
0.9990
0.0005
0.4
0.0002
−0.9176
−0.9174
0.9988
0.9992
0.0004
0.5
0.0006
−0.8723
−0.8717
0.9990
0.9994
0.0004
0.6
0.001
−0.8249
−0.8239
0.9992
0.9995
0.0003
0.7
0.0015
−0.7779
−0.7764
0.9993
0.9996
0.0003
0.8
0.0021
−0.7325
−0.7304
0.9994
0.9996
0.0002
0.9
0.0026
−0.6892
−0.6866
0.9995
0.9997
0.0002
1
0.0031
−0.6482
−0.6451
0.9995
0.9997
0.0002Table 2
The region for all the eigenvalues ofM
α with ℑ
(
θ
)
=
0 and 16
×
16.
α
E
min
⁡
L
min
⁡
λ
min
⁡
λ
max
⁡
U
max
⁡
E
max
⁡
0.1
0
−0.9929
−0.9929
0.9997
1
0.0003
0.2
0
−0.9608
−0.9608
0.9998
1
0.0002
0.3
0.0001
−0.9135
−0.9134
0.9999
1
0.0001
0.4
0.0002
−0.8635
−0.8633
0.9999
1
0.0001
0.5
0.0004
−0.8154
−0.8150
0.9999
1
0.0001
0.6
0.0006
−0.7702
−0.7696
0.99996
1
0.00004
0.7
0.0007
−0.7278
−0.7271
0.99998
1
0.00002
0.8
0.001
−0.6880
−0.6870
0.99997
1
0.00003
0.9
0.001
−0.6504
−0.6494
0.99998
1
0.00002
1
0.001
−0.6147
−0.6137
0.99998
1
0.00002From Tables1 and 2, it is not difficult to find that the theoretical results are in line with the results of numerical experiments. Further, for 8
×
8, the average error in the lower bounds for 10 different values of α is 0.00112 and the average error in the upper bounds for 10 different values of α is 0.00047. For 16
×
16, the average error in the lower bounds for 10 different values of α is 0.0005 and the average error in the upper bounds for 10 different values of α is 0.000091. That is, Theorem 3 provides reasonably good bounds for the eigenvalue distribution of the iteration matrix M
α of the HSS method when the iteration parameter α is taken in different regions.Example 2 (see [11]).
The saddle point system is from the discretization of a groundwater flow problem using mixed-hybrid finite elements [11]. In the example at hand, n
=
270 and m
=
207. By calculations, here we have λ
n
=
0.0017, λ
1
=
0.010, σ
1
=
2.611, and σ
m
=
0.19743.
In this case there are nonreal eigenvalues (except for very smallα). In Table 3 we list the upper bounds given in Theorem 3 when ℑ
(
θ
)
≠
0. From Table 3, it is not difficult to find that the theoretical results are in line with the results of numerical experiments. That is, Theorem 3 provides reasonably good bounds for the eigenvalue distribution of the iteration matrix M
α with ℑ
(
θ
)
≠
0 when the iteration parameter α is taken in different regions.Table 3
All the nonreal eigenvalues ofM
α with ℑ
(
θ
)
≠
0.
α
max
⁡
|
λ
|
Upper bound
0.05
0.963349
0.999793
0.1
0.977199
0.999878
0.3
0.979200
0.999894
0.5
0.959713
0.999860
1
0.865509
0.999774



---

*Source: 942968-2014-03-31.xml*