# More on Generalizations and Modifications of Iterative Methods for Solving Large Sparse Indefinite Linear Systems

Authors: Jen-Yuan Chen; David R. Kincaid; Yu-Chien Li
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

Continuing from the works of Li et al. (2014), Li (2007),  and Kincaid et al. (2000), we present more generalizations and modifications of iterative methods for solving large sparse symmetric and nonsymmetric indefinite systems of linear equations. We discuss a variety of iterative methods such as GMRES, MGMRES, MINRES, LQ-MINRES, QR MINRES, MMINRES, MGRES, and others.


---

## Body

## 1. Introduction

When solving large sparse linear systems of the form(1)
A
x
=
b
,
in which the coefficient matrix A is indefinite, there are basis methods and a variety of generalizations and modifications of them. For example, basic iterative methods for symmetric indefinite linear systems are the MINRES method and the SYMMLQ method, while a basic method for nonsymmetric linear systems is the GMRES method. (See, e.g., Lanczos [1], Golub and Van Loan [2], Paige and Saunders [3], Saad [4], and Saad and Schultz [5].)In Section2, we review the Arnoldi process and present background material. In Sections 3 and 4, we describe the LQ-MINRES and the QR-MINRES methods, respectively, as well as discussing their relationship in Section 5. In Section 6, we take a closer look at the QR-MINRES method and the SYMMQR method. In Sections 7 and 8, we describe the modified MINRES (MMINRES) method and the generalized QR-MINRES method, respectively. In Section 9, we review the GMRES method. Finally, we discuss the differences between the modified MINRES (MMINRES) method and the modified GMRES (MGMRES) method, in Section 10.


## 2. Arnoldi Process

First, we assume that matrixA is symmetric. In [6, 7], we use a short term recurrence to generate orthonormal vectors {
w
(
0
)
,
w
(
1
)
,
w
(
2
)
,
…
,
w
(
n
-
3
)
,
w
(
n
-
2
)
,
w
(
n
-
1
)
} as follows:
(2)
u
(
0
)
=
arbitrary
,
r
(
0
)
=
b
-
A
u
(
0
)
,
w
~
(
0
)
=
r
(
0
)
,
σ
0
=
〈
w
~
(
0
)
,
w
~
(
0
)
〉
,
w
(
0
)
=
(
1
σ
0
)
w
~
(
0
)
,
f
o
r
i
=
1,2
,
…
,
n
-
1
,
α
i
-
1
=
〈
A
w
(
i
-
1
)
,
w
(
i
-
1
)
〉
,
β
i
-
1
=
〈
A
w
(
i
-
1
)
,
w
(
i
-
2
)
〉
,
w
~
(
i
)
=
A
w
(
i
-
1
)
-
α
i
-
1
w
(
i
-
1
)
-
β
i
-
1
w
(
i
-
2
)
,
σ
i
=
〈
w
~
(
i
)
,
w
~
(
i
)
〉
,
w
(
i
)
=
(
1
σ
i
)
w
~
(
i
)
,
e
n
d
f
o
r
.
Here we assume that w
(
-
1
)
=
0 and σ
i
≠
0, for all i. If we let w
~
(
0
)
=
r
(
0
)
=
b
-
A
u
(
0
), then the subspace,
(3)
Span
⁡
{
w
(
0
)
,
w
(
1
)
,
w
(
2
)
,
…
,
w
(
n
-
3
)
,
w
(
n
-
2
)
,
w
(
n
-
1
)
}
,
is equivalent to the Krylov subspace
(4)
K
n
(
r
(
0
)
,
A
)
=
Span
⁡
{
r
(
0
)
,
A
r
(
0
)
,
A
2
r
(
0
)
,
A
3
r
(
0
)
,
…
,
A
n
-
3
r
(
0
)
,
h
h
h
h
h
h
h
A
n
-
2
r
(
0
)
,
A
n
-
1
r
(
0
)
}
.
Consequently, we have the following properties, for (0
≤
i, j
≤
n
-
1):
(5)
〈
w
(
i
)
,
w
(
j
)
〉
=
δ
i
j
,
β
i
=
σ
i
,
as well as these matrix equations
(6)
A
W
n
-
1
=
W
n
-
1
T
n
+
σ
n
w
(
n
)
e
n
T
=
W
n
T
~
n
+
1
,
(7)
W
n
-
1
T
W
n
-
1
=
I
,
where
(8)
W
n
-
1
=
[
w
(
0
)
,
w
(
1
)
,
w
(
1
)
,
…
,
w
(
n
-
3
)
,
w
(
n
-
2
)
,
w
(
n
-
1
)
]
n
×
n
,
(9)
e
n
T
=
[
0,0
,
0
,
…
,
0,0
,
0,1
]
1
×
n
,
(10)
T
n
=
[
α
0
β
1
σ
1
α
1
β
2
σ
2
α
2
β
3
⋱
⋱
⋱
σ
n
-
3
α
n
-
3
β
n
-
2
σ
n
-
2
α
n
-
2
β
n
-
1
σ
n
-
1
α
n
-
1
]
n
×
n
,
(11)
T
~
n
+
1
=
[
α
0
β
1
σ
1
α
1
β
2
σ
2
α
2
β
3
⋱
⋱
⋱
σ
n
-
3
α
n
-
3
β
n
-
2
σ
n
-
2
α
n
-
2
β
n
-
1
σ
n
-
1
α
n
-
1
σ
n
]
(
n
+
1
)
×
n
=
T
n
+
T
n
e
n
+
1
T
.Example. We illustrate (6), for the case n
=
3.From (2) and (7), we have
(12)
σ
1
w
(
1
)
=
w
~
(
1
)
=
A
w
(
0
)
-
α
0
w
(
0
)
-
β
0
w
(
-
1
)
σ
2
w
(
2
)
=
w
~
(
2
)
=
A
w
(
1
)
-
α
1
w
(
1
)
-
β
1
w
(
0
)
σ
3
w
(
3
)
=
w
~
(
3
)
=
A
w
(
2
)
-
α
2
w
(
2
)
-
β
2
w
(
1
)
.
Since w
(
-
1
)
=
0, we obtain
(13)
A
W
2
=
A
[
w
(
0
)
w
(
1
)
w
(
2
)
]
=
[
A
w
(
0
)
A
w
(
1
)
A
w
(
2
)
]
=
[
β
0
w
(
-
1
)
+
α
0
w
(
0
)
+
σ
1
w
(
1
)
β
1
w
(
0
)
+
α
1
w
(
1
)
+
σ
2
w
(
2
)
β
2
w
(
1
)
+
α
2
w
(
2
)
+
σ
3
w
(
3
)
]
T
=
[
w
(
0
)
w
(
1
)
w
(
2
)
w
(
3
)
]
[
α
0
β
1
0
σ
1
α
1
β
2
0
σ
2
α
2
0
0
σ
3
]
4
×
3
=
W
3
T
~
4
=
[
W
2
w
(
3
)
]
[
T
3
0
0
σ
3
]
=
W
2
T
3
+
σ
3
w
(
3
)
e
3
T
.
So we obtain (6), with n
=
3:
(14)
A
W
2
=
W
2
T
3
+
σ
3
w
(
3
)
e
3
T
=
W
3
T
~
4
.


## 3. LQ-MINRES Method

We chooseu
(
n
) such that u
(
n
)
-
u
(
0
)
∈
K
n
(
r
(
0
)
,
A
). Hence, we have
(15)
u
(
n
)
=
u
(
0
)
+
W
n
-
1
y
(
n
)
,
r
(
n
)
=
r
(
0
)
-
(
A
W
n
-
1
)
y
(
n
)
.
For the MINRES method [3], we let
(16)
f
(
y
(
n
)
)
=
(
r
(
n
)
)
T
(
r
(
n
)
)
,
=
(
r
(
0
)
-
A
W
n
-
1
y
(
n
)
)
T
(
r
(
0
)
-
A
W
n
-
1
y
(
n
)
)
;
then
(17)
∇
f
(
y
(
n
)
)
=
-
2
W
n
-
1
T
A
(
r
(
0
)
-
A
W
n
-
1
y
(
n
)
)
=
-
2
W
n
-
1
T
A
r
(
0
)
+
2
W
n
-
1
T
A
2
W
n
-
1
y
(
n
)
.
Letting ∇
f
(
y
(
n
)
)
=
0, we can minimize ∥
r
(
n
)
∥ by solving this linear system for y
(
n
)
(18)
(
W
n
-
1
T
A
2
W
n
-
1
)
y
(
n
)
=
W
n
-
1
T
A
r
(
0
)
.First, using (6), (7), and (5), we expand the coefficient matrix on the left-hand side of linear system (18)
(19)
W
n
-
1
T
A
2
W
n
-
1
=
(
W
n
-
1
T
A
)
(
A
W
n
-
1
)
=
(
A
W
n
-
1
)
T
(
A
W
n
-
1
)
=
(
W
n
-
1
T
n
+
σ
n
w
(
n
)
e
n
T
)
T
(
W
n
-
1
T
n
+
σ
n
w
(
n
)
e
n
T
)
=
(
T
n
T
W
n
-
1
T
+
σ
n
e
n
(
w
(
n
)
)
T
)
(
W
n
-
1
T
n
+
σ
n
w
(
n
)
e
n
T
)
=
T
n
T
T
n
+
σ
n
2
e
n
e
n
T
=
T
n
2
+
σ
n
2
e
n
e
n
T
,
since T
n is symmetric. Second, we exam the right-hand side vector in linear system (18)
(20)
(
W
n
-
1
T
A
)
r
(
0
)
=
(
W
n
-
1
T
A
)
(
σ
0
w
(
0
)
)
=
σ
0
(
W
n
-
1
T
A
W
n
-
1
)
(
W
n
-
1
T
w
(
0
)
)
=
σ
0
T
n
e
1
,
since r
(
0
)
=
σ
0
w
(
0
), W
n
-
1
W
n
-
1
T
=
I, and W
n
-
1
T
A
W
n
-
1
=
T
n.Here〈
w
(
i
)
,
w
(
j
)
〉
=
δ
i
j. We obtain
(21)
T
n
(
Q
n
-
1
)
=
[
γ
0
δ
1
γ
1
ε
2
δ
2
γ
2
⋱
⋱
⋱
ε
n
-
3
δ
n
-
3
γ
n
-
3
ε
n
-
2
δ
n
-
2
γ
n
-
2
ε
n
-
1
δ
n
-
1
γ
-
n
-
1
]
n
×
n
≡
L
¯
n
,
where
(22)
Q
n
-
1
≡
Q
1,2
Q
2,3
Q
3,4
⋯
Q
n
-
2
,
n
-
1
Q
n
-
1
,
n
.
Here a Givens rotation matrix is(23)
Q
i
,
i
+
1
=
[
1
1
⋱
1
1
c
i
-
s
i
s
i
c
i
1
1
⋱
1
1
]
n
×
n
,with c
i
2
+
s
i
2
=
1.Here, we repeatedly apply Givens rotations to the right-hand side ofT
n, (10), in order to zero out the β
i-diagonal above the α
i main diagonal and change the tridiagonal matrix T
n into a lower tridiagonal matrix L
¯
n.Then, from (22), we have
(24)
T
n
Q
n
-
1
=
L
¯
n
.
Since Q
n
-
1
-
1
=
Q
n
-
1
T, we obtain
(25)
T
n
=
L
¯
n
Q
n
-
1
T
,
T
n
T
=
Q
n
-
1
L
¯
n
T
.
Since T
n is symmetric, we have
(26)
T
n
2
=
T
n
T
n
=
T
n
T
n
T
=
(
L
¯
n
Q
n
-
1
T
)
(
Q
n
-
1
L
¯
n
T
)
=
L
¯
n
L
¯
n
T
.
Thus, we find that the coefficient matrix (26) can be written as
(27)
T
n
2
+
σ
n
2
e
n
e
n
T
=
L
¯
n
L
¯
n
T
+
σ
n
2
e
n
e
n
T
.
Consequently, we are now interested in solving this linear system
(28)
(
L
¯
n
L
¯
n
T
+
σ
n
2
e
n
e
n
T
)
y
(
n
)
=
σ
0
T
n
e
1
.In the next step in the SYMMLQ method [6, 7], we solve
(29)
T
n
+
1
y
(
n
+
1
)
=
σ
0
e
1
.Since(30)
(
T
n
+
1
)
Q
n
-
1
=
[
γ
0
δ
1
γ
1
ε
2
δ
2
γ
2
⋱
⋱
⋱
ε
n
-
3
δ
n
-
3
γ
n
-
3
ε
n
-
2
δ
n
-
2
γ
n
-
2
ε
n
-
1
δ
n
-
1
ε
n
γ
-
n
-
1
σ
n
δ
-
n
α
n
]
(
n
+
1
)
×
(
n
+
1
)
,where
(31)
Q
n
-
1
≡
Q
1,2
Q
2,3
Q
3,4
⋯
Q
n
-
3
,
n
-
2
Q
n
-
2
,
n
-
1
Q
n
-
1
,
n
,
then we choose
(32)
c
n
=
γ
-
n
-
1
γ
n
-
1
,
γ
n
-
1
=
γ
-
n
-
1
2
+
σ
n
2
.
Thus, we have γ
-
n
-
1
=
c
n
γ
n
-
1. Recall that c
n
2
+
s
n
2
=
1 by (23). (For details on the SYMMLQ method, see [6, 7].)Then, we have(33)
L
n
=
[
γ
0
δ
1
γ
1
ε
2
δ
2
γ
2
⋱
⋱
⋱
ε
n
-
3
δ
n
-
3
γ
n
-
3
ε
n
-
2
δ
n
-
2
γ
n
-
2
ε
n
-
1
δ
n
-
1
γ
n
-
1
]
n
×
n
=
[
0
0
0
B
⋮
0
0
γ
n
-
1
]
n
×
n
=
B
+
γ
n
-
1
e
n
,
where
(34)
B
=
[
γ
0
δ
1
γ
1
ε
2
δ
2
γ
2
⋱
⋱
⋱
ε
n
-
3
δ
n
-
3
γ
n
-
3
ε
n
-
2
δ
n
-
2
γ
n
-
2
ε
n
-
1
δ
n
-
1
]
n
×
(
n
-
1
)
.
Consequently, we obtain
(35)
L
n
L
n
T
=
(
B
+
γ
n
-
1
e
n
)
(
B
T
+
γ
n
-
1
e
n
T
)
=
B
B
T
+
γ
n
-
1
2
e
n
e
n
T
.
Then, we let
(36)
L
¯
n
≡
L
n
D
~
n
,
where
(37)
D
~
n
=
[
1
1
⋱
1
1
c
n
]
n
×
n
.
So we have
(38)
L
¯
=
B
+
γ
n
-
1
c
n
e
n
=
B
+
γ
-
n
-
1
e
n
since γ
-
n
-
1
2
/
γ
n
-
1
2
=
c
n. Consequently, we have
(39)
L
¯
n
L
¯
n
T
=
(
B
+
γ
-
n
-
1
e
n
)
(
B
T
+
γ
-
n
-
1
e
n
T
)
=
B
B
T
+
γ
-
n
-
1
2
e
n
e
n
T
.Using (35) and (39), we have
(40)
L
n
L
n
T
-
γ
n
-
1
2
e
n
e
n
T
=
B
B
T
=
L
¯
n
L
¯
n
T
-
γ
-
n
-
1
2
e
n
e
n
T
.
Since γ
-
n
-
1
2
+
σ
n
2
=
γ
n
-
1
2, the coefficient matrix in linear equation (28) is
(41)
L
¯
n
L
¯
n
T
+
σ
n
2
e
n
e
n
T
=
L
n
L
n
T
.From (24) and (36)
(42)
T
n
Q
n
-
1
=
L
¯
n
,
L
¯
n
=
L
n
D
~
n
,
we have the right-hand side vector in linear system (28)
(43)
σ
0
T
n
e
1
=
σ
0
L
¯
n
Q
n
-
1
T
e
1
=
σ
0
L
n
D
~
n
Q
n
-
1
T
e
1
.
Since L
n is nonsingular, and from (41) and (43), linear system (28) is
(44)
(
L
n
L
n
T
)
y
(
n
)
=
σ
0
L
n
D
~
n
Q
n
-
1
T
e
1
,
which reduces to
(45)
(
L
n
T
)
y
(
n
)
=
σ
0
D
~
n
Q
n
-
1
T
e
1
.
Thus, we obtain this equation for the nth iteration of the LQ-MINRES method
(46)
u
L
(
n
)
=
u
(
0
)
+
W
n
-
1
y
(
n
)
=
u
(
0
)
+
W
n
-
1
(
L
n
T
)
-
1
(
σ
0
D
~
n
Q
n
-
1
T
e
1
)
.


## 4. QR-MINRES Method

Again, as in Section3, we consider another method for solving linear system (18) for y
(
n
)
(47)
(
W
n
-
1
T
A
2
W
n
-
1
)
y
(
n
)
=
W
n
-
1
T
A
r
(
0
)
.
Then, instead of solving linear system (47), we now solve
(48)
(
T
n
2
+
σ
n
2
e
n
e
n
T
)
y
(
n
)
=
σ
0
T
n
e
1
.First, we repeatedly apply Givens rotations to the left-hand side ofT
n
(49)
Q
n
-
1
T
n
=
[
γ
0
δ
1
ε
2
γ
1
δ
2
ε
3
γ
2
δ
3
ε
4
⋱
⋱
⋱
γ
n
-
3
δ
n
-
2
ε
n
-
1
γ
n
-
2
δ
n
-
1
γ
-
n
-
1
]
n
×
n
≡
R
¯
n
,
where
(50)
Q
n
-
1
≡
Q
n
-
1
,
n
Q
n
-
2
,
n
-
1
Q
n
-
3
,
n
-
2
⋯
Q
3,4
Q
2,3
Q
1,2
.
Here, we use Givens rotations applied on the left-hand side of T
n, (10), to transform a tridiagonal matrix into an upper tridiagonal matrix L
¯
n, (21).Then, we obtain(51)
Q
n
-
1
T
n
=
R
¯
n
,
T
n
=
Q
n
-
1
T
R
¯
n
.
Since T
n is symmetric, we obtain
(52)
T
n
=
T
n
T
=
R
¯
n
T
Q
n
-
1
.
Thus, the coefficient matrix in linear system (48) can be written as
(53)
T
n
2
+
σ
n
2
e
n
e
n
T
=
R
¯
n
T
R
¯
n
+
σ
n
2
e
n
e
n
T
.
Consequently, we are interested in solving this linear system
(54)
(
R
¯
n
R
¯
n
T
+
σ
n
2
e
n
e
n
T
)
y
(
n
)
=
σ
0
T
n
e
1
.In the next step in the SYMMQR method [6, 7], we solve this linear system
(55)
T
n
+
1
y
(
n
+
1
)
=
σ
0
e
1
.
Since(56)
(
Q
n
-
1
)
T
n
+
1
=
[
γ
0
δ
1
ε
2
γ
1
δ
2
ε
2
γ
2
δ
3
ε
4
⋱
⋱
⋱
γ
n
-
3
δ
n
-
2
ε
n
-
1
γ
n
-
2
δ
n
-
1
ε
n
γ
-
n
-
1
σ
n
δ
-
n
α
n
]
(
n
+
1
)
×
(
n
+
1
)
,where
(57)
Q
n
-
1
≡
Q
n
-
1
,
n
Q
n
-
2
,
n
-
1
Q
n
-
3
,
n
-
2
⋯
Q
2,3
Q
1,2
,
then we choose
(58)
c
n
=
γ
-
n
-
1
γ
n
-
1
,
γ
n
-
1
=
γ
-
n
-
1
2
+
σ
n
2
.
Thus, we obtain γ
-
n
-
1
=
c
n
γ
n
-
1. (For details on the SYMMQR method, see [6, 7].)Let(59)
R
n
=
[
γ
0
δ
1
ε
2
γ
1
δ
2
ε
3
γ
2
δ
3
ε
4
⋱
⋱
⋱
γ
n
-
3
δ
n
-
2
ε
n
-
1
γ
n
-
2
δ
n
-
1
γ
n
-
1
]
n
×
n
=
[
B
0
0
0
⋯
0
0
γ
n
-
1
]
n
×
n
=
B
+
γ
n
-
1
e
n
T
,
where
(60)
B
=
[
γ
0
δ
1
ε
2
γ
1
δ
2
ε
3
γ
2
δ
3
ε
4
⋱
⋱
⋱
γ
n
-
3
δ
n
-
2
ε
n
-
1
γ
n
-
2
δ
n
-
1
]
(
n
-
1
)
×
n
.
We have
(61)
R
n
T
R
n
=
(
B
T
+
γ
n
-
1
e
n
)
(
B
+
γ
n
-
1
e
n
T
)
=
B
T
B
+
γ
n
-
1
2
e
n
e
n
T
.Then, we have(62)
R
¯
n
=
D
~
n
R
n
,
where
(63)
D
~
n
=
[
1
1
⋱
1
1
c
n
]
n
×
n
.
So we have
(64)
R
¯
n
=
B
+
c
n
γ
n
-
1
e
n
T
=
B
+
γ
-
n
-
1
e
n
T
,
R
¯
n
T
=
B
T
+
γ
-
n
-
1
e
n
,
since γ
-
n
-
1
/
γ
n
-
1
=
c
n. Consequently, we obtain
(65)
R
¯
n
T
R
¯
n
=
(
B
T
+
γ
-
n
-
1
e
n
)
(
B
+
γ
-
n
-
1
e
n
)
T
=
B
T
B
+
γ
-
n
-
1
2
e
n
e
n
T
.Using (64), we have
(66)
R
n
R
n
T
-
γ
n
2
e
n
e
n
T
=
R
¯
n
R
¯
n
T
-
γ
-
n
2
e
n
e
n
T
.
Since γ
-
n
-
1
2
+
σ
n
2
=
γ
n
-
1
2, the coefficient matrix in the linear equation (54) is
(67)
R
¯
n
R
¯
n
T
+
σ
n
2
e
n
e
n
T
=
R
n
R
n
T
.Since(68)
T
n
=
R
¯
n
T
Q
n
-
1
,
R
¯
n
=
D
~
n
R
n
,
we have right-hand side vector in the linear system (54)
(69)
σ
0
T
n
e
1
=
σ
0
R
¯
n
T
Q
n
-
1
e
1
=
σ
0
R
n
T
D
~
n
Q
n
-
1
e
1
.
Since R
n is nonsingular, we obtain the linear system (54)
(70)
(
R
n
T
R
n
)
y
(
n
)
=
σ
0
R
n
T
D
~
n
Q
n
-
1
e
1
,
which reduces to
(71)
R
n
y
(
n
)
=
σ
0
D
~
n
Q
n
-
1
e
1
.
Thus, we obtain the equation for the nth iteration of the QR-MINRES method
(72)
u
R
(
n
)
=
u
(
0
)
+
W
n
-
1
y
(
n
)
=
u
(
0
)
+
W
n
-
1
R
n
-
1
(
σ
0
D
~
n
Q
n
-
1
e
1
)
.


## 5. Relation between LQ-MINRES and QR-MINRES

Now, we show that the LQ-MINRES method and the QR-MINRES method are essentially the same. In the LQ-MINRES method (46), we have
(73)
u
L
(
n
)
=
u
(
0
)
+
W
n
-
1
(
L
n
T
)
-
1
(
σ
0
D
~
n
L
Q
L
T
e
1
)
.
In the QR-MINRES method (72), we have
(74)
u
R
(
n
)
=
u
(
0
)
+
W
n
-
1
R
n
-
1
(
σ
0
D
~
n
R
Q
R
e
1
)
.
For the LQ-MINRES method (73), we have
(75)
c
1
=
α
0
γ
0
,
c
k
L
=
γ
-
k
-
1
L
γ
k
-
1
L
,
s
1
=
β
1
γ
0
,
s
k
L
=
β
k
γ
k
-
1
L
,
δ
-
k
L
=
{
β
1
,
k
=
1
,
-
c
k
-
1
L
β
k
,
δ
k
L
=
c
k
L
δ
-
k
L
+
s
k
L
α
k
,
ε
k
L
=
s
k
-
1
L
β
k
,
γ
-
k
L
=
{
α
0
,
k
=
0
,
-
s
k
L
δ
-
k
L
-
c
k
L
α
k
,
γ
k
L
=
(
γ
-
k
L
)
2
+
σ
k
+
1
2
.
In the QR-MINRES method (46), we have
(76)
c
1
=
α
0
γ
0
,
c
k
R
=
γ
-
k
-
1
R
γ
k
-
1
R
,
s
1
=
-
β
1
γ
0
,
s
k
R
=
-
β
k
γ
k
-
1
R
,
δ
-
k
R
=
{
β
1
,
k
=
1
,
c
k
-
1
R
β
k
,
δ
k
R
=
c
k
R
δ
-
k
R
-
s
k
R
α
k
,
ε
k
R
=
-
s
k
-
1
R
β
k
,
γ
-
k
R
=
{
α
0
,
k
=
0
,
s
k
R
δ
-
k
R
+
c
k
R
α
k
,
γ
k
R
=
(
γ
-
k
R
)
2
+
σ
k
+
1
2
.
From the computation and by induction, we have the following relations between the LQ-MINRES method and the QR-MINRES method:
(77)
c
k
L
=
{
c
k
R
,
k
:
odd
,
-
c
k
R
,
k
:
even
,
γ
-
k
L
=
{
-
γ
k
R
,
k
:
odd
,
γ
k
R
,
k
:
even
,
δ
-
k
L
=
{
δ
k
R
,
k
:
odd
,
-
δ
k
R
,
k
:
even
,
s
k
L
=
-
s
k
R
.
By induction, we have
(78)
δ
k
L
=
δ
k
R
,
ε
k
L
=
ε
k
R
,
γ
k
L
=
γ
k
R
.
Hence, we obtain
(79)
L
n
T
=
R
n
.
Moreover, if we let
(80)
σ
0
D
~
n
L
Q
L
T
e
1
=
[
ξ
0
L
,
ξ
1
L
,
ξ
2
L
,
…
,
ξ
n
-
3
L
,
ξ
n
-
2
L
,
ξ
n
-
1
L
]
1
×
n
T
,
σ
0
D
~
n
R
Q
R
e
1
=
[
ξ
0
R
,
ξ
1
R
,
ξ
2
R
,
…
,
ξ
n
-
3
R
,
ξ
n
-
2
R
,
ξ
n
-
1
R
]
1
×
n
T
,
then
(81)
ξ
i
L
=
c
i
+
1
L
s
1
L
s
2
L
s
3
L
⋯
s
i
-
2
L
s
i
-
1
L
s
i
L
σ
0
=
c
i
+
1
L
(
-
1
)
i
s
1
R
s
2
R
s
3
R
⋯
s
s
-
2
R
s
i
-
1
R
s
i
R
σ
0
=
c
i
+
1
R
s
1
R
s
2
R
s
3
R
⋯
s
i
-
2
R
s
i
-
1
R
s
i
R
σ
0
=
ξ
i
R
.
Thus, we obtain
(82)
u
L
(
n
)
=
u
R
(
n
)
.


## 6. A Closer Look at QR-MINRES and SYMMQR

In the SYMMQR method [6, 7], we have two estimated solutions: u
ls
(
n
) and u
Gal
(
n
).The first estimated solution is(83)
u
ls
(
n
)
=
u
(
0
)
+
W
n
-
1
y
ls
(
n
)
,
where y
ls
(
n
) is the solution of this linear system
(84)
R
n
y
(
n
)
=
z
(
n
)
,
with the right-hand side vector being
(85)
z
(
n
)
=
[
ξ
0
,
ξ
1
,
ξ
2
,
…
,
ξ
n
-
3
,
ξ
n
-
2
,
ξ
n
-
1
]
1
×
n
T
.
From these equations, we have
(86)
z
(
n
)
=
σ
0
D
~
n
R
Q
R
e
1
.
Thus, we have
(87)
u
R
(
n
)
=
u
ls
(
n
)
,
where u
ls
(
n
) is the solution of this least square problem
(88)
min
⁡
y
(
n
)
∈
R
n
∥
T
~
n
+
1
y
(
n
)
-
σ
0
e
1
∥
.The second estimated solution is(89)
u
Gal
(
n
)
=
u
(
0
)
+
W
n
-
1
y
Gal
(
n
)
,
where y
Gal is the solution of this linear system
(90)
R
¯
n
y
(
n
)
=
z
-
(
n
)
,
(91)
u
Gal
(
n
)
-
u
(
0
)
=
D
~
n
-
2
(
u
R
(
n
)
-
u
(
0
)
)
.


## 7. Modified MINRES (MMINRES) Method

Next, we assume that matrixA is nonsymmetric. In [6, 7], we use a long term recurrence to generate orthonormal vectors {
w
(
0
)
,
w
(
1
)
,
w
(
2
)
,
…
,
w
(
n
-
3
)
,
w
(
n
-
2
)
,
w
(
n
-
1
)
} as follows:
(92)
u
(
0
)
=
arbitrary
,
r
(
0
)
=
b
-
A
u
(
0
)
,
w
~
(
0
)
=
r
(
0
)
,
σ
0
=
〈
w
~
(
0
)
,
w
~
(
0
)
〉
,
w
(
0
)
=
(
1
σ
0
)
w
~
(
0
)
,
f
o
r
i
=
1,2
,
…
,
n
-
1
,
for
w
~
(
i
)
=
A
w
(
i
-
1
)
∑
‍
j
=
0
i
-
1
b
i
,
j
w
(
j
)
,
for
where
b
i
,
j
=
〈
A
w
(
i
-
1
)
,
w
(
j
)
〉
,
for
σ
i
=
〈
w
~
(
i
)
,
w
~
(
i
)
〉
,
for
w
(
i
)
=
(
1
σ
i
)
w
~
(
i
)
,
e
n
d
f
o
r
.
Consequently, we obtain the following matrix equations:
(93)
A
W
n
-
1
=
W
n
-
1
H
n
+
σ
n
w
(
n
)
e
n
T
=
W
n
H
~
n
+
1
,
W
n
-
1
T
W
n
-
1
=
I
,
where
(94)
W
n
-
1
=
[
w
(
0
)
,
w
(
1
)
,
w
(
2
)
,
…
,
w
(
n
-
3
)
,
w
(
n
-
2
)
,
w
(
n
-
1
)
]
n
×
n
,
e
n
T
=
[
0,0
,
0
,
…
,
0,0
,
0,1
]
1
×
n
,
H
n
=
[
b
1,0
b
2,0
b
3,0
⋯
b
n
-
2,0
b
n
-
1,0
b
n
,
0
σ
1
b
2,1
b
3,1
⋯
b
n
-
2,1
b
n
-
1,1
b
n
,
1
σ
2
b
3,2
⋯
b
n
-
2,2
b
n
-
1,2
b
n
,
2
⋱
⋱
⋮
⋮
⋮
σ
n
-
3
b
n
-
2
,
n
-
3
b
n
-
1
,
n
-
3
b
n
,
n
-
3
σ
n
-
2
b
n
-
1
,
n
-
2
b
n
,
n
-
2
σ
n
-
1
b
n
,
n
-
1
]
n
×
n
,
H
~
n
+
1
=
[
b
1,0
b
2,0
b
3,0
⋯
b
n
-
2,0
b
n
-
1,0
b
n
,
0
σ
1
b
2,1
b
3,1
⋯
b
n
-
2,1
b
n
-
1,1
b
n
,
1
σ
2
b
3,2
⋯
b
n
-
2,2
b
n
-
1,2
b
n
,
2
⋱
⋱
⋮
⋮
⋮
σ
n
-
3
b
n
-
2
,
n
-
3
b
n
-
1
,
n
-
3
b
n
,
n
-
3
σ
n
-
2
b
n
-
1
,
n
-
2
b
n
,
n
-
2
σ
n
-
1
b
n
,
n
-
1
σ
n
]
(
n
+
1
)
×
n
.
Since the matrix H
n is a full upper Hessenberg matrix, the LQ-MINRES method isnot a practical procedure. Hence, we discuss only a generalization of the QR-MINRES method.


## 8. Generalized QR-MINRES Method

Since the matrixA is nonsymmetric, to minimize an expression such as this
(95)
min
⁡
y
(
n
)
∈
R
n
f
(
y
(
n
)
)
=
(
r
(
n
)
)
T
(
r
(
n
)
)
,
we choose y
(
n
) to satisfy
(96)
(
W
n
-
1
T
A
T
A
W
n
-
1
)
y
(
n
)
=
W
n
-
1
T
A
T
r
(
0
)
.
First, from the Arnoldi process and from the left-hand side of linear system (96), we can write the coefficient matrix of this linear system as
(97)
W
n
-
1
T
A
T
A
W
n
-
1
=
(
A
W
n
-
1
)
T
A
W
n
-
1
=
(
W
n
-
1
H
n
+
σ
n
w
(
n
)
e
n
T
)
T
(
W
n
-
1
H
n
+
σ
n
w
(
n
)
e
n
T
)
=
H
n
T
H
n
+
σ
n
2
e
n
e
n
T
.
Second, from the right-hand side vector of the linear system (96), we have
(98)
(
W
n
-
1
T
A
T
)
r
(
0
)
=
(
A
W
n
-
1
)
T
σ
0
w
(
0
)
=
(
W
n
-
1
H
n
+
σ
n
w
(
n
)
e
n
T
)
T
σ
0
w
(
0
)
=
(
H
n
T
W
n
-
1
T
)
σ
0
w
(
0
)
=
σ
0
H
n
T
e
1
.
Consequently, instead of solving (96), we solve this linear system
(99)
(
H
n
T
H
n
+
σ
n
2
e
n
e
n
T
)
y
(
n
)
=
σ
0
H
n
T
e
1
.First, we repeatedly apply Givens rotations to the left-hand side ofH
n
(100)
Q
n
-
1
,
n
Q
n
-
2
,
n
-
1
Q
n
-
3
,
n
-
2
⋯
Q
3,4
Q
2,3
Q
1,2
H
n
≡
R
¯
n
.
By defining
(101)
Q
n
-
1
≡
Q
n
-
1
,
n
Q
n
-
2
,
n
-
1
Q
n
-
3
,
n
-
2
⋯
Q
3,4
Q
2,3
Q
1,2
,
we obtain
(102)
Q
n
-
1
H
n
=
R
¯
n
,
(103)
H
n
=
Q
n
-
1
T
R
¯
n
,
so that
(104)
H
n
T
=
R
¯
n
T
Q
n
-
1
.
Thus, the coefficient matrix in linear system (99) has the following form by using (103) and (104):
(105)
H
n
T
H
n
+
σ
n
2
e
n
e
n
T
=
R
¯
n
T
R
¯
n
+
σ
n
2
e
n
e
n
T
=
R
n
T
R
n
+
σ
n
2
e
n
e
n
T
.
Moreover, by using (102) and (104), the right-hand side vector in linear system (99) is
(106)
σ
0
H
n
T
e
1
=
σ
0
R
¯
n
T
Q
n
-
1
e
1
=
σ
0
R
n
T
D
~
n
Q
n
-
1
e
1
,
where
(107)
R
n
=
[
γ
0
×
×
⋯
⋯
⋯
×
γ
1
×
×
⋯
⋯
×
γ
2
×
×
⋯
×
⋱
⋱
⋱
⋮
γ
n
-
3
×
×
γ
n
-
2
×
γ
n
-
1
]
n
×
n
,
(108)
D
~
n
=
[
1
1
⋱
1
1
c
n
]
n
×
n
,
where c
n
=
γ
-
n
-
1
/
γ
n
-
1 and γ
n
-
1
=
γ
-
n
-
1
2
+
σ
n
2. Thus, we obtain γ
-
n
-
1
=
c
n
γ
n
-
1. Then, we have
(109)
R
¯
n
=
D
~
n
R
n
.Let(110)
B
≡
[
γ
0
×
×
×
×
×
×
γ
1
⋱
⋱
⋮
γ
2
⋱
⋱
⋮
⋱
⋱
⋱
⋮
γ
n
-
3
⋱
×
γ
n
-
2
×
]
(
n
-
1
)
×
n
.
Then, we have
(111)
R
n
=
B
+
γ
n
-
1
e
n
,
and we obtain
(112)
R
n
T
R
n
=
(
B
T
+
γ
n
-
1
e
n
T
)
(
B
+
γ
n
-
1
e
n
)
=
B
T
B
+
γ
n
-
1
2
e
n
T
e
n
.
We have
(113)
R
¯
n
=
D
~
n
R
n
=
B
+
c
n
γ
n
-
1
e
n
=
B
+
γ
-
n
-
1
e
n
,
(114)
R
¯
n
T
R
¯
n
=
(
B
T
+
γ
-
n
-
1
e
n
T
)
(
B
+
γ
-
n
-
1
e
n
)
=
B
T
B
+
γ
-
2
e
n
T
e
n
.Usingγ
-
n
-
1
2
+
σ
n
2
=
γ
n
2, (112), and (114) we find that the coefficient matrix in linear system (104) is
(115)
R
¯
n
T
R
¯
n
+
σ
n
2
e
n
e
n
T
=
R
n
T
R
n
,
and the right-hand side vector is
(116)
σ
0
H
n
T
e
1
=
σ
0
R
¯
n
T
Q
n
-
1
e
1
=
σ
0
R
n
T
D
~
n
Q
n
-
1
e
1
.
Since R
n is nonsingular, we obtain this linear system
(117)
(
R
n
T
R
n
)
y
(
n
)
=
σ
0
R
n
T
D
~
n
Q
n
-
1
e
1
,
which reduces to this linear system
(118)
R
n
y
(
n
)
=
σ
0
D
~
n
Q
n
-
1
e
1
.
Thus, we obtain the nth iteration of the generalized QR-MINRES method
(119)
u
R
(
n
)
=
u
(
0
)
+
W
n
-
1
y
(
n
)
=
u
(
0
)
+
W
n
-
1
R
n
-
1
(
σ
0
D
~
n
Q
n
-
1
e
1
)
.


## 9. GMRES Method

In the GMRES method, we let(120)
u
(
n
)
=
u
(
0
)
+
W
n
-
1
y
(
n
)
.
Multiplying by A, we have
(121)
A
u
(
n
)
=
A
u
(
0
)
+
(
A
W
n
-
1
)
y
(
n
)
,
b
-
A
u
(
n
)
=
b
-
A
u
(
0
)
-
(
A
W
n
-
1
)
y
(
n
)
.
Then
(122)
r
(
n
)
=
r
(
0
)
-
(
A
W
n
-
1
)
y
(
n
)
.
For minimizing ∥
r
(
n
)
∥, we need to solve
(123)
min
⁡
y
∈
R
n
∥
H
~
n
+
1
y
-
σ
0
e
1
∥
,
by using Givens rotation, which is the GMRES method.In Saad’s book [4], there is a relation between the FOM method and the GMRES method. For the FOM method, we impose the Galerkin condition r
(
n
)
⊥
W
n
-
1 and we solve this linear system for y
(124)
H
n
y
=
σ
0
e
1
.
For the (n
+
1)st iteration, we solve this linear system for y
(125)
H
n
+
1
y
=
σ
0
e
1
.
Between the nth iteration and the (n
+
1)st iteration of the FOM method, we obtain the solution of the this least squares problem
(126)
min
⁡
y
∈
R
n
∥
H
~
n
+
1
y
-
σ
0
e
1
∥
,
which is the same as in the GMRES method.


## 10. Differences between MMINRES and MGMRES

In this section, we assume that matricesE and E
A are nonsingular symmetric matrices (butnot necessarily positive definite). In [6, 7], we use a short term recurrence to generate orthonormal vectors {
w
(
0
)
,
w
(
1
)
,
w
(
2
)
,
…
,
w
(
n
-
3
)
,
w
(
n
-
2
)
,
w
(
n
-
1
)
} as follows:
(127)
u
(
0
)
=
arbitrary
,
r
(
0
)
=
b
-
A
u
(
0
)
,
w
~
(
0
)
=
r
(
0
)
,
σ
0
=
〈
E
w
~
(
0
)
,
w
~
(
0
)
〉
,
w
(
0
)
=
(
1
σ
0
)
w
~
(
0
)
,
f
o
r
i
=
1,2
,
…
,
n
-
1
,
(128)
α
i
-
1
=
〈
E
A
w
(
i
-
1
)
,
w
(
i
-
1
)
〉
〈
E
w
(
i
-
1
)
,
w
(
i
-
1
)
〉
,
β
i
-
1
=
〈
E
A
w
(
i
-
1
)
,
w
(
i
-
2
)
〉
〈
E
w
(
i
-
2
)
,
w
(
i
-
2
)
〉
,
(129)
w
~
(
i
)
=
A
w
(
i
-
1
)
-
α
i
-
1
w
(
i
-
1
)
-
β
i
-
1
w
(
i
-
2
)
,
(130)
σ
i
=
|
〈
E
w
~
(
i
)
,
w
~
(
i
)
〉
|
,
w
(
i
)
=
(
1
σ
i
)
w
~
(
i
)
,
e
n
d
f
o
r
.
We obtain these properties, for (0
≤
i, j
≤
n
-
1),
(131)
〈
E
w
(
i
)
,
w
(
j
)
〉
=
0
,
if
i
≠
j
,
β
i
=
σ
i
,
(132)
(
E
W
n
-
1
)
T
W
n
-
1
=
[
d
0
d
1
d
2
⋱
d
n
-
3
d
n
-
2
d
n
-
1
]
n
×
n
≡
D
n
,
where
(133)
d
i
=
〈
E
w
(
i
)
,
w
(
i
)
〉
=
{
1
,
if
〈
E
w
~
(
i
)
,
w
~
(
i
)
〉
>
0
,
-
1
,
if
〈
E
w
~
(
i
)
,
w
~
(
i
)
〉
<
0
.
Consequently, we obtain these matrix equations
(134)
A
W
n
-
1
=
W
n
-
1
T
n
+
σ
n
w
(
n
)
e
n
T
=
W
n
T
^
n
+
1
,
(135)
W
n
-
1
=
[
w
(
0
)
,
w
(
1
)
,
w
(
2
)
,
…
,
w
(
n
-
3
)
,
w
(
n
-
2
)
,
w
(
n
-
1
)
]
n
×
n
,
(136)
e
n
T
=
[
0,0
,
0
,
…
,
0,0
,
0,1
]
1
×
n
,
(137)
T
n
=
[
α
0
β
1
σ
1
α
1
β
2
σ
2
α
2
β
3
⋱
⋱
⋱
σ
n
-
3
α
n
-
3
β
n
-
2
σ
n
-
2
α
n
-
2
β
n
-
1
σ
n
-
1
α
n
-
1
]
n
×
n
,
(138)
T
^
n
+
1
=
[
α
0
β
1
σ
1
α
1
β
2
σ
2
α
2
β
3
⋱
⋱
⋱
σ
n
-
3
α
n
-
3
β
n
-
2
σ
n
-
2
α
n
-
2
β
n
-
1
σ
n
-
1
α
n
-
1
σ
n
]
(
n
+
1
)
×
n
.From (134) and (132), we obtain
(139)
(
E
W
n
-
1
)
T
(
A
W
n
-
1
)
=
(
E
W
n
-
1
)
T
(
W
n
-
1
T
n
+
σ
n
w
(
n
)
e
n
T
)
=
(
E
W
n
-
1
)
T
W
n
-
1
T
n
+
(
E
W
n
-
1
)
T
σ
n
w
(
n
)
e
n
T
=
(
E
W
n
-
1
)
T
W
n
-
1
T
n
+
σ
n
〈
E
W
n
-
1
,
w
(
n
)
〉
e
n
T
=
D
n
T
n
+
0
=
D
n
T
n
.Assume thatx
(
n
)
-
x
(
0
)
∈
W
n
-
1; then we have
(140)
x
(
n
)
=
x
(
0
)
+
W
n
-
1
y
(
n
)
r
(
n
)
=
r
(
0
)
-
(
A
W
n
-
1
)
y
(
n
)
.
From the Galerkin condition E
r
(
n
)
⊥
W
n
-
1, we have
(141)
(
E
r
(
n
)
)
T
W
n
-
1
=
0
.
From (141) and since E is symmetric, we obtain
(142)
0
=
(
E
r
(
n
)
)
T
W
n
-
1
=
(
r
(
n
)
)
T
E
T
W
n
-
1
=
(
r
(
n
)
)
T
E
W
n
-
1
=
(
E
W
n
-
1
)
T
r
(
n
)
.
Then by (142), we have
(143)
(
E
W
n
-
1
)
T
r
(
n
)
=
0
.From (139), (140), and (143), we obtain this linear system
(144)
(
D
n
T
n
)
y
(
n
)
=
(
E
W
n
-
1
)
T
(
A
W
n
-
1
)
y
(
n
)
=
(
E
W
n
-
1
)
T
(
r
(
0
)
-
r
(
n
)
)
=
(
E
W
n
-
1
)
T
r
(
0
)
=
σ
0
(
E
W
n
-
1
)
T
w
(
0
)
=
σ
0
〈
E
W
n
-
1
,
w
(
0
)
〉
=
σ
0
e
n
,
using (127), where σ
0
=
d
0
|
〈
E
r
(
0
)
,
r
(
0
)
〉
| and σ
0
w
(
0
)
=
r
(
0
).By (132) and (137), we have(145)
D
n
T
n
=
[
d
0
α
0
d
0
β
1
d
1
σ
1
d
1
α
1
d
1
β
2
d
2
σ
2
d
2
α
2
d
2
β
3
⋱
⋱
⋱
d
n
-
3
σ
n
-
3
d
n
-
3
σ
n
-
3
d
n
-
3
β
n
-
2
d
n
-
2
σ
n
-
2
d
n
-
2
α
n
-
2
d
n
-
2
β
n
-
1
d
n
-
1
σ
n
-
1
d
n
-
1
α
n
-
1
]
n
×
n
.Notice thatD
n
T
n is symmetric since
(146)
d
i
-
1
β
i
=
d
i
-
1
〈
E
A
w
(
i
)
,
w
(
i
-
1
)
〉
〈
E
w
(
i
-
1
)
,
w
(
i
-
1
)
〉
=
d
i
-
1
〈
w
(
i
)
,
E
A
w
(
i
-
1
)
〉
〈
E
w
(
i
-
1
)
,
w
(
i
-
1
)
〉
=
d
i
-
1
〈
w
(
i
)
,
E
(
σ
i
w
(
i
)
+
α
i
-
1
w
(
i
-
1
)
+
β
i
-
1
w
(
i
-
2
)
)
〉
〈
E
w
(
i
-
1
)
,
w
(
i
-
1
)
〉
=
(
d
i
-
1
[
σ
i
〈
E
w
(
i
)
,
w
(
i
)
〉
+
α
i
-
1
〈
E
w
(
i
)
,
w
(
i
-
1
)
〉
(
〈
E
w
(
i
-
1
)
,
w
(
i
-
1
)
〉
)
-
1
(
〈
E
w
(
i
-
1
)
,
w
(
i
-
1
)
〉
)
-
1
+
β
i
-
1
〈
E
w
(
i
)
,
w
(
i
-
2
)
〉
]
)
×
(
〈
E
w
(
i
-
1
)
,
w
(
i
-
1
)
〉
)
-
1
=
d
i
-
1
σ
i
〈
E
w
(
i
)
,
w
(
i
)
〉
〈
E
w
(
i
-
1
)
,
w
(
i
-
1
)
〉
=
d
i
-
1
σ
i
d
i
d
i
-
1
=
d
i
σ
i
.
Here we use (128), E
A is symmetric, (129), (130), E is symmetric, (131), and (133).Letx
-
sym
(
n
) be the estimated solution corresponding to the Galerkin condition. Then
(147)
x
-
sym
(
n
)
=
x
(
0
)
+
W
n
-
1
y
-
(
n
)
,
where y
-
(
n
) satisfies this linear system
(148)
(
D
n
T
n
)
y
-
(
n
)
=
σ
0
e
n
.Letx
min
⁡
(
n
) be the estimated solution corresponding to the least squares problem. Then
(149)
x
min
⁡
(
n
)
=
x
(
0
)
+
W
n
-
1
y
(
n
)
,
where y
(
n
) satisfies this expression
(150)
min
⁡
y
(
n
)
∈
R
n
∥
(
D
n
+
1
T
^
n
+
1
)
y
(
n
)
-
σ
0
e
n
+
1
∥
.
We call x
min
⁡
(
n
) the nth iteration of the MMINRES method.Notice that if to matrixD
n
+
1
T
n
+
1 we add this bottom row
(151)
[
0,0
,
0
,
…
0,0
,
0
,
d
n
σ
n
]
1
×
n
and add this far-right column
(152)
[
0,0
,
0
,
…
0,0
,
0
,
d
n
-
1
β
n
,
d
n
α
n
]
1
×
n
+
1
T
,
see (132) and (138), then we obtain the matrix D
n
+
1
T
^
n
+
1.We define these Given rotation matrices(153)
Q
n
-
1
≡
Q
n
-
1
,
n
Q
n
-
2
,
n
-
1
Q
n
-
3
,
n
-
2
⋯
Q
3,4
Q
2,3
Q
1,2
,
where Q
i
,
i
+
1 is given by (23). Multiplying matrix Q
n
-
1 times both sides of linear system (148), we obtain this linear system
(154)
(
Q
n
-
1
D
n
T
n
)
y
-
(
n
)
=
Q
n
-
1
σ
0
e
n
,
where, from (137), the coefficient matrix is
(155)
Q
n
-
1
D
n
T
n
=
[
γ
0
δ
1
ε
2
γ
1
δ
2
ε
3
γ
2
δ
3
ε
4
⋱
⋱
⋱
γ
n
-
3
δ
n
-
2
ε
n
-
1
γ
n
-
2
δ
n
-
1
γ
-
n
-
1
]
n
×
n
≡
R
¯
n
,
and the right-hand side vector is
(156)
Q
n
-
1
σ
0
e
n
=
[
ζ
0
,
ζ
1
,
ζ
2
,
…
,
ζ
n
-
3
,
ζ
n
-
2
,
ζ
-
n
-
1
]
1
×
n
T
≡
z
(
n
)
.
Note that γ
-
n
-
1 isnot always nonzero, so that R
¯
n might be singular, but here, we assume that R
¯
n is nonsingular. Then we define this matrix factorization
(157)
W
n
-
1
=
P
¯
n
R
¯
n
,
where
(158)
P
¯
n
≡
[
p
(
0
)
,
p
(
1
)
,
p
(
2
)
,
…
,
p
(
n
-
3
)
,
p
(
n
-
2
)
,
p
-
(
n
-
1
)
]
n
×
n
.
Moreover, we define the right-hand side vector in (156) as
(159)
z
-
(
n
)
=
R
¯
n
y
-
(
n
)
.
From (147), we have, using (157) and (159),
(160)
x
-
sym
(
n
)
=
x
(
0
)
+
W
n
-
1
y
-
(
n
)
=
x
(
0
)
+
P
¯
n
R
¯
n
y
-
(
n
)
=
x
(
0
)
+
P
¯
n
z
-
(
n
)
.For the next iteratex
-
sym
(
n
+
1
), we need to solve this linear system
(161)
(
D
n
+
1
T
n
+
1
)
y
-
(
n
+
1
)
=
σ
0
e
n
+
1
,
where, by (132) and (137), the coefficient matrix is(162)
D
n
+
1
T
n
+
1
=
[
d
0
α
0
d
0
β
1
d
1
σ
1
d
1
α
1
d
1
β
2
d
2
σ
2
d
2
α
2
d
2
β
3
⋱
⋱
⋱
d
n
-
3
σ
n
-
3
d
n
-
3
α
n
-
3
d
n
-
3
β
n
-
2
d
n
-
2
σ
n
-
2
d
n
-
2
α
n
-
2
d
n
-
2
β
n
-
1
d
n
-
1
σ
n
-
1
d
n
-
1
α
n
-
1
d
n
-
1
β
n
d
n
σ
n
d
n
α
n
]
(
n
+
1
)
×
(
n
+
1
)
.MultiplyingQ
n
-
1 times both sides of linear system (161), we obtain this coefficient matrix(163)
Q
n
-
1
(
D
n
+
1
T
n
+
1
)
=
[
γ
0
δ
1
ε
2
γ
1
δ
2
ε
3
γ
2
δ
3
ε
4
⋱
⋱
⋱
γ
n
-
3
δ
n
-
2
ε
n
-
1
γ
n
-
2
δ
n
-
1
ε
n
γ
-
n
-
1
ψ
d
n
σ
n
d
n
α
n
]
(
n
+
1
)
×
(
n
+
1
)
.The last columns in matrices (162) and (163) are related as follows:
(164)
Q
n
-
1
,
n
[
0,0
,
0
,
…
0,0
,
0,0
,
d
n
-
1
β
n
,
d
n
α
n
]
(
n
+
1
)
×
1
T
=
[
0,0
,
0
,
…
0,0
,
0
,
ε
n
,
ψ
,
d
n
α
n
]
(
n
+
1
)
×
1
T
.
To eliminate d
n
σ
n, we compute the nth Givens rotation matrix Q
n
,
n
+
1 with
(165)
γ
n
-
1
=
γ
-
n
-
1
2
+
(
d
n
σ
n
)
2
,
c
n
=
γ
-
n
-
1
γ
n
-
1
,
s
n
=
-
d
n
σ
n
γ
n
-
1
.
Recall, by (23), that c
i
2
+
s
i
2
=
1. Next, we multiply matrix Q
n
,
n
+
1 times the coefficient matrix Q
n
-
1
(
D
n
+
1
T
n
+
1
), in (163),(166)
Q
n
,
n
+
1
Q
n
-
1
(
D
n
+
1
T
n
+
1
)
=
[
γ
0
δ
1
ε
2
γ
1
δ
2
ε
3
γ
2
δ
3
ε
4
⋱
⋱
⋱
γ
n
-
3
δ
n
-
2
ε
n
-
1
γ
n
-
2
δ
n
-
1
ε
n
γ
n
-
1
δ
n
γ
-
n
]
(
n
+
1
)
×
(
n
+
1
)
≡
R
¯
n
+
1
.Then multiplying matrixQ
n
,
n
+
1 times the right-hand side vector Q
n
-
1
σ
0
e
n
+
1, we obtain
(167)
Q
n
,
n
+
1
(
Q
n
-
1
σ
0
e
n
+
1
)
=
[
ζ
0
,
ζ
1
,
ζ
2
,
…
,
ζ
n
-
2
,
ζ
n
-
1
,
ζ
-
n
]
(
n
+
1
)
×
1
T
≡
z
-
n
+
1
.
Looking at the last columns in (163) and (166), we see that
(168)
Q
n
,
n
+
1
[
0,0
,
0
,
…
0,0
,
0
,
ε
n
,
ψ
,
d
n
α
n
]
(
n
+
1
)
×
1
T
=
[
0,0
,
0
,
…
,
0,0
,
0
,
ε
n
,
δ
n
,
γ
-
n
]
(
n
+
1
)
×
1
T
,
where
(169)
ζ
n
-
1
=
c
n
ζ
-
n
-
1
,
ζ
-
n
=
s
n
ζ
-
n
-
1
.
Recall, by (23), c
n
2
+
s
n
2
=
1.Before forming the iteratex
-
sym
(
n
+
1
), we consider this least square problem (150)
(170)
min
⁡
y
(
n
)
∈
R
n
∥
(
D
n
+
1
T
^
n
+
1
)
y
(
n
)
-
σ
0
e
n
+
1
∥
.
We have
(171)
∥
Q
n
,
n
+
1
Q
n
-
1
(
D
n
+
1
T
^
n
+
1
y
(
n
)
-
σ
0
e
n
+
1
)
∥
=
∥
[
R
n
0,0
,
0
,
…
,
0,0
,
0
]
(
n
+
1
)
×
n
y
(
n
)
-
[
ζ
0
ζ
1
ζ
2
⋮
ζ
n
-
2
ζ
n
-
1
ζ
-
n
]
(
n
+
1
)
×
1
∥
,
where
(172)
R
n
≡
[
γ
0
δ
1
ε
2
γ
1
δ
2
ε
3
γ
2
δ
3
ε
4
⋱
⋱
⋱
γ
n
-
4
δ
n
-
3
ε
n
-
2
γ
n
-
3
δ
n
-
2
ε
n
-
1
γ
n
-
2
δ
n
-
1
γ
n
-
1
]
n
×
n
.
Next define
(173)
z
(
n
)
≡
[
ζ
0
,
ζ
1
,
ζ
2
,
…
,
ζ
n
-
3
,
ζ
n
-
2
,
ζ
n
-
1
]
1
×
n
T
.Hence,y
(
n
) is the solution of this linear system
(174)
R
n
y
(
n
)
=
z
(
n
)
,
which minimizes the expression
(175)
min
⁡
y
(
n
)
∈
R
n
∥
(
D
n
+
1
T
^
n
+
1
)
y
(
n
)
-
σ
0
e
n
+
1
∥
,
and then
(176)
ζ
-
n
=
∥
(
D
n
+
1
T
^
n
+
1
)
y
(
n
)
-
σ
0
e
n
+
1
∥
.Ifσ
n
≠
0, then γ
n
≠
0 and R
n is nonsingular, and we can solve linear system (174) for y
(
n
). We discuss the case σ
n
=
0 later.By (149), let
(177)
x
min
⁡
(
n
)
=
x
(
0
)
+
W
n
-
1
y
(
n
)
=
x
(
0
)
+
(
W
n
-
1
R
n
-
1
)
z
(
n
)
,
using (174). Here
(178)
W
n
-
1
=
P
n
R
n
,
(179)
P
n
-
1
=
[
p
(
0
)
,
p
(
1
)
,
p
(
2
)
,
…
,
p
(
n
-
3
)
,
p
(
n
-
2
)
,
p
(
n
-
1
)
]
n
×
n
.
From (177) and (179), we have
(180)
x
min
⁡
(
n
)
=
x
(
0
)
+
P
n
z
(
n
)
=
x
min
⁡
(
n
-
1
)
+
ζ
n
-
1
p
(
n
-
1
)
,
where, by (172),
(181)
p
(
n
-
1
)
=
(
1
γ
n
-
1
)
[
w
(
n
-
1
)
-
δ
n
-
1
p
(
n
-
2
)
-
ε
n
-
1
p
(
n
-
3
)
]
.From (147), we obtain, by (159), (157), and (180),
(182)
x
-
sym
(
n
+
1
)
=
x
(
0
)
+
W
n
y
-
(
n
+
1
)
=
x
(
0
)
+
W
n
(
R
n
+
1
-
1
z
(
n
+
1
)
)
=
x
(
0
)
+
(
W
n
R
¯
n
+
1
-
1
)
z
-
(
n
+
1
)
=
x
(
0
)
+
P
¯
n
+
1
z
-
(
n
+
1
)
=
x
(
0
)
+
P
n
-
1
z
(
n
)
+
ζ
-
n
p
-
(
n
)
=
x
min
⁡
(
n
)
+
ζ
-
n
p
-
(
n
)
.We note thatx
-
sym
(
n
) is the estimated solution satisfying the Galerkin condition, while
(183)
x
min
⁡
(
n
)
=
x
(
0
)
+
W
n
-
1
y
(
n
)
,
where y
(
n
) minimizes this expression
(184)
min
⁡
y
(
n
)
∈
R
n
∥
(
D
n
+
1
T
^
n
+
1
)
y
(
n
)
-
σ
0
e
n
+
1
∥
.Proposition 1.
Ifσ
n
=
0 and w
~
(
n
)
=
0, then x
-
sym
(
n
) is the exact solution of A
u
=
b. Moreover, one obtains x
min
⁡
(
n
)
=
x
-
sym
(
n
).Proof.
We consider the residual vectorr
-
(
n
) corresponding to the iterate x
-
sym
(
n
). Then, by (147), we have
(185)
r
-
(
n
)
=
b
-
A
x
-
sym
(
n
)
=
b
-
A
(
x
(
0
)
+
W
n
-
1
y
-
(
n
)
)
=
(
b
-
A
x
(
0
)
)
-
(
A
W
n
-
1
)
y
-
(
n
)
=
r
(
0
)
-
(
A
W
n
-
1
)
y
-
(
n
)
.
Here y
-
(
n
) satisfies (148) and we have
(186)
(
D
n
T
n
)
y
-
(
n
)
=
σ
0
e
n
,
(187)
T
n
y
-
(
n
)
=
D
n
-
1
σ
0
e
n
.
Hence, starting from (185) and by using (134) and (187), we have
(188)
r
-
(
n
)
=
r
(
0
)
-
(
A
W
n
-
1
)
y
-
(
n
)
=
r
(
0
)
-
(
W
n
-
1
T
n
+
σ
n
w
(
n
)
e
n
T
)
y
-
(
n
)
=
r
(
0
)
-
W
n
-
1
(
T
n
y
-
(
n
)
)
-
σ
n
w
(
n
)
e
n
T
y
-
(
n
)
=
r
(
0
)
-
W
n
-
1
(
D
n
-
1
σ
0
e
n
)
-
σ
n
w
(
n
)
e
n
T
y
-
(
n
)
=
σ
0
w
(
0
)
-
σ
0
w
(
0
)
-
σ
n
w
(
n
)
e
n
T
y
-
(
n
)
=
0
-
σ
n
w
(
n
)
e
n
T
y
-
(
n
)
=
-
σ
n
η
-
n
w
(
n
)
,
since r
(
0
)
=
σ
0
w
(
0
). Here η
-
n is the nth component of the vector y
-
(
n
).
Ifσ
n
=
0, then r
-
(
n
)
=
0. Thus, we obtain x
-
sym
(
n
), which is the exact solution. It follows from (165) that if σ
n
=
0, then
(189)
c
n
=
γ
-
n
-
1
|
γ
-
n
-
1
|
=
{
1
,
γ
-
n
-
1
>
0
,
-
1
,
γ
-
n
-
1
<
0
,
s
n
=
0
.
Since
(190)
x
-
sym
(
n
)
=
x
(
0
)
+
W
n
-
1
y
-
(
n
)
,
R
¯
n
y
-
(
n
)
=
z
-
(
n
)
,
x
min
⁡
(
n
)
=
x
(
0
)
+
W
n
-
1
y
(
n
)
,
R
n
y
(
n
)
=
z
(
n
)
,
the only difference between R
¯
n and R
n is the (
k
,
k
)-entries, which are γ
-
n
-
1 and γ
n
-
1, respectively. Let the nth components of y
-
(
n
) and y
(
n
) be η
-
n and η
n, respectively. It follows that both matrices R
¯
n and R
n are triangular, where η
n
=
ζ
n
-
1
/
γ
n
-
1 and η
-
n
=
ζ
-
n
-
1
/
γ
-
n
-
1. By (169), we have
(191)
η
n
=
c
n
ζ
-
n
-
1
|
γ
-
n
-
1
|
=
ζ
-
n
-
1
γ
-
n
-
1
=
η
-
n
.
Hence, we have
(192)
y
(
n
)
=
y
-
(
n
)
,
x
min
⁡
(
n
)
=
x
-
sym
(
n
)
.


## 11. Final Notes

In the MGMRES method, we solve this linear system(193)
(
T
~
n
+
1
T
D
n
+
1
T
n
+
1
)
y
(
n
+
1
)
=
σ
0
e
1
,
while in the MMINRES method, we solve this linear system
(194)
(
T
~
n
+
1
T
T
~
n
+
1
)
y
(
n
+
1
)
=
D
n
+
1
σ
0
e
1
.Clearly, the MMINRES method and the MGMRES method are the same when the diagonal matrixD
n
+
1 is the identity matrix I
n
+
1.See also Kincaid et al. [8].



---

*Source: 628069-2014-10-27.xml*