# A Smoothing Process of Multicolor Relaxation for Solving Partial Differential Equation by Multigrid Method

Authors: Xingwen Zhu; Lixiang Zhang
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

This paper is concerned with a novel methodology of smoothing analysis process of multicolor point relaxation by multigrid method for solving elliptically partial differential equations (PDEs). The objective was firstly focused on the two-color relaxation technique on the local Fourier analysis (LFA) and then generalized to the multicolor problem. As a key starting point of the problems under consideration, the mathematical constitutions among Fourier modes with various frequencies were constructed as a base to expand two-color to multicolor smoothing analyses. Two different invariant subspaces based on the 2h-harmonics for the two-color relaxation with two and four Fourier modes were constructed and successfully used in smoothing analysis process of Poisson’s equation for the two-color point Jacobi relaxation. Finally, the two-color smoothing analysis was generalized to the multicolor smoothing analysis problems by multigrid method based on the invariant subspaces constructed.


---

## Body

## 1. Introduction

Multigrid methods [1–6] are generally considered as one of the fastest numerical methods for solving complex partial differential equations (PDEs), for example, Navier-Stokes equation in computational fluid dynamics (CFD). As we know, the speed of the multigrid computational convergence depends closely on the numerical properties of the underlying problem of PDEs, for example, equating type and discretizing stencil. Meanwhile, a variety of algorithms for the components in multigrid are of great importance, for example, the processing methods based on smoothing, restriction, prolongation processes, and so on. So, an appropriate choice for the available components has a great impact on the overall performance for specific problems.Local Fourier analysis (LFA) [5, 7–12] is a very useful tool to predict asymptotic convergence factors of the multigrid methods for PDEs with high order accuracy. Therefore it is widely used to design efficient multigrid algorithms. In LFA an infinite regular grid needs to be considered and boundary conditions need to be ignored. On an infinite grid, the discrete solutions and the corresponding errors are represented by linear combinations of certain complex exponential functions. Thus, Fourier modes are often used to form a unitary basis of the subspace of the grid functions with bounded norms [5, 7, 12]. The LFA monograph by Wienands and Joppich [11] provides an excellent background for experimenting with Fourier analysis. Recent advances in this context included LFA for triangular grids [13, 14], hexagonal meshes [15], semistructured meshes [16], multigrid with overlapping smoothers [17], multigrid with a preconditioner as parameters [18], and full multigrid method [19]. In [8], an LFA for multigrid methods on the finite element discretization of a 2D curl-curl equation with a quadrilateral grid was introduced.A general definition on the multicolor relaxation was provided in [20]. Smoothing analysis of the two-color relaxation on LFA was given in [21–24], and the four-color relaxation with tetrahedral grids was presented in [16, 25]. In [26], a parallel multigrid method for solving Navier-Stokes equation was investigated and a multigrid Poisson equation solver was employed in [27]. A parallel successive overrelaxation (SOR) algorithm for solving the Poisson problem was discussed in [28], and multicolor SOR methods were studied in [29].In the present paper, a novel smoothing analysis process of multicolor relaxation on LFA is provided with details. An important coupled relation among Fourier modes with various frequencies is constructed and expanded to the multicolor smoothing analysis. The roles of the Fourier modes with the high and low frequencies in the proposed method are well characterized. Thus, by the two invariant subspaces based on the 2h-harmonics the two-color smoothing analysis process is well generalized to the multicolor problems.


## 2. LFA in Multigrid

### 2.1. General Definition

A rigorous base of the local mode analysis in multigrid was elaborated [12]. Herein, we are following [11] as a starting point of our framework.A generally linear scalar constant-coefficient system without boundary conditions is described with a discrete problem with infinite grid; that is,(1)
L
h
u
h
(
x
⃑
)
=
∑
n
⃑
∈
J
l
n
⃑
u
h
(
x
⃑
+
n
⃑
·
h
⃑
)
=
f
h
(
x
⃑
)
,
x
⃑
∈
G
h
in which an infinite grid is stated as
(2)
G
h
=
{
x
⃑
=
(
k
1
h
1
,
…
,
k
d
h
d
)
∣
k
⃑
=
(
k
1
,
…
,
k
d
)
∈
Z
d
}
,
where h
⃑
=
(
h
1
,
h
2
,
…
,
h
d
) is the mesh size, d denotes the dimension of  x
⃑, the discrete operator is given by
(3)
L
h
:
=
[
l
n
⃑
]
h
,
and l
n
⃑
∈
R with n
⃑
∈
J is the stencil coefficients [3–5] of L
h for (2), J
⊂
Z
d containing (
0,0
,
…
,
0
), and n
⃑
·
h
⃑
=
^
(
n
1
h
1
,
n
2
h
2
,
…
,
n
d
h
d
). From [11, 20], the Fourier eigenfunctions of the constant-coefficient infinite grid operator L
h in (1) are given by
(4)
φ
h
(
θ
⃑
,
x
⃑
)
:
=
∏
j
=
1
d
exp
⁡
⁡
(
i
θ
j
x
j
h
j
)
=
exp
⁡
(
i
θ
⃑
k
⃑
)
,
where x
⃑
∈
G
h, θ
⃑
=
(
θ
1
,
θ
2
,
…
,
θ
d
)
∈
Θ
=
(
-
π
,
π
]
d denotes the Fourier frequency, θ
⃑
k
⃑
=
^
θ
1
k
1
+
θ
2
k
2
+
⋯
+
θ
d
k
d, and φ
h
(
θ
⃑
,
x
⃑
) is called Fourier mode [3, 5, 20], which is orthogonal with respect to the scaled Euclidean inner product [3, 5, 10]. On grid (2), the corresponding eigenvalues of L
h are expressed by
(5)
L
h
φ
h
(
θ
⃑
,
x
⃑
)
=
L
~
h
(
θ
⃑
)
φ
h
(
θ
⃑
,
x
⃑
)
with
(6)
L
~
h
(
θ
⃑
)
:
=
∑
n
⃑
∈
J
l
n
⃑
exp
⁡
(
i
θ
⃑
n
⃑
)
called Fourier symbol of L
h. Further, a Fourier subspace with the bounded infinite grid function V
h
∈
F
(
G
h
), that is F
(
G
h
)
⊆
F
h, is defined as
(7)
F
h
∶
=
span
⁡
{
φ
h
(
θ
⃑
,
x
⃑
)
∣
θ
⃑
∈
Θ
=
(
-
π
,
π
]
d
}
in which Θ
low
=
(
-
π
/
2
,
π
/
2
]
d is referred to the low frequency and Θ
high
=
Θ
∖
Θ
low is referred to the high frequency. As a standard multigrid coarsening [11], a case of H
⃑
=
2
h
⃑ is considered, and infinite coarse grid G
H is stated as
(8)
G
H
=
{
x
⃑
=
(
k
1
H
1
,
k
2
H
2
,
…
,
k
d
H
d
)
∣
k
⃑
=
(
k
1
,
k
2
,
…
,
k
d
)
∈
Z
d
k
⃑
=
(
k
1
,
k
2
,
…
,
k
d
)
∈
Z
d
}
.


### 2.2. Smoothing Analysis of Multigrid Relaxation

For multigrid relaxationS
h of discrete operator L
h on the infinite grid (2), if (4) are the eigenfunctions of S
h, then S
~
h
(
θ
⃑
) is the Fourier symbol of S
h. For pattern relaxation [11], (4) are no longer the eigenfunctions of relaxation operator S
h. However, it leaves certain low-dimensional subspaces of (4) invariant yielding a block-diagonal matrix of smoothing operator consisting of small blocks. As presented in [10, 11], the 2
h-harmonics of (4) is defined as
(9)
F
2
h
(
θ
⃑
)
≔
span
⁡
{
φ
h
(
θ
⃑
α
⃑
,
x
⃑
)
∣
α
⃑
=
(
α
1
,
…
,
α
d
)
,
α
m
∈
{
0,1
}
,
m
=
1
,
…
,
d
φ
h
(
θ
⃑
α
⃑
,
x
⃑
)
}
,
where θ
⃑
=
θ
⃑
(
0
,
…
,
0
)
∈
Θ
low and θ
⃑
α
⃑
=
θ
⃑
(
0
,
…
,
0
)
-
(
α
1
sign
⁡
(
θ
1
)
,
…
,
α
d
sign
⁡
(
θ
d
)
)
π. If relaxation operator S
h satisfies
(10)
S
h
(
φ
h
(
θ
⃑
(
0
,
…
,
0
)
,
x
⃑
)
,
…
,
φ
h
(
θ
⃑
(
0
,
…
,
1
)
,
x
⃑
)
)
=
(
φ
h
(
θ
⃑
(
0
,
…
,
0
)
,
x
⃑
)
,
…
,
φ
h
(
θ
⃑
(
0
,
…
,
1
)
,
x
⃑
)
)
S
^
h
(
θ
⃑
)
,
that is, S
h
:
F
2
h
→
F
2
h, the matrix S
^
h
(
θ
⃑
) is called Fourier representation of S
h. Furthermore, an idea coarse-grid correction operator Q
h
H is introduced [11] to drop out the low-frequency modes and to keep the high-frequency modes. So, it is clear that Q
h
H is a projection operator onto the subspace of the high-frequency modes
(11)
F
high
(
θ
⃑
)
:
=
span
⁡
{
φ
h
(
θ
⃑
,
x
⃑
)
∣
θ
⃑
∈
Θ
high
}
.
By the same way, a subspace of the low-frequency modes is defined as
(12)
F
low
(
θ
⃑
)
:
=
span
⁡
{
φ
h
(
θ
⃑
,
x
⃑
)
∣
θ
⃑
∈
Θ
low
}
.
Thus, a general coarsening strategy [11] is stated as
(13)
Q
h
H
φ
h
(
θ
⃑
,
x
⃑
)
:
=
{
φ
h
(
θ
⃑
,
x
⃑
)
φ
h
(
θ
⃑
,
x
⃑
)
∈
F
high
0
φ
h
(
θ
⃑
,
x
⃑
)
∈
F
low
.
Consequently, a smoothing factor [11] on the Fourier modes for the multigrid relaxation, S
h
(
ω
) and Q
h
H, is yielded as
(14)
ρ
(
v
,
ω
)
=
sup
⁡
θ
⃑
∈
Θ
low
ρ
(
Q
^
h
2
h
S
^
h
v
(
θ
⃑
,
ω
)
)
v
,
where ω is the relaxation parameter, v
=
v
1
+
v
2 denotes the sum of pre- and postsmoothing steps, Q
^
h
H and S
^
h
(
θ
⃑
,
ω
) are the Fourier representations of S
h
(
ω
) and Q
h
H, respectively, and ρ
(
M
) denotes the spectral radius of the matrix M.


## 2.1. General Definition

A rigorous base of the local mode analysis in multigrid was elaborated [12]. Herein, we are following [11] as a starting point of our framework.A generally linear scalar constant-coefficient system without boundary conditions is described with a discrete problem with infinite grid; that is,(1)
L
h
u
h
(
x
⃑
)
=
∑
n
⃑
∈
J
l
n
⃑
u
h
(
x
⃑
+
n
⃑
·
h
⃑
)
=
f
h
(
x
⃑
)
,
x
⃑
∈
G
h
in which an infinite grid is stated as
(2)
G
h
=
{
x
⃑
=
(
k
1
h
1
,
…
,
k
d
h
d
)
∣
k
⃑
=
(
k
1
,
…
,
k
d
)
∈
Z
d
}
,
where h
⃑
=
(
h
1
,
h
2
,
…
,
h
d
) is the mesh size, d denotes the dimension of  x
⃑, the discrete operator is given by
(3)
L
h
:
=
[
l
n
⃑
]
h
,
and l
n
⃑
∈
R with n
⃑
∈
J is the stencil coefficients [3–5] of L
h for (2), J
⊂
Z
d containing (
0,0
,
…
,
0
), and n
⃑
·
h
⃑
=
^
(
n
1
h
1
,
n
2
h
2
,
…
,
n
d
h
d
). From [11, 20], the Fourier eigenfunctions of the constant-coefficient infinite grid operator L
h in (1) are given by
(4)
φ
h
(
θ
⃑
,
x
⃑
)
:
=
∏
j
=
1
d
exp
⁡
⁡
(
i
θ
j
x
j
h
j
)
=
exp
⁡
(
i
θ
⃑
k
⃑
)
,
where x
⃑
∈
G
h, θ
⃑
=
(
θ
1
,
θ
2
,
…
,
θ
d
)
∈
Θ
=
(
-
π
,
π
]
d denotes the Fourier frequency, θ
⃑
k
⃑
=
^
θ
1
k
1
+
θ
2
k
2
+
⋯
+
θ
d
k
d, and φ
h
(
θ
⃑
,
x
⃑
) is called Fourier mode [3, 5, 20], which is orthogonal with respect to the scaled Euclidean inner product [3, 5, 10]. On grid (2), the corresponding eigenvalues of L
h are expressed by
(5)
L
h
φ
h
(
θ
⃑
,
x
⃑
)
=
L
~
h
(
θ
⃑
)
φ
h
(
θ
⃑
,
x
⃑
)
with
(6)
L
~
h
(
θ
⃑
)
:
=
∑
n
⃑
∈
J
l
n
⃑
exp
⁡
(
i
θ
⃑
n
⃑
)
called Fourier symbol of L
h. Further, a Fourier subspace with the bounded infinite grid function V
h
∈
F
(
G
h
), that is F
(
G
h
)
⊆
F
h, is defined as
(7)
F
h
∶
=
span
⁡
{
φ
h
(
θ
⃑
,
x
⃑
)
∣
θ
⃑
∈
Θ
=
(
-
π
,
π
]
d
}
in which Θ
low
=
(
-
π
/
2
,
π
/
2
]
d is referred to the low frequency and Θ
high
=
Θ
∖
Θ
low is referred to the high frequency. As a standard multigrid coarsening [11], a case of H
⃑
=
2
h
⃑ is considered, and infinite coarse grid G
H is stated as
(8)
G
H
=
{
x
⃑
=
(
k
1
H
1
,
k
2
H
2
,
…
,
k
d
H
d
)
∣
k
⃑
=
(
k
1
,
k
2
,
…
,
k
d
)
∈
Z
d
k
⃑
=
(
k
1
,
k
2
,
…
,
k
d
)
∈
Z
d
}
.


## 2.2. Smoothing Analysis of Multigrid Relaxation

For multigrid relaxationS
h of discrete operator L
h on the infinite grid (2), if (4) are the eigenfunctions of S
h, then S
~
h
(
θ
⃑
) is the Fourier symbol of S
h. For pattern relaxation [11], (4) are no longer the eigenfunctions of relaxation operator S
h. However, it leaves certain low-dimensional subspaces of (4) invariant yielding a block-diagonal matrix of smoothing operator consisting of small blocks. As presented in [10, 11], the 2
h-harmonics of (4) is defined as
(9)
F
2
h
(
θ
⃑
)
≔
span
⁡
{
φ
h
(
θ
⃑
α
⃑
,
x
⃑
)
∣
α
⃑
=
(
α
1
,
…
,
α
d
)
,
α
m
∈
{
0,1
}
,
m
=
1
,
…
,
d
φ
h
(
θ
⃑
α
⃑
,
x
⃑
)
}
,
where θ
⃑
=
θ
⃑
(
0
,
…
,
0
)
∈
Θ
low and θ
⃑
α
⃑
=
θ
⃑
(
0
,
…
,
0
)
-
(
α
1
sign
⁡
(
θ
1
)
,
…
,
α
d
sign
⁡
(
θ
d
)
)
π. If relaxation operator S
h satisfies
(10)
S
h
(
φ
h
(
θ
⃑
(
0
,
…
,
0
)
,
x
⃑
)
,
…
,
φ
h
(
θ
⃑
(
0
,
…
,
1
)
,
x
⃑
)
)
=
(
φ
h
(
θ
⃑
(
0
,
…
,
0
)
,
x
⃑
)
,
…
,
φ
h
(
θ
⃑
(
0
,
…
,
1
)
,
x
⃑
)
)
S
^
h
(
θ
⃑
)
,
that is, S
h
:
F
2
h
→
F
2
h, the matrix S
^
h
(
θ
⃑
) is called Fourier representation of S
h. Furthermore, an idea coarse-grid correction operator Q
h
H is introduced [11] to drop out the low-frequency modes and to keep the high-frequency modes. So, it is clear that Q
h
H is a projection operator onto the subspace of the high-frequency modes
(11)
F
high
(
θ
⃑
)
:
=
span
⁡
{
φ
h
(
θ
⃑
,
x
⃑
)
∣
θ
⃑
∈
Θ
high
}
.
By the same way, a subspace of the low-frequency modes is defined as
(12)
F
low
(
θ
⃑
)
:
=
span
⁡
{
φ
h
(
θ
⃑
,
x
⃑
)
∣
θ
⃑
∈
Θ
low
}
.
Thus, a general coarsening strategy [11] is stated as
(13)
Q
h
H
φ
h
(
θ
⃑
,
x
⃑
)
:
=
{
φ
h
(
θ
⃑
,
x
⃑
)
φ
h
(
θ
⃑
,
x
⃑
)
∈
F
high
0
φ
h
(
θ
⃑
,
x
⃑
)
∈
F
low
.
Consequently, a smoothing factor [11] on the Fourier modes for the multigrid relaxation, S
h
(
ω
) and Q
h
H, is yielded as
(14)
ρ
(
v
,
ω
)
=
sup
⁡
θ
⃑
∈
Θ
low
ρ
(
Q
^
h
2
h
S
^
h
v
(
θ
⃑
,
ω
)
)
v
,
where ω is the relaxation parameter, v
=
v
1
+
v
2 denotes the sum of pre- and postsmoothing steps, Q
^
h
H and S
^
h
(
θ
⃑
,
ω
) are the Fourier representations of S
h
(
ω
) and Q
h
H, respectively, and ρ
(
M
) denotes the spectral radius of the matrix M.


## 3. Smoothing Analysis of Two-Color Relaxation

To develop two different processes of LFA for the two-color relaxation, grid (2) is divided into two disjoint subsets G
h
R and G
h
B, referring to as the red and black points, respectively. Two process steps [11] are required to construct a complete two-color relaxation S
h
R
B
(
ω
). In the first step (S
h
R
(
ω
)), the unknowns located at the red points are only smoothed, whereas the unknowns at the black points remain to be unchanged. Then, in the second step (S
h
B
(
ω
)), the unknowns at the black points are changed by using the new values calculated with the red points in the first step. So, a complete red-black point process is obtained by iteration
(15)
S
h
R
B
(
ω
)
=
S
h
B
(
ω
)
S
h
R
(
ω
)
.
From the process mentioned above, it is noted that the Fourier modes (4) are no longer eigenfunctions of (15) on grid (2) because the relaxation operator is used.


### 3.1. Invariant Subspaces for Two-Color Relaxation

A new smoothing analysis process of the two-color relaxation is proposed with details. The proposed process is different with [11, 20–24]. A novel constitution among the Fourier modes with various frequencies is developed as a base of the smoothing analysis process. The analysis process is proved to be valuable.The gridG
h
=
{
x
⃑
=
(
k
1
h
1
,
k
2
h
2
)
∣
k
⃑
=
(
k
1
,
k
2
)
∈
Z
2
} is divided into two disjoint subsets G
h
0 and G
h
1; that is, G
h
=
G
h
0
∪
G
h
1 with
(16)
G
h
β
=
{
x
⃑
=
(
k
1
h
1
,
k
2
h
2
)
∣
k
1
+
k
2
=
β
mod
⁡
2
,
k
⃑
∈
Z
2
}
,
where β
=
0,1. According to (16), the subspace of the 2h-harmonics (9) is redefined as
(17)
F
2
h
2
(
θ
⃑
)
:
=
span
⁡
{
φ
h
(
θ
⃑
0
,
x
⃑
)
,
φ
h
(
θ
⃑
1
,
x
⃑
)
}
with θ
⃑
=
(
θ
1
,
θ
2
)
∈
Θ
low
=
(
-
π
/
2
,
π
/
2
]
2, where θ
⃑
α
=
(
θ
⃑
+
(
α
,
α
)
π
)
mod
⁡
2
π, α
=
0,1. Thus, the constitutions among the various Fourier modes defined by (16) and (17) are presented as follows.Proposition 1.
For∀
x
⃑
∈
G
h, ∀
(
k
1
,
k
2
)
∈
Z
2, and ∀
α
∈
{
0,1
}, if θ
⃑
∈
Θ
low, then the following formulation holds:
(18)
φ
h
(
θ
⃑
α
,
x
⃑
)
=
exp
⁡
[
i
π
α
(
k
1
+
k
2
)
]
φ
h
(
θ
⃑
,
x
⃑
)
.Proof.
From (4), for ∀
x
⃑
∈
G
h, it holds for φ
h
(
θ
⃑
α
,
x
⃑
)
=
exp
⁡
(
i
θ
⃑
α
k
⃑
). From (17), ∃
n
⃑
=
(
n
1
,
n
2
)
∈
Z
2 is subjected to θ
⃑
α
=
(
θ
1
+
α
π
,
θ
2
+
α
π
)
+
2
π
n
⃑. Then
(19)
θ
⃑
α
k
⃑
=
θ
⃑
k
⃑
+
π
α
(
k
1
+
k
2
)
+
2
π
n
⃑
k
⃑
holds. Thus,
(20)
φ
h
(
θ
⃑
α
,
x
⃑
)
=
exp
⁡
⁡
(
i
θ
⃑
α
k
⃑
)
=
exp
⁡
⁡
[
i
π
α
(
k
1
+
k
2
)
]
exp
⁡
⁡
(
i
θ
⃑
k
⃑
)
=
exp
⁡
[
i
π
α
(
k
1
+
k
2
)
]
φ
h
(
θ
⃑
,
x
⃑
)
.
Proposition 1 follows.Proposition 2.
For∀
α, β
∈
{
0,1
}, and ∀
x
⃑
∈
G
h
β, if θ
⃑
∈
Θ
l
o
w, then the following formulation holds:
(21)
φ
h
(
θ
⃑
α
,
x
⃑
)
=
exp
⁡
(
i
π
α
β
)
φ
h
(
θ
⃑
,
x
⃑
)
.Proof.
By Proposition1 and G
h
β
⊆
G
h, for ∀
x
⃑
∈
G
h
β, then
(22)
φ
h
(
θ
⃑
α
,
x
⃑
)
=
exp
⁡
[
i
π
α
(
k
1
+
k
2
)
]
φ
h
(
θ
⃑
,
x
⃑
)
,
where (
k
1
,
k
2
)
∈
Z
2. For x
⃑
∈
G
h
β, from (16), ∃
p
∈
Z is subjected to k
1
+
k
2
=
β
+
2
p; hence,
(23)
φ
h
(
θ
⃑
α
,
x
⃑
)
=
exp
⁡
[
i
π
α
(
β
+
2
p
)
]
φ
h
(
θ
⃑
,
x
⃑
)
=
exp
⁡
(
i
π
α
β
)
φ
h
(
θ
⃑
,
x
⃑
)
.
Proposition 2 holds.Subsequently, the smoothing analysis process of the two-color relaxation on the subspace of the2
h-harmonics (17) is conducted. By (15) and (16) and without loss of generality, let G
h
0 and G
h
1 correspond to G
h
R and G
h
B, respectively; thus (15) is rewritten as
(24)
S
h
01
(
ω
)
=
S
h
1
(
ω
)
S
h
0
(
ω
)
.Theorem 3.
The iteration operatorS
h
01
(
ω
) for the two-color relaxation leaves the subspace of the 2h-harmonics (17) to be invariant.Proof.
From the process of the two-color relaxation, the operatorS
h
β
(
ω
) of grid (16) is
(25)
S
h
β
(
ω
)
φ
h
(
θ
⃑
,
x
⃑
)
=
{
S
~
h
β
(
θ
⃑
,
ω
)
φ
h
(
θ
⃑
,
x
⃑
)
∀
x
⃑
∈
G
h
β
φ
h
(
θ
⃑
,
x
⃑
)
∀
x
⃑
∉
G
h
β
,
where S
~
h
β
(
θ
⃑
,
ω
) is Fourier symbol of S
h
β
(
ω
) on grid (16) with β
=
0,1. From (10) and (25), now it is proved that the subspace of the 2h-harmonics (17) is invariant for the iteration operator (24). Because of (17), we need to find out two complex numbers a
0 and a
1 with ∀
α, β
∈
{
0,1
} and make them subjected to
(26)
S
h
β
(
ω
)
φ
h
(
θ
⃑
α
,
x
⃑
)
=
a
0
φ
h
(
θ
⃑
0
,
x
⃑
)
+
a
1
φ
h
(
θ
⃑
1
,
x
⃑
)
.
From (25), the right hand side of (26) is written as
(27)
S
h
β
(
ω
)
φ
h
(
θ
⃑
α
,
x
⃑
)
=
{
S
~
h
β
(
θ
⃑
α
,
ω
)
φ
h
(
θ
⃑
α
,
x
⃑
)
∀
x
⃑
∈
G
h
β
φ
h
(
θ
⃑
α
,
x
⃑
)
∀
x
⃑
∉
G
h
β
.
By Propositions 1 and 2, the right hand side of (27) is expressed as
(28)
S
h
β
(
ω
)
φ
h
(
θ
⃑
α
,
x
⃑
)
=
{
S
~
h
β
(
θ
⃑
α
,
ω
)
exp
⁡
⁡
(
i
α
β
π
)
φ
h
(
θ
⃑
,
x
⃑
)
∀
x
⃑
∈
G
h
β
exp
⁡
⁡
[
i
α
(
1
-
β
)
π
]
φ
h
(
θ
⃑
,
x
⃑
)
∀
x
⃑
∉
G
h
β
.
Taking A
α
β
=
S
~
h
β
(
θ
⃑
α
,
ω
), (28) is written as
(29)
S
h
β
(
ω
)
φ
h
(
θ
⃑
α
,
x
⃑
)
=
{
A
α
β
exp
⁡
⁡
(
i
α
β
π
)
φ
h
(
θ
⃑
,
x
⃑
)
∀
x
⃑
∈
G
h
β
exp
⁡
⁡
[
i
α
(
1
-
β
)
π
]
φ
h
(
θ
⃑
,
x
⃑
)
∀
x
⃑
∉
G
h
β
.
From Propositions 1 and 2, the left hand side of (26) is written as
(30)
a
0
φ
h
(
θ
⃑
0
,
x
⃑
)
+
a
1
φ
h
(
θ
⃑
1
,
x
⃑
)
=
{
(
a
0
+
a
1
exp
⁡
(
i
β
π
)
)
φ
h
(
θ
⃑
,
x
⃑
)
x
⃑
∈
G
h
β
(
a
0
+
a
1
exp
⁡
[
i
(
1
-
β
)
π
]
)
φ
h
(
θ
⃑
,
x
⃑
)
x
⃑
∉
G
h
β
.
Hence, from (26), (29), and (30), a set of two linear equations on a
0 and a
1 is given as
(31)
a
0
+
a
1
exp
⁡
⁡
(
i
β
π
)
=
A
α
β
exp
⁡
⁡
(
i
α
β
π
)
a
0
+
a
1
exp
⁡
[
i
(
1
-
β
)
π
]
=
exp
⁡
[
i
α
(
1
-
β
)
π
]
,
where α, β
∈
{
0,1
}. Therefore, from (31), it is concluded that there exist two complex numbers a
0 and a
1 that are subjected to (26). From (10), (17), and (26), solving linear equation (31), the Fourier representations of the iteration operators S
h
0
(
ω
) and S
h
1
(
ω
) are obtained as
(32)
S
^
h
0
(
θ
⃑
,
ω
)
=
1
2
(
A
0
0
+
1
A
1
0
-
1
A
0
0
-
1
A
1
0
+
1
)
,
S
^
h
1
(
θ
⃑
,
ω
)
=
1
2
(
A
0
1
+
1
-
A
1
1
+
1
-
A
0
1
+
1
A
1
1
+
1
)
,
where A
α
β
=
S
~
h
β
(
θ
⃑
α
,
ω
) and α, β
∈
{
0,1
}. Furthermore, from (32), the Fourier representations of the two-color relaxation S
h
01
(
ω
) are
(33)
S
^
h
01
(
θ
⃑
,
ω
)
=
S
^
h
1
(
θ
⃑
,
ω
)
S
^
h
0
(
θ
⃑
,
ω
)
=
1
2
(
A
0
1
+
1
-
A
1
1
+
1
-
A
0
1
+
1
A
1
1
+
1
)
·
1
2
(
A
0
0
+
1
A
1
0
-
1
A
0
0
-
1
A
1
0
+
1
)
.
From (10), Theorem 3 holds.


### 3.2. Invariant Subspaces on Four Fourier Modes for Two-Color Relaxation

We need to develop a Fourier representation of the two-color relaxation in the subspace of the 2h-harmonics with four Fourier modes. By following (9), for 2D system, another subspace of the 2h-harmonics is given as
(34)
F
2
h
*
(
θ
⃑
)
:
=
span
⁡
{
φ
h
(
θ
⃑
α
⃑
,
x
⃑
)
∣
α
⃑
=
(
α
1
,
α
2
)
,
α
m
∈
{
0,1
}
,
m
=
1,2
φ
h
(
θ
⃑
α
⃑
,
x
⃑
)
}
with θ
⃑
=
(
θ
1
,
θ
2
)
=
θ
⃑
(
0,0
)
∈
Θ
low
=
(
-
π
/
2
,
π
/
2
]
2, θ
⃑
α
⃑
=
θ
⃑
(
0,0
)
-
(
α
1
sign
⁡
(
θ
1
)
,
α
2
sign
⁡
(
θ
2
)
)
π.For the sake of convenient analysis, takingθ
⃑
α
⃑
=
θ
⃑
(
α
1
,
α
2
)
=
θ
⃑
α
1
α
2, for example, θ
⃑
(
0,0
)
=
θ
⃑
00, then F
2
h
*
(
θ
⃑
) is defined as
(35)
F
2
h
*
(
θ
⃑
)
:
=
span
⁡
{
φ
h
(
θ
⃑
00
,
x
⃑
)
,
φ
h
(
θ
⃑
11
,
x
⃑
)
,
φ
h
(
θ
⃑
10
,
x
⃑
)
,
φ
h
(
θ
⃑
01
,
x
⃑
)
}
.
Meanwhile, the grid G
h is divided into four subsets [11] as
(36)
G
h
=
G
h
00
∪
G
h
11
∪
G
h
10
∪
G
h
01
,
where G
h
η
⃑
=
{
x
⃑
=
(
k
1
h
1
,
k
2
h
2
)
∣
k
m
=
η
m
mod
⁡
2
,
m
=
1,2
} and η
⃑
=
(
η
1
,
η
2
)
∈
Λ
=
{
00,11,10,01
}. The red and black grid points corresponding with G
h are thus obtained as
(37)
G
h
R
=
G
h
00
∪
G
h
11
,
G
h
B
=
G
h
10
∪
G
h
01
.
Therefore, a constitutive relationship among the various Fourier 2h-harmonics is constructed.Proposition 4.
For∀
x
⃑
∈
G
h, ∀
k
⃑
=
(
k
1
,
k
2
)
∈
Z
2, and ∀
α
⃑
∈
Λ, if θ
⃑
∈
Θ
l
o
w, the following equation is yielded as
(38)
φ
h
(
θ
⃑
α
⃑
,
x
⃑
)
=
exp
⁡
(
-
i
π
α
⃑
k
⃑
)
φ
h
(
θ
⃑
,
x
⃑
)
.Proposition 5.
For∀
x
⃑
∈
G
h
β
⃑, ∀
k
⃑
=
(
k
1
,
k
2
)
∈
Z
2, and ∀
α
⃑
,
β
⃑
∈
Λ, if θ
⃑
∈
Θ
l
o
w, the following equation is yielded as
(39)
φ
h
(
θ
⃑
α
⃑
,
x
⃑
)
=
exp
⁡
⁡
(
-
i
π
α
⃑
β
⃑
)
φ
h
(
θ
⃑
,
x
⃑
)
.
The proof of Propositions 5 and 4 is similar to Propositions 2 and 1.Subsequently, a smoothing analysis process of the two-color relaxation on the subspace of the2
h-harmonics (35) is obtained.Theorem 6.
The iteration operator (15) for the two-color relaxation leaves the subspace of the 2h-harmonics (35) to be invariant 0.Proof.
Similar to the proof of Theorem3, from process of the two-color relaxation and (15), operators S
h
R
(
ω
) and S
h
B
(
ω
) of the grid (37) are
(40)
S
h
R
(
ω
)
φ
h
(
θ
⃑
α
⃑
,
x
⃑
)
=
{
S
~
h
R
(
θ
⃑
α
⃑
,
ω
)
φ
h
(
θ
⃑
α
⃑
,
x
⃑
)
∀
x
⃑
∈
G
h
R
φ
h
(
θ
⃑
α
⃑
,
x
⃑
)
∀
x
⃑
∉
G
h
R
(41)
S
h
B
(
ω
)
φ
h
(
θ
⃑
α
⃑
,
x
⃑
)
=
{
S
~
h
B
(
θ
⃑
α
⃑
,
ω
)
φ
h
(
θ
⃑
α
⃑
,
x
⃑
)
∀
x
⃑
∈
G
h
B
φ
h
(
θ
⃑
α
⃑
,
x
⃑
)
∀
x
⃑
∉
G
h
B
,
where S
~
h
R
(
θ
⃑
α
⃑
,
ω
) and S
~
h
B
(
θ
⃑
α
⃑
,
ω
) are Fourier symbols of S
h
R
(
ω
) and S
h
R
(
ω
) with φ
h
(
θ
⃑
α
⃑
,
x
⃑
) on the corresponding grids (37), respectively, and α
⃑
∈
Λ. From (15), in order to prove S
h
R
B
(
ω
)
:
F
2
h
*
(
θ
⃑
)
→
F
2
h
*
(
θ
⃑
) with θ
⃑
∈
Θ
low, we need to find out four complex numbers a
00, a
11, a
10, and a
01 subjected to
(42)
S
h
R
(
ω
)
φ
h
(
θ
⃑
α
⃑
,
x
⃑
)
=
a
00
φ
h
(
θ
⃑
00
,
x
⃑
)
+
a
11
φ
h
(
θ
⃑
11
,
x
⃑
)
+
a
10
φ
h
(
θ
⃑
10
,
x
⃑
)
+
a
01
φ
h
(
θ
⃑
01
,
x
⃑
)
.
Meanwhile, we also need to find other four complex numbers b
00, b
11, b
10, and b
01 and make them subjected to
(43)
S
h
B
(
ω
)
φ
h
(
θ
⃑
α
⃑
,
x
⃑
)
=
b
00
φ
h
(
θ
⃑
00
,
x
⃑
)
+
b
11
φ
h
(
θ
⃑
11
,
x
⃑
)
+
b
10
φ
h
(
θ
⃑
10
,
x
⃑
)
+
b
01
φ
h
(
θ
⃑
01
,
x
⃑
)
.
Firstly, we prove (42) as follows.
From (36) and (40), as well as Propositions 5 and 4, the right and left hand sides of (42) are written as, respectively,
(44)
S
h
R
(
ω
)
φ
h
(
θ
⃑
α
⃑
,
x
⃑
)
=
{
A
α
⃑
R
φ
h
(
θ
⃑
,
x
⃑
)
∀
x
⃑
∈
G
h
00
A
α
⃑
R
exp
⁡
[
-
i
π
(
α
1
+
α
2
)
]
φ
h
(
θ
⃑
,
x
⃑
)
∀
x
⃑
∈
G
h
11
exp
⁡
(
-
i
π
α
1
)
φ
h
(
θ
⃑
,
x
⃑
)
∀
x
⃑
∈
G
h
10
exp
⁡
(
-
i
π
α
2
)
φ
h
(
θ
⃑
,
x
⃑
)
∀
x
⃑
∈
G
h
01
,
∑
α
⃑
∈
Λ
a
α
⃑
φ
h
(
θ
⃑
α
⃑
,
x
⃑
)
=
{
(
a
00
+
a
11
+
a
10
+
a
01
)
φ
h
(
θ
⃑
,
x
⃑
)
∀
x
⃑
∈
G
h
00
(
a
00
+
a
11
-
a
10
-
a
01
)
φ
h
(
θ
⃑
,
x
⃑
)
∀
x
⃑
∈
G
h
11
(
a
00
-
a
11
-
a
10
+
a
01
)
φ
h
(
θ
⃑
,
x
⃑
)
∀
x
⃑
∈
G
h
10
(
a
00
-
a
11
+
a
10
-
a
01
)
φ
h
(
θ
⃑
,
x
⃑
)
∀
x
⃑
∈
G
h
01
,
where A
α
⃑
R
=
S
~
h
R
(
θ
⃑
α
⃑
,
ω
), α
⃑
=
(
α
1
,
α
2
)
∈
Λ. Hence, by using (42) and (44), linear equations with respect to the complex numbers a
00, a
11, a
10, and a
01 are obtained as
(45)
a
00
+
a
11
+
a
10
+
a
01
=
A
α
⃑
R
a
00
+
a
11
-
a
10
-
a
01
=
A
α
⃑
R
exp
⁡
[
-
i
π
(
α
1
+
α
2
)
]
a
00
-
a
11
-
a
10
+
a
01
=
exp
⁡
(
-
i
π
α
1
)
a
00
-
a
11
+
a
10
-
a
01
=
exp
⁡
(
-
i
π
α
2
)
.
In the same way, equations with respect to the complex numbers b
00, b
11, b
10, and b
01 are obtained as
(46)
b
00
+
b
11
+
b
10
+
b
01
=
1
b
00
+
b
11
-
b
10
-
b
01
=
exp
⁡
[
-
i
π
(
α
1
+
α
2
)
]
b
00
-
b
11
-
b
10
+
b
01
=
A
α
⃑
B
exp
⁡
(
-
i
π
α
1
)
b
00
-
b
11
+
b
10
-
b
01
=
A
α
⃑
B
exp
⁡
(
-
i
π
α
2
)
,
where A
α
⃑
B
=
S
~
h
B
(
θ
⃑
α
⃑
,
ω
), α
⃑
=
(
α
1
,
α
2
)
∈
Λ. From (10), (35), (42), and (43), solving (45) and (46), the Fourier representations of the iteration operators S
h
R
(
ω
) and S
h
B
(
ω
) are obtained as
(47)
S
^
h
⃑
R
(
θ
⃑
,
ω
)
=
1
2
(
A
00
R
+
1
A
11
R
-
1
0
0
A
00
R
-
1
A
11
R
+
1
0
0
0
0
A
10
R
+
1
A
01
R
-
1
0
0
A
10
R
-
1
A
01
R
+
1
)
S
^
h
B
(
θ
⃑
,
ω
)
=
1
2
(
A
00
B
+
1
-
A
11
B
+
1
0
0
-
A
00
B
-
1
A
11
B
+
1
0
0
0
0
A
10
B
+
1
-
A
01
B
+
1
0
0
-
A
10
B
+
1
A
01
B
+
1
)
.
Furthermore, from (47), the Fourier representation of the iteration operators S
h
R
B
(
ω
) is
(48)
S
^
h
R
B
(
θ
⃑
,
ω
)
=
S
^
h
B
(
θ
⃑
,
ω
)
S
^
h
R
(
θ
⃑
,
ω
)
=
1
2
(
A
00
B
+
1
-
A
11
B
+
1
0
0
-
A
00
B
-
1
A
11
B
+
1
0
0
0
0
A
10
B
+
1
-
A
01
B
+
1
0
0
-
A
10
B
+
1
A
01
B
+
1
)
·
1
2
(
A
00
R
+
1
A
11
R
-
1
0
0
A
00
R
-
1
A
11
R
+
1
0
0
0
0
A
10
R
+
1
A
01
R
-
1
0
0
A
10
R
-
1
A
01
R
+
1
)
,
where A
α
⃑
R
=
S
~
h
R
(
θ
⃑
α
⃑
,
ω
), A
α
⃑
B
=
S
~
h
B
(
θ
⃑
α
⃑
,
ω
), α
⃑
=
(
α
1
,
α
2
)
∈
Λ. Theorem 6 holds.From Theorems3 and 6, two ways to carry out smoothing analysis of the two-color relaxation are obtained.


## 3.1. Invariant Subspaces for Two-Color Relaxation

A new smoothing analysis process of the two-color relaxation is proposed with details. The proposed process is different with [11, 20–24]. A novel constitution among the Fourier modes with various frequencies is developed as a base of the smoothing analysis process. The analysis process is proved to be valuable.The gridG
h
=
{
x
⃑
=
(
k
1
h
1
,
k
2
h
2
)
∣
k
⃑
=
(
k
1
,
k
2
)
∈
Z
2
} is divided into two disjoint subsets G
h
0 and G
h
1; that is, G
h
=
G
h
0
∪
G
h
1 with
(16)
G
h
β
=
{
x
⃑
=
(
k
1
h
1
,
k
2
h
2
)
∣
k
1
+
k
2
=
β
mod
⁡
2
,
k
⃑
∈
Z
2
}
,
where β
=
0,1. According to (16), the subspace of the 2h-harmonics (9) is redefined as
(17)
F
2
h
2
(
θ
⃑
)
:
=
span
⁡
{
φ
h
(
θ
⃑
0
,
x
⃑
)
,
φ
h
(
θ
⃑
1
,
x
⃑
)
}
with θ
⃑
=
(
θ
1
,
θ
2
)
∈
Θ
low
=
(
-
π
/
2
,
π
/
2
]
2, where θ
⃑
α
=
(
θ
⃑
+
(
α
,
α
)
π
)
mod
⁡
2
π, α
=
0,1. Thus, the constitutions among the various Fourier modes defined by (16) and (17) are presented as follows.Proposition 1.
For∀
x
⃑
∈
G
h, ∀
(
k
1
,
k
2
)
∈
Z
2, and ∀
α
∈
{
0,1
}, if θ
⃑
∈
Θ
low, then the following formulation holds:
(18)
φ
h
(
θ
⃑
α
,
x
⃑
)
=
exp
⁡
[
i
π
α
(
k
1
+
k
2
)
]
φ
h
(
θ
⃑
,
x
⃑
)
.Proof.
From (4), for ∀
x
⃑
∈
G
h, it holds for φ
h
(
θ
⃑
α
,
x
⃑
)
=
exp
⁡
(
i
θ
⃑
α
k
⃑
). From (17), ∃
n
⃑
=
(
n
1
,
n
2
)
∈
Z
2 is subjected to θ
⃑
α
=
(
θ
1
+
α
π
,
θ
2
+
α
π
)
+
2
π
n
⃑. Then
(19)
θ
⃑
α
k
⃑
=
θ
⃑
k
⃑
+
π
α
(
k
1
+
k
2
)
+
2
π
n
⃑
k
⃑
holds. Thus,
(20)
φ
h
(
θ
⃑
α
,
x
⃑
)
=
exp
⁡
⁡
(
i
θ
⃑
α
k
⃑
)
=
exp
⁡
⁡
[
i
π
α
(
k
1
+
k
2
)
]
exp
⁡
⁡
(
i
θ
⃑
k
⃑
)
=
exp
⁡
[
i
π
α
(
k
1
+
k
2
)
]
φ
h
(
θ
⃑
,
x
⃑
)
.
Proposition 1 follows.Proposition 2.
For∀
α, β
∈
{
0,1
}, and ∀
x
⃑
∈
G
h
β, if θ
⃑
∈
Θ
l
o
w, then the following formulation holds:
(21)
φ
h
(
θ
⃑
α
,
x
⃑
)
=
exp
⁡
(
i
π
α
β
)
φ
h
(
θ
⃑
,
x
⃑
)
.Proof.
By Proposition1 and G
h
β
⊆
G
h, for ∀
x
⃑
∈
G
h
β, then
(22)
φ
h
(
θ
⃑
α
,
x
⃑
)
=
exp
⁡
[
i
π
α
(
k
1
+
k
2
)
]
φ
h
(
θ
⃑
,
x
⃑
)
,
where (
k
1
,
k
2
)
∈
Z
2. For x
⃑
∈
G
h
β, from (16), ∃
p
∈
Z is subjected to k
1
+
k
2
=
β
+
2
p; hence,
(23)
φ
h
(
θ
⃑
α
,
x
⃑
)
=
exp
⁡
[
i
π
α
(
β
+
2
p
)
]
φ
h
(
θ
⃑
,
x
⃑
)
=
exp
⁡
(
i
π
α
β
)
φ
h
(
θ
⃑
,
x
⃑
)
.
Proposition 2 holds.Subsequently, the smoothing analysis process of the two-color relaxation on the subspace of the2
h-harmonics (17) is conducted. By (15) and (16) and without loss of generality, let G
h
0 and G
h
1 correspond to G
h
R and G
h
B, respectively; thus (15) is rewritten as
(24)
S
h
01
(
ω
)
=
S
h
1
(
ω
)
S
h
0
(
ω
)
.Theorem 3.
The iteration operatorS
h
01
(
ω
) for the two-color relaxation leaves the subspace of the 2h-harmonics (17) to be invariant.Proof.
From the process of the two-color relaxation, the operatorS
h
β
(
ω
) of grid (16) is
(25)
S
h
β
(
ω
)
φ
h
(
θ
⃑
,
x
⃑
)
=
{
S
~
h
β
(
θ
⃑
,
ω
)
φ
h
(
θ
⃑
,
x
⃑
)
∀
x
⃑
∈
G
h
β
φ
h
(
θ
⃑
,
x
⃑
)
∀
x
⃑
∉
G
h
β
,
where S
~
h
β
(
θ
⃑
,
ω
) is Fourier symbol of S
h
β
(
ω
) on grid (16) with β
=
0,1. From (10) and (25), now it is proved that the subspace of the 2h-harmonics (17) is invariant for the iteration operator (24). Because of (17), we need to find out two complex numbers a
0 and a
1 with ∀
α, β
∈
{
0,1
} and make them subjected to
(26)
S
h
β
(
ω
)
φ
h
(
θ
⃑
α
,
x
⃑
)
=
a
0
φ
h
(
θ
⃑
0
,
x
⃑
)
+
a
1
φ
h
(
θ
⃑
1
,
x
⃑
)
.
From (25), the right hand side of (26) is written as
(27)
S
h
β
(
ω
)
φ
h
(
θ
⃑
α
,
x
⃑
)
=
{
S
~
h
β
(
θ
⃑
α
,
ω
)
φ
h
(
θ
⃑
α
,
x
⃑
)
∀
x
⃑
∈
G
h
β
φ
h
(
θ
⃑
α
,
x
⃑
)
∀
x
⃑
∉
G
h
β
.
By Propositions 1 and 2, the right hand side of (27) is expressed as
(28)
S
h
β
(
ω
)
φ
h
(
θ
⃑
α
,
x
⃑
)
=
{
S
~
h
β
(
θ
⃑
α
,
ω
)
exp
⁡
⁡
(
i
α
β
π
)
φ
h
(
θ
⃑
,
x
⃑
)
∀
x
⃑
∈
G
h
β
exp
⁡
⁡
[
i
α
(
1
-
β
)
π
]
φ
h
(
θ
⃑
,
x
⃑
)
∀
x
⃑
∉
G
h
β
.
Taking A
α
β
=
S
~
h
β
(
θ
⃑
α
,
ω
), (28) is written as
(29)
S
h
β
(
ω
)
φ
h
(
θ
⃑
α
,
x
⃑
)
=
{
A
α
β
exp
⁡
⁡
(
i
α
β
π
)
φ
h
(
θ
⃑
,
x
⃑
)
∀
x
⃑
∈
G
h
β
exp
⁡
⁡
[
i
α
(
1
-
β
)
π
]
φ
h
(
θ
⃑
,
x
⃑
)
∀
x
⃑
∉
G
h
β
.
From Propositions 1 and 2, the left hand side of (26) is written as
(30)
a
0
φ
h
(
θ
⃑
0
,
x
⃑
)
+
a
1
φ
h
(
θ
⃑
1
,
x
⃑
)
=
{
(
a
0
+
a
1
exp
⁡
(
i
β
π
)
)
φ
h
(
θ
⃑
,
x
⃑
)
x
⃑
∈
G
h
β
(
a
0
+
a
1
exp
⁡
[
i
(
1
-
β
)
π
]
)
φ
h
(
θ
⃑
,
x
⃑
)
x
⃑
∉
G
h
β
.
Hence, from (26), (29), and (30), a set of two linear equations on a
0 and a
1 is given as
(31)
a
0
+
a
1
exp
⁡
⁡
(
i
β
π
)
=
A
α
β
exp
⁡
⁡
(
i
α
β
π
)
a
0
+
a
1
exp
⁡
[
i
(
1
-
β
)
π
]
=
exp
⁡
[
i
α
(
1
-
β
)
π
]
,
where α, β
∈
{
0,1
}. Therefore, from (31), it is concluded that there exist two complex numbers a
0 and a
1 that are subjected to (26). From (10), (17), and (26), solving linear equation (31), the Fourier representations of the iteration operators S
h
0
(
ω
) and S
h
1
(
ω
) are obtained as
(32)
S
^
h
0
(
θ
⃑
,
ω
)
=
1
2
(
A
0
0
+
1
A
1
0
-
1
A
0
0
-
1
A
1
0
+
1
)
,
S
^
h
1
(
θ
⃑
,
ω
)
=
1
2
(
A
0
1
+
1
-
A
1
1
+
1
-
A
0
1
+
1
A
1
1
+
1
)
,
where A
α
β
=
S
~
h
β
(
θ
⃑
α
,
ω
) and α, β
∈
{
0,1
}. Furthermore, from (32), the Fourier representations of the two-color relaxation S
h
01
(
ω
) are
(33)
S
^
h
01
(
θ
⃑
,
ω
)
=
S
^
h
1
(
θ
⃑
,
ω
)
S
^
h
0
(
θ
⃑
,
ω
)
=
1
2
(
A
0
1
+
1
-
A
1
1
+
1
-
A
0
1
+
1
A
1
1
+
1
)
·
1
2
(
A
0
0
+
1
A
1
0
-
1
A
0
0
-
1
A
1
0
+
1
)
.
From (10), Theorem 3 holds.


## 3.2. Invariant Subspaces on Four Fourier Modes for Two-Color Relaxation

We need to develop a Fourier representation of the two-color relaxation in the subspace of the 2h-harmonics with four Fourier modes. By following (9), for 2D system, another subspace of the 2h-harmonics is given as
(34)
F
2
h
*
(
θ
⃑
)
:
=
span
⁡
{
φ
h
(
θ
⃑
α
⃑
,
x
⃑
)
∣
α
⃑
=
(
α
1
,
α
2
)
,
α
m
∈
{
0,1
}
,
m
=
1,2
φ
h
(
θ
⃑
α
⃑
,
x
⃑
)
}
with θ
⃑
=
(
θ
1
,
θ
2
)
=
θ
⃑
(
0,0
)
∈
Θ
low
=
(
-
π
/
2
,
π
/
2
]
2, θ
⃑
α
⃑
=
θ
⃑
(
0,0
)
-
(
α
1
sign
⁡
(
θ
1
)
,
α
2
sign
⁡
(
θ
2
)
)
π.For the sake of convenient analysis, takingθ
⃑
α
⃑
=
θ
⃑
(
α
1
,
α
2
)
=
θ
⃑
α
1
α
2, for example, θ
⃑
(
0,0
)
=
θ
⃑
00, then F
2
h
*
(
θ
⃑
) is defined as
(35)
F
2
h
*
(
θ
⃑
)
:
=
span
⁡
{
φ
h
(
θ
⃑
00
,
x
⃑
)
,
φ
h
(
θ
⃑
11
,
x
⃑
)
,
φ
h
(
θ
⃑
10
,
x
⃑
)
,
φ
h
(
θ
⃑
01
,
x
⃑
)
}
.
Meanwhile, the grid G
h is divided into four subsets [11] as
(36)
G
h
=
G
h
00
∪
G
h
11
∪
G
h
10
∪
G
h
01
,
where G
h
η
⃑
=
{
x
⃑
=
(
k
1
h
1
,
k
2
h
2
)
∣
k
m
=
η
m
mod
⁡
2
,
m
=
1,2
} and η
⃑
=
(
η
1
,
η
2
)
∈
Λ
=
{
00,11,10,01
}. The red and black grid points corresponding with G
h are thus obtained as
(37)
G
h
R
=
G
h
00
∪
G
h
11
,
G
h
B
=
G
h
10
∪
G
h
01
.
Therefore, a constitutive relationship among the various Fourier 2h-harmonics is constructed.Proposition 4.
For∀
x
⃑
∈
G
h, ∀
k
⃑
=
(
k
1
,
k
2
)
∈
Z
2, and ∀
α
⃑
∈
Λ, if θ
⃑
∈
Θ
l
o
w, the following equation is yielded as
(38)
φ
h
(
θ
⃑
α
⃑
,
x
⃑
)
=
exp
⁡
(
-
i
π
α
⃑
k
⃑
)
φ
h
(
θ
⃑
,
x
⃑
)
.Proposition 5.
For∀
x
⃑
∈
G
h
β
⃑, ∀
k
⃑
=
(
k
1
,
k
2
)
∈
Z
2, and ∀
α
⃑
,
β
⃑
∈
Λ, if θ
⃑
∈
Θ
l
o
w, the following equation is yielded as
(39)
φ
h
(
θ
⃑
α
⃑
,
x
⃑
)
=
exp
⁡
⁡
(
-
i
π
α
⃑
β
⃑
)
φ
h
(
θ
⃑
,
x
⃑
)
.
The proof of Propositions 5 and 4 is similar to Propositions 2 and 1.Subsequently, a smoothing analysis process of the two-color relaxation on the subspace of the2
h-harmonics (35) is obtained.Theorem 6.
The iteration operator (15) for the two-color relaxation leaves the subspace of the 2h-harmonics (35) to be invariant 0.Proof.
Similar to the proof of Theorem3, from process of the two-color relaxation and (15), operators S
h
R
(
ω
) and S
h
B
(
ω
) of the grid (37) are
(40)
S
h
R
(
ω
)
φ
h
(
θ
⃑
α
⃑
,
x
⃑
)
=
{
S
~
h
R
(
θ
⃑
α
⃑
,
ω
)
φ
h
(
θ
⃑
α
⃑
,
x
⃑
)
∀
x
⃑
∈
G
h
R
φ
h
(
θ
⃑
α
⃑
,
x
⃑
)
∀
x
⃑
∉
G
h
R
(41)
S
h
B
(
ω
)
φ
h
(
θ
⃑
α
⃑
,
x
⃑
)
=
{
S
~
h
B
(
θ
⃑
α
⃑
,
ω
)
φ
h
(
θ
⃑
α
⃑
,
x
⃑
)
∀
x
⃑
∈
G
h
B
φ
h
(
θ
⃑
α
⃑
,
x
⃑
)
∀
x
⃑
∉
G
h
B
,
where S
~
h
R
(
θ
⃑
α
⃑
,
ω
) and S
~
h
B
(
θ
⃑
α
⃑
,
ω
) are Fourier symbols of S
h
R
(
ω
) and S
h
R
(
ω
) with φ
h
(
θ
⃑
α
⃑
,
x
⃑
) on the corresponding grids (37), respectively, and α
⃑
∈
Λ. From (15), in order to prove S
h
R
B
(
ω
)
:
F
2
h
*
(
θ
⃑
)
→
F
2
h
*
(
θ
⃑
) with θ
⃑
∈
Θ
low, we need to find out four complex numbers a
00, a
11, a
10, and a
01 subjected to
(42)
S
h
R
(
ω
)
φ
h
(
θ
⃑
α
⃑
,
x
⃑
)
=
a
00
φ
h
(
θ
⃑
00
,
x
⃑
)
+
a
11
φ
h
(
θ
⃑
11
,
x
⃑
)
+
a
10
φ
h
(
θ
⃑
10
,
x
⃑
)
+
a
01
φ
h
(
θ
⃑
01
,
x
⃑
)
.
Meanwhile, we also need to find other four complex numbers b
00, b
11, b
10, and b
01 and make them subjected to
(43)
S
h
B
(
ω
)
φ
h
(
θ
⃑
α
⃑
,
x
⃑
)
=
b
00
φ
h
(
θ
⃑
00
,
x
⃑
)
+
b
11
φ
h
(
θ
⃑
11
,
x
⃑
)
+
b
10
φ
h
(
θ
⃑
10
,
x
⃑
)
+
b
01
φ
h
(
θ
⃑
01
,
x
⃑
)
.
Firstly, we prove (42) as follows.
From (36) and (40), as well as Propositions 5 and 4, the right and left hand sides of (42) are written as, respectively,
(44)
S
h
R
(
ω
)
φ
h
(
θ
⃑
α
⃑
,
x
⃑
)
=
{
A
α
⃑
R
φ
h
(
θ
⃑
,
x
⃑
)
∀
x
⃑
∈
G
h
00
A
α
⃑
R
exp
⁡
[
-
i
π
(
α
1
+
α
2
)
]
φ
h
(
θ
⃑
,
x
⃑
)
∀
x
⃑
∈
G
h
11
exp
⁡
(
-
i
π
α
1
)
φ
h
(
θ
⃑
,
x
⃑
)
∀
x
⃑
∈
G
h
10
exp
⁡
(
-
i
π
α
2
)
φ
h
(
θ
⃑
,
x
⃑
)
∀
x
⃑
∈
G
h
01
,
∑
α
⃑
∈
Λ
a
α
⃑
φ
h
(
θ
⃑
α
⃑
,
x
⃑
)
=
{
(
a
00
+
a
11
+
a
10
+
a
01
)
φ
h
(
θ
⃑
,
x
⃑
)
∀
x
⃑
∈
G
h
00
(
a
00
+
a
11
-
a
10
-
a
01
)
φ
h
(
θ
⃑
,
x
⃑
)
∀
x
⃑
∈
G
h
11
(
a
00
-
a
11
-
a
10
+
a
01
)
φ
h
(
θ
⃑
,
x
⃑
)
∀
x
⃑
∈
G
h
10
(
a
00
-
a
11
+
a
10
-
a
01
)
φ
h
(
θ
⃑
,
x
⃑
)
∀
x
⃑
∈
G
h
01
,
where A
α
⃑
R
=
S
~
h
R
(
θ
⃑
α
⃑
,
ω
), α
⃑
=
(
α
1
,
α
2
)
∈
Λ. Hence, by using (42) and (44), linear equations with respect to the complex numbers a
00, a
11, a
10, and a
01 are obtained as
(45)
a
00
+
a
11
+
a
10
+
a
01
=
A
α
⃑
R
a
00
+
a
11
-
a
10
-
a
01
=
A
α
⃑
R
exp
⁡
[
-
i
π
(
α
1
+
α
2
)
]
a
00
-
a
11
-
a
10
+
a
01
=
exp
⁡
(
-
i
π
α
1
)
a
00
-
a
11
+
a
10
-
a
01
=
exp
⁡
(
-
i
π
α
2
)
.
In the same way, equations with respect to the complex numbers b
00, b
11, b
10, and b
01 are obtained as
(46)
b
00
+
b
11
+
b
10
+
b
01
=
1
b
00
+
b
11
-
b
10
-
b
01
=
exp
⁡
[
-
i
π
(
α
1
+
α
2
)
]
b
00
-
b
11
-
b
10
+
b
01
=
A
α
⃑
B
exp
⁡
(
-
i
π
α
1
)
b
00
-
b
11
+
b
10
-
b
01
=
A
α
⃑
B
exp
⁡
(
-
i
π
α
2
)
,
where A
α
⃑
B
=
S
~
h
B
(
θ
⃑
α
⃑
,
ω
), α
⃑
=
(
α
1
,
α
2
)
∈
Λ. From (10), (35), (42), and (43), solving (45) and (46), the Fourier representations of the iteration operators S
h
R
(
ω
) and S
h
B
(
ω
) are obtained as
(47)
S
^
h
⃑
R
(
θ
⃑
,
ω
)
=
1
2
(
A
00
R
+
1
A
11
R
-
1
0
0
A
00
R
-
1
A
11
R
+
1
0
0
0
0
A
10
R
+
1
A
01
R
-
1
0
0
A
10
R
-
1
A
01
R
+
1
)
S
^
h
B
(
θ
⃑
,
ω
)
=
1
2
(
A
00
B
+
1
-
A
11
B
+
1
0
0
-
A
00
B
-
1
A
11
B
+
1
0
0
0
0
A
10
B
+
1
-
A
01
B
+
1
0
0
-
A
10
B
+
1
A
01
B
+
1
)
.
Furthermore, from (47), the Fourier representation of the iteration operators S
h
R
B
(
ω
) is
(48)
S
^
h
R
B
(
θ
⃑
,
ω
)
=
S
^
h
B
(
θ
⃑
,
ω
)
S
^
h
R
(
θ
⃑
,
ω
)
=
1
2
(
A
00
B
+
1
-
A
11
B
+
1
0
0
-
A
00
B
-
1
A
11
B
+
1
0
0
0
0
A
10
B
+
1
-
A
01
B
+
1
0
0
-
A
10
B
+
1
A
01
B
+
1
)
·
1
2
(
A
00
R
+
1
A
11
R
-
1
0
0
A
00
R
-
1
A
11
R
+
1
0
0
0
0
A
10
R
+
1
A
01
R
-
1
0
0
A
10
R
-
1
A
01
R
+
1
)
,
where A
α
⃑
R
=
S
~
h
R
(
θ
⃑
α
⃑
,
ω
), A
α
⃑
B
=
S
~
h
B
(
θ
⃑
α
⃑
,
ω
), α
⃑
=
(
α
1
,
α
2
)
∈
Λ. Theorem 6 holds.From Theorems3 and 6, two ways to carry out smoothing analysis of the two-color relaxation are obtained.


## 4. Two-Color Jacobi Relaxation for 2D Poisson Equation

### 4.1. Poisson Equation and Optimal Smoothing Parameter

2D Poisson equation to be considered is stated as(49)
-
Δ
u
(
x
1
,
x
2
)
=
f
(
x
1
,
x
2
)
.
For using uniform grids of mesh size h to solve this equation, a central discretization stencil is introduced as
(50)
L
h
=
-
Δ
h
=
1
h
2
[
-
1
-
1
4
-
1
-
1
]
h
.
From (3)–(6), the Fourier symbol of (50) is
(51)
L
~
h
(
θ
⃑
)
=
1
h
2
(
4
-
2
cos
⁡
θ
1
-
2
cos
⁡
θ
2
)
.
From [1], the damped Jacobi relaxation S
h
JAC is defined as
(52)
S
h
JAC
(
ω
)
=
I
h
-
ω
D
h
-
1
L
h
,
where I
h
=
[
1
]
h is the identity operator, ω is the smoothing parameter, and D
h
=
(
1
/
h
2
)
[
4
]
h is the diagonal part of the discrete operator L
h. Thus, the Fourier symbol of (52) is given as
(53)
S
~
h
JAC
(
θ
⃑
,
ω
)
=
1
-
ω
(
sin
2
θ
1
2
+
sin
2
θ
2
2
)
.For the operatorsS
h
(
ω
) and Q
h
H in (14) with a relaxation parameter ω and according to the optimal one-stage relaxation [11], smoothing parameter and a related smoothing factor are given by
(54)
ω
opt
=
2
2
-
S
max
⁡
-
S
min
⁡
,
ρ
opt
=
S
max
⁡
-
S
min
⁡
2
-
S
max
⁡
-
S
min
⁡
,
where S
max
⁡ and S
min
⁡ are the maximum and minimum eigenvalues of the matrix Q
^
h
H
S
^
h
(
θ
⃑
,
1
) for θ
⃑
∈
Θ
low
=
(
-
π
/
2
,
π
/
2
]
2 and S
^
h
(
θ
⃑
,
1
) is the Fourier representation of S
h
(
ω
) with ω
=
1.


### 4.2. Two-Color Relaxation on (17)

According to (32), (33), and (53), for point Jacobi relaxation, A
α
β in (17) is expressed as
(55)
A
α
0
=
A
α
1
=
S
~
h
0
(
θ
⃑
α
,
ω
)
=
S
~
h
1
(
θ
⃑
α
,
ω
)
=
S
~
h
JAC
(
θ
⃑
α
,
ω
)
=
1
-
ω
(
sin
2
θ
1
α
2
+
sin
2
θ
2
α
2
)
which denotes that both red and black points are swept by the Jacobi point relaxation method, where α, β
=
0, 1 and ω is the smoothing parameter. Further, when ω
=
1, (55) is rewritten as
(56)
A
α
0
=
A
α
1
=
S
~
h
JAC
(
θ
⃑
α
,
1
)
=
1
-
(
sin
2
θ
1
α
2
+
sin
2
θ
2
α
2
)
,
where α
=
0, 1. For simplification, let
(57)
s
1
=
si
n
2
θ
1
0
2
=
si
n
2
θ
1
2
,
s
2
=
si
n
2
θ
2
0
2
=
si
n
2
θ
2
2
.
By substituting (56) and (57) into (33), (56) is given as
(58)
A
0
0
=
A
0
1
=
1
-
(
s
1
+
s
2
)
,
A
1
0
=
A
1
1
=
s
1
+
s
2
-
1
,
(59)
S
^
h
01
(
θ
⃑
,
1
)
=
(
1
-
1
2
(
s
1
+
s
2
)
1
-
1
2
(
s
1
+
s
2
)
1
2
(
s
1
+
s
2
)
1
2
(
s
1
+
s
2
)
)
·
(
1
-
1
2
(
s
1
+
s
2
)
1
2
(
s
1
+
s
2
)
-
1
-
1
2
(
s
1
+
s
2
)
1
2
(
s
1
+
s
2
)
)
.
Further, by using (13) and (17), the Fourier representation of Q
h
H is given as Q
^
h
H
=
diag
⁡
(
0,1
). From (59), the product of Q
^
h
H and (59) is
(60)
Q
^
h
H
S
^
h
01
(
θ
⃑
,
1
)
=
(
0
0
1
2
(
s
1
+
s
2
)
(
1
-
s
1
-
s
2
)
1
2
(
s
1
+
s
2
)
(
s
1
+
s
2
-
1
)
)
.
Therefore, a unique nonzero eigenvalue of the matrix Q
^
h
H
S
^
h
01
(
θ
⃑
,
1
) is yielded as
(61)
λ
(
s
1
,
s
2
)
=
1
2
(
s
1
+
s
2
)
(
s
1
+
s
2
-
1
)
.
Because of θ
⃑
∈
Θ
low
=
(
-
π
/
2
,
π
/
2
]
2, thus, from (57), we know (
s
1
,
s
2
)
∈
[
0,1
/
2
]
2. So, by using (54), the optimal smoothing parameters for the two-color relaxation are given as
(62)
S
max
⁡
=
max
⁡
(
s
1
,
s
2
)
∈
[
0,1
/
2
]
2
λ
(
s
1
,
s
2
)
|
θ
⃑
=
(
π
/
2
,
π
/
2
)
=
0
,
S
min
⁡
=
min
⁡
(
s
1
,
s
2
)
∈
[
0,1
/
2
]
2
λ
(
s
1
,
s
2
)
|
θ
⃑
=
(
0
,
π
/
2
)
=
-
1
8
,
(63)
ω
opt
=
2
2
-
S
max
⁡
-
S
min
⁡
=
16
17
,
ρ
opt
=
S
max
⁡
-
S
min
⁡
2
-
S
max
⁡
-
S
min
⁡
=
1
17
.


### 4.3. Two-Color Jacobi Relaxation on (35)

By using (48) and (53), for point Jacobi relaxation, A
α
⃑
R and A
α
⃑
B for (35) are expressed as
(64)
A
α
⃑
R
=
A
α
⃑
B
=
S
~
h
R
(
θ
⃑
α
⃑
,
ω
)
=
S
~
h
B
(
θ
⃑
α
⃑
,
ω
)
=
S
~
h
JAC
(
θ
⃑
α
⃑
,
ω
)
=
1
-
ω
(
sin
2
θ
1
α
1
2
+
sin
2
θ
2
α
2
2
)
which denotes that both red and black points are swept by the Jacobi point relaxation method, where α
⃑
=
(
α
1
,
α
2
)
∈
Λ. Further, substituting (57) into (64), when ω
=
1, (64) is written as
(65)
A
00
R
=
A
00
B
=
1
-
(
s
1
+
s
2
)
A
11
R
=
A
11
B
=
s
1
+
s
2
-
1
A
10
R
=
A
10
B
=
s
1
-
s
2
A
01
R
=
A
01
B
=
-
(
s
1
-
s
2
)
.
Substituting (65) into (48), the Fourier representation of S
h
R
B
(
ω
) with ω
=
1 is expressed as
(66)
S
^
h
R
B
(
θ
⃑
,
1
)
=
diag
⁡
(
S
^
11
,
S
^
22
)
,
where
(67)
S
^
11
=
(


1
2
(
s
1
+
s
2
-
1
)
(
s
1
+
s
2
-
2
)
-
1
2
(
s
1
+
s
2
-
1
)
(
s
1
+
s
2
-
2
)
-
1
2
(
s
1
+
s
2
-
1
)
(
s
1
+
s
2
)
1
2
(
s
1
+
s
2
-
1
)
(
s
1
+
s
2
)


)

,
S
^
22
=
(
1
2
(
s
1
+
s
2
-
1
)
(
s
1
+
s
2
)
-
1
2
(
s
1
-
s
2
+
1
)
(
s
1
-
s
2
)
1
2
(
s
2
-
s
1
+
1
)
(
s
1
-
s
2
)
-
1
2
(
s
2
-
s
1
+
1
)
(
s
1
-
s
2
)
)
.
From (13) and (35), the Fourier representation of operator Q
h
H is given as
(68)
Q
^
h
H
=
diag
⁡
(
Q
^
11
,
Q
^
22
)
,
where Q
^
11
=
diag
⁡
(
0,1
), Q
^
22
=
diag
⁡
(
1,1
). Therefore, the product of (66) and (68) is obtained as
(69)
Q
^
h
H
S
^
h
R
B
(
θ
⃑
,
1
)
=
diag
⁡
(
Q
^
11
S
^
11
,
Q
^
22
S
^
22
)
,
in which the diagonal blocks are expressed as
(70)
Q
^
11
S
^
11
=
(
0
0
-
(
s
1
+
s
2
)
(
s
1
+
s
2
-
1
)
2
(
s
1
+
s
2
)
(
s
1
+
s
2
-
1
)
2
)
,
(71)
Q
^
22
S
^
22
=
(
(
s
1
-
s
2
)
(
s
1
-
s
2
+
1
)
2
-
(
s
1
-
s
2
)
(
s
1
-
s
2
+
1
)
2
(
s
1
-
s
2
)
(
s
2
-
s
1
+
1
)
2
-
(
s
1
-
s
2
)
(
s
2
-
s
1
+
1
)
2
)
.
The eigenvalues of the matrix (69) are obtained as
(72)
λ
1
=
0
,
λ
2
=
(
s
1
-
s
2
)
2
,
λ
3
=
0
,
λ
4
=
(
s
1
+
s
2
)
(
s
1
+
s
2
-
1
)
2
.
When θ
⃑
∈
Θ
low, the maximum and minimum eigenvalues of the matrix Q
^
h
H
S
^
h
R
B
(
θ
⃑
,
1
) are as follows:
(73)
λ
max
⁡
(
Q
^
h
H
S
^
h
R
B
(
θ
⃑
,
1
)
)
=
max
⁡
(
s
1
,
s
2
)
∈
[
0,1
/
2
]
2
{
λ
1
,
λ
2
,
λ
3
,
λ
4
}
=
max
⁡
(
s
1
,
s
2
)
∈
[
0,1
/
2
]
2
λ
2
=
1
4
,
(74)
λ
min
⁡
(
Q
^
h
H
S
^
h
R
B
(
θ
⃑
,
1
)
)
=
min
⁡
(
s
1
,
s
2
)
∈
[
0,1
/
2
]
2
{
λ
1
,
λ
2
,
λ
3
,
λ
4
}
=
min
⁡
(
s
1
,
s
2
)
∈
[
0,1
/
2
]
2
λ
4
=
-
1
8
.
Therefore, by using (54), the values of the optimal smoothing parameters for the Poisson equation are obtained as
(75)
S
max
⁡
=
λ
max
⁡
(
Q
^
h
H
S
^
h
R
B
(
θ
⃑
,
1
)
)
|
θ
⃑
=
(
0
,
π
/
2
)
=
1
4
,
S
min
⁡
=
λ
min
⁡
(
Q
^
h
H
S
^
h
R
B
(
θ
⃑
,
1
)
)
|
θ
⃑
=
(
π
/
2,0
)
=
-
1
8
,
(76)
ω
opt
=
2
2
-
S
max
⁡
-
S
min
⁡
=
16
15
,
ρ
opt
=
S
max
⁡
-
S
min
⁡
2
-
S
max
⁡
-
S
min
⁡
=
1
5
.


## 4.1. Poisson Equation and Optimal Smoothing Parameter

2D Poisson equation to be considered is stated as(49)
-
Δ
u
(
x
1
,
x
2
)
=
f
(
x
1
,
x
2
)
.
For using uniform grids of mesh size h to solve this equation, a central discretization stencil is introduced as
(50)
L
h
=
-
Δ
h
=
1
h
2
[
-
1
-
1
4
-
1
-
1
]
h
.
From (3)–(6), the Fourier symbol of (50) is
(51)
L
~
h
(
θ
⃑
)
=
1
h
2
(
4
-
2
cos
⁡
θ
1
-
2
cos
⁡
θ
2
)
.
From [1], the damped Jacobi relaxation S
h
JAC is defined as
(52)
S
h
JAC
(
ω
)
=
I
h
-
ω
D
h
-
1
L
h
,
where I
h
=
[
1
]
h is the identity operator, ω is the smoothing parameter, and D
h
=
(
1
/
h
2
)
[
4
]
h is the diagonal part of the discrete operator L
h. Thus, the Fourier symbol of (52) is given as
(53)
S
~
h
JAC
(
θ
⃑
,
ω
)
=
1
-
ω
(
sin
2
θ
1
2
+
sin
2
θ
2
2
)
.For the operatorsS
h
(
ω
) and Q
h
H in (14) with a relaxation parameter ω and according to the optimal one-stage relaxation [11], smoothing parameter and a related smoothing factor are given by
(54)
ω
opt
=
2
2
-
S
max
⁡
-
S
min
⁡
,
ρ
opt
=
S
max
⁡
-
S
min
⁡
2
-
S
max
⁡
-
S
min
⁡
,
where S
max
⁡ and S
min
⁡ are the maximum and minimum eigenvalues of the matrix Q
^
h
H
S
^
h
(
θ
⃑
,
1
) for θ
⃑
∈
Θ
low
=
(
-
π
/
2
,
π
/
2
]
2 and S
^
h
(
θ
⃑
,
1
) is the Fourier representation of S
h
(
ω
) with ω
=
1.


## 4.2. Two-Color Relaxation on (17)

According to (32), (33), and (53), for point Jacobi relaxation, A
α
β in (17) is expressed as
(55)
A
α
0
=
A
α
1
=
S
~
h
0
(
θ
⃑
α
,
ω
)
=
S
~
h
1
(
θ
⃑
α
,
ω
)
=
S
~
h
JAC
(
θ
⃑
α
,
ω
)
=
1
-
ω
(
sin
2
θ
1
α
2
+
sin
2
θ
2
α
2
)
which denotes that both red and black points are swept by the Jacobi point relaxation method, where α, β
=
0, 1 and ω is the smoothing parameter. Further, when ω
=
1, (55) is rewritten as
(56)
A
α
0
=
A
α
1
=
S
~
h
JAC
(
θ
⃑
α
,
1
)
=
1
-
(
sin
2
θ
1
α
2
+
sin
2
θ
2
α
2
)
,
where α
=
0, 1. For simplification, let
(57)
s
1
=
si
n
2
θ
1
0
2
=
si
n
2
θ
1
2
,
s
2
=
si
n
2
θ
2
0
2
=
si
n
2
θ
2
2
.
By substituting (56) and (57) into (33), (56) is given as
(58)
A
0
0
=
A
0
1
=
1
-
(
s
1
+
s
2
)
,
A
1
0
=
A
1
1
=
s
1
+
s
2
-
1
,
(59)
S
^
h
01
(
θ
⃑
,
1
)
=
(
1
-
1
2
(
s
1
+
s
2
)
1
-
1
2
(
s
1
+
s
2
)
1
2
(
s
1
+
s
2
)
1
2
(
s
1
+
s
2
)
)
·
(
1
-
1
2
(
s
1
+
s
2
)
1
2
(
s
1
+
s
2
)
-
1
-
1
2
(
s
1
+
s
2
)
1
2
(
s
1
+
s
2
)
)
.
Further, by using (13) and (17), the Fourier representation of Q
h
H is given as Q
^
h
H
=
diag
⁡
(
0,1
). From (59), the product of Q
^
h
H and (59) is
(60)
Q
^
h
H
S
^
h
01
(
θ
⃑
,
1
)
=
(
0
0
1
2
(
s
1
+
s
2
)
(
1
-
s
1
-
s
2
)
1
2
(
s
1
+
s
2
)
(
s
1
+
s
2
-
1
)
)
.
Therefore, a unique nonzero eigenvalue of the matrix Q
^
h
H
S
^
h
01
(
θ
⃑
,
1
) is yielded as
(61)
λ
(
s
1
,
s
2
)
=
1
2
(
s
1
+
s
2
)
(
s
1
+
s
2
-
1
)
.
Because of θ
⃑
∈
Θ
low
=
(
-
π
/
2
,
π
/
2
]
2, thus, from (57), we know (
s
1
,
s
2
)
∈
[
0,1
/
2
]
2. So, by using (54), the optimal smoothing parameters for the two-color relaxation are given as
(62)
S
max
⁡
=
max
⁡
(
s
1
,
s
2
)
∈
[
0,1
/
2
]
2
λ
(
s
1
,
s
2
)
|
θ
⃑
=
(
π
/
2
,
π
/
2
)
=
0
,
S
min
⁡
=
min
⁡
(
s
1
,
s
2
)
∈
[
0,1
/
2
]
2
λ
(
s
1
,
s
2
)
|
θ
⃑
=
(
0
,
π
/
2
)
=
-
1
8
,
(63)
ω
opt
=
2
2
-
S
max
⁡
-
S
min
⁡
=
16
17
,
ρ
opt
=
S
max
⁡
-
S
min
⁡
2
-
S
max
⁡
-
S
min
⁡
=
1
17
.


## 4.3. Two-Color Jacobi Relaxation on (35)

By using (48) and (53), for point Jacobi relaxation, A
α
⃑
R and A
α
⃑
B for (35) are expressed as
(64)
A
α
⃑
R
=
A
α
⃑
B
=
S
~
h
R
(
θ
⃑
α
⃑
,
ω
)
=
S
~
h
B
(
θ
⃑
α
⃑
,
ω
)
=
S
~
h
JAC
(
θ
⃑
α
⃑
,
ω
)
=
1
-
ω
(
sin
2
θ
1
α
1
2
+
sin
2
θ
2
α
2
2
)
which denotes that both red and black points are swept by the Jacobi point relaxation method, where α
⃑
=
(
α
1
,
α
2
)
∈
Λ. Further, substituting (57) into (64), when ω
=
1, (64) is written as
(65)
A
00
R
=
A
00
B
=
1
-
(
s
1
+
s
2
)
A
11
R
=
A
11
B
=
s
1
+
s
2
-
1
A
10
R
=
A
10
B
=
s
1
-
s
2
A
01
R
=
A
01
B
=
-
(
s
1
-
s
2
)
.
Substituting (65) into (48), the Fourier representation of S
h
R
B
(
ω
) with ω
=
1 is expressed as
(66)
S
^
h
R
B
(
θ
⃑
,
1
)
=
diag
⁡
(
S
^
11
,
S
^
22
)
,
where
(67)
S
^
11
=
(


1
2
(
s
1
+
s
2
-
1
)
(
s
1
+
s
2
-
2
)
-
1
2
(
s
1
+
s
2
-
1
)
(
s
1
+
s
2
-
2
)
-
1
2
(
s
1
+
s
2
-
1
)
(
s
1
+
s
2
)
1
2
(
s
1
+
s
2
-
1
)
(
s
1
+
s
2
)


)

,
S
^
22
=
(
1
2
(
s
1
+
s
2
-
1
)
(
s
1
+
s
2
)
-
1
2
(
s
1
-
s
2
+
1
)
(
s
1
-
s
2
)
1
2
(
s
2
-
s
1
+
1
)
(
s
1
-
s
2
)
-
1
2
(
s
2
-
s
1
+
1
)
(
s
1
-
s
2
)
)
.
From (13) and (35), the Fourier representation of operator Q
h
H is given as
(68)
Q
^
h
H
=
diag
⁡
(
Q
^
11
,
Q
^
22
)
,
where Q
^
11
=
diag
⁡
(
0,1
), Q
^
22
=
diag
⁡
(
1,1
). Therefore, the product of (66) and (68) is obtained as
(69)
Q
^
h
H
S
^
h
R
B
(
θ
⃑
,
1
)
=
diag
⁡
(
Q
^
11
S
^
11
,
Q
^
22
S
^
22
)
,
in which the diagonal blocks are expressed as
(70)
Q
^
11
S
^
11
=
(
0
0
-
(
s
1
+
s
2
)
(
s
1
+
s
2
-
1
)
2
(
s
1
+
s
2
)
(
s
1
+
s
2
-
1
)
2
)
,
(71)
Q
^
22
S
^
22
=
(
(
s
1
-
s
2
)
(
s
1
-
s
2
+
1
)
2
-
(
s
1
-
s
2
)
(
s
1
-
s
2
+
1
)
2
(
s
1
-
s
2
)
(
s
2
-
s
1
+
1
)
2
-
(
s
1
-
s
2
)
(
s
2
-
s
1
+
1
)
2
)
.
The eigenvalues of the matrix (69) are obtained as
(72)
λ
1
=
0
,
λ
2
=
(
s
1
-
s
2
)
2
,
λ
3
=
0
,
λ
4
=
(
s
1
+
s
2
)
(
s
1
+
s
2
-
1
)
2
.
When θ
⃑
∈
Θ
low, the maximum and minimum eigenvalues of the matrix Q
^
h
H
S
^
h
R
B
(
θ
⃑
,
1
) are as follows:
(73)
λ
max
⁡
(
Q
^
h
H
S
^
h
R
B
(
θ
⃑
,
1
)
)
=
max
⁡
(
s
1
,
s
2
)
∈
[
0,1
/
2
]
2
{
λ
1
,
λ
2
,
λ
3
,
λ
4
}
=
max
⁡
(
s
1
,
s
2
)
∈
[
0,1
/
2
]
2
λ
2
=
1
4
,
(74)
λ
min
⁡
(
Q
^
h
H
S
^
h
R
B
(
θ
⃑
,
1
)
)
=
min
⁡
(
s
1
,
s
2
)
∈
[
0,1
/
2
]
2
{
λ
1
,
λ
2
,
λ
3
,
λ
4
}
=
min
⁡
(
s
1
,
s
2
)
∈
[
0,1
/
2
]
2
λ
4
=
-
1
8
.
Therefore, by using (54), the values of the optimal smoothing parameters for the Poisson equation are obtained as
(75)
S
max
⁡
=
λ
max
⁡
(
Q
^
h
H
S
^
h
R
B
(
θ
⃑
,
1
)
)
|
θ
⃑
=
(
0
,
π
/
2
)
=
1
4
,
S
min
⁡
=
λ
min
⁡
(
Q
^
h
H
S
^
h
R
B
(
θ
⃑
,
1
)
)
|
θ
⃑
=
(
π
/
2,0
)
=
-
1
8
,
(76)
ω
opt
=
2
2
-
S
max
⁡
-
S
min
⁡
=
16
15
,
ρ
opt
=
S
max
⁡
-
S
min
⁡
2
-
S
max
⁡
-
S
min
⁡
=
1
5
.


## 5. Extending Two-Color to Multicolor Relaxation

Herein, the proposed smoothing analysis process of two-color relaxation is generalized to a 3D system. The Fourier representation of the smoothing operator for two-color relaxation is still a 2-order square matrix in (17). The result in (35) for a 3D case is changed to a 2
3
×
2
3 diagonal block matrix.For am-color relaxation (m
>
2), the infinite grid G
h is subdivided into m types of the grid points G
h
0
,
G
h
1
,
…
,
G
h
m
-
1 for presenting m different colors [11, 20]. Thus a complete analyzing step of the m-color relaxation consists of m substeps: at the βth step (β
=
0,1
,
…
,
m
-
1), the unknowns located at only x
⃑
∈
G
h
β are changed by using updated data at the previous step. For example, for the m-color relaxation of a 2D system, the infinite grid G
h is stated as
(77)
G
h
=
⋃
β
=
0
m
-
1
G
h
β
,
with
(78)
G
h
β
=
{
x
⃑
=
(
k
1
h
1
,
k
2
h
2
)
∣
k
1
+
k
2
=
β
mod
⁡
m
,
(
k
1
,
k
2
)
∈
Z
2
}
,
where β
∈
Λ
m
:
=
{
0,1
,
…
,
m
-
1
}. In the subdivisions of the infinite grids G
h, there are ∀
j, n
∈
Λ
m, j
≠
n, and G
h
j
∩
G
h
n
=
ϕ.For the standard coarsening [11, 20], the subspace of the 2h-harmonics is defined as
(79)
F
2
h
m
≔
span
⁡
{
φ
h
(
θ
⃑
0
,
x
⃑
)
,
φ
h
(
θ
⃑
1
,
x
⃑
)
,
…
,
φ
h
(
θ
⃑
m
-
1
,
x
⃑
)
}
,
where θ
⃑
∈
Θ
low, ∀
α
∈
Λ
m, and θ
⃑
α
=
(
θ
⃑
+
(
2
π
/
m
)
(
α
,
α
)
)
(
mod
⁡
2
π
).In order to obtain a Fourier representation of them-color point relaxation, let S
h
m
c
(
ω
) be the above complete m-color point relaxation operator and let S
h
β
(
ω
) be the βth subrelaxation (β
∈
Λ
m); thus, the m-color point relaxation is expressed as
(80)
S
h
m
c
(
ω
)
=
∏
β
=
0
m
-
1
S
h
β
(
ω
)
with
(81)
S
h
β
(
ω
)
φ
h
(
θ
⃑
α
,
x
⃑
)
=
{
A
α
β
φ
h
(
θ
⃑
α
,
x
⃑
)
x
⃑
∈
G
h
β
φ
h
(
θ
⃑
α
,
x
⃑
)
x
⃑
∉
G
h
β
,
where A
α
β
=
S
~
h
β
(
θ
⃑
α
,
ω
) denotes the Fourier symbol of S
h
β
(
ω
), α, β
∈
Λ
m. The proof of this process is analogous to the two-color case. In fact, as we know, the subspace of the 2h-harmonics F
2
h
m with m Fourier modes remains to be invariant for m-color point relaxation operator S
h
m
c
(
ω
); that is, S
h
m
c
(
ω
)
:
F
2
h
m
→
F
2
h
m. So, the Fourier representation of the m-color point relaxation (80) is given as S
^
h
m
c
(
ω
)
=
∏
β
=
0
m
-
1
S
^
h
β
(
ω
), where S
^
h
β
(
ω
) is a Fourier representation of S
h
β
(
ω
) in F
2
h
m.Proposition 7.
For∀
α, β
∈
Λ
m, ∀
x
⃑
∈
G
h
β, if θ
⃑
∈
Θ
low, the following equation holds:
(82)
φ
h
(
θ
⃑
α
,
x
⃑
)
=
exp
⁡
(
i
2
π
m
α
β
)
φ
h
(
θ
⃑
,
x
⃑
)
.
The proof is similar to Proposition 1.Theorem 8.
The iteration operator (80) for m-color point relaxation makes the subspace of the 2h-harmonics (79) invariant.
The proof is similar to Theorem3. In fact, in order to prove S
h
m
c
(
ω
)
:
F
2
h
m
→
F
2
h
m, one only needs to do ∀
β
∈
Λ
m, S
h
β
(
ω
)
:
F
2
h
m
→
F
2
h
m, which is equivalent to finding out m complex numbers a
j, j
∈
Λ
m, subject to
(83)
S
h
β
(
ω
)
φ
h
(
θ
⃑
α
,
x
⃑
)
=
∑
α
=
0
m
-
1
a
α
φ
h
(
θ
⃑
α
,
x
⃑
)
.
Being similar to the proof of Theorems3 and 6 and according to (81), (83) and Proposition 7, m linear equations on a
j are obtained as
(84)
a
0
+
a
1
+
a
2
+
⋯
+
a
m
-
1
=
1
x
⃑
∈
G
h
0
a
0
+
a
1
exp
⁡
(
i
2
π
m
)
+
a
2
exp
⁡
(
i
2
π
·
2
m
)
+
⋯
+
a
m
-
1
exp
⁡
[
i
2
π
(
m
-
1
)
m
]
=
exp
⁡
(
i
2
π
α
m
)
x
⃑
∈
G
h
1
a
0
+
a
1
exp
⁡
(
i
2
π
·
2
m
)
+
a
2
exp
⁡
(
i
2
π
·
4
m
)
a
a
a
a
+
⋯
+
a
m
-
1
exp
⁡
[
i
2
π
(
m
-
1
)
·
2
m
]
=
exp
⁡
(
i
2
π
·
2
α
m
)
a
a
a
a
a
a
a
a
a
a
a
a
x
⃑
∈
G
h
2
⋮
a
0
+
a
1
exp
⁡
(
i
2
π
·
β
m
)
+
a
2
exp
⁡
(
i
2
π
·
2
β
m
)
a
a
a
+
⋯
+
a
m
-
1
exp
⁡
[
i
2
π
(
m
-
1
)
·
β
m
]
=
A
α
β
exp
⁡
(
i
2
π
·
α
β
m
)
a
a
a
a
a
a
a
a
a
a
a
a
x
⃑
∈
G
h
β
⋮
a
0
+
a
1
exp
⁡
[
i
2
π
(
m
-
1
)
m
]
a
a
a
a
a
a
a
a
a
a
a
a
a
a
+
a
2
exp
⁡
[
i
2
π
·
2
(
m
-
1
)
m
]
+
⋯
a
a
a
a
+
a
m
-
1
exp
⁡
[
i
2
π
(
m
-
1
)
·
(
m
-
1
)
m
]
a
=
exp
⁡
[
i
2
π
(
m
-
1
)
·
α
m
]
a
a
a
a
a
a
a
a
a
a
a
a
a
x
⃑
∈
G
h
m
-
1
.
Letting η
=
2
π
/
m, ξ
n
=
exp
⁡
(
i
n
η
) with n
∈
Λ
m, the equations are simplified as
(85)
N
a
⃑
=
b
⃑
β
,
where a
⃑
=
(
a
0
,
a
1
,
…
,
a
m
-
1
)
T, b
⃑
β
=
(
ξ
0
,
ξ
1
,
…
,
A
α
β
ξ
1
α
β
,
…
,
ξ
m
-
1
α
)
T, T denotes transposition of matrix or vector, and N is the Vander monde matrix; namely,
(86)
N
=
(
1
1
⋯
1
ξ
0
ξ
1
⋯
ξ
m
-
1
⋮
⋮
⋱
⋮
ξ
0
m
-
1
ξ
1
m
-
1
⋯
ξ
m
-
1
m
-
1
)
.
Because of  ∀
j
≠
n
∈
Λ
m, ξ
j
≠
ξ
n, the determinant of the matrix N is nonzero. Therefore, from (83)–(86), for ∀
α, β
∈
Λ
m, the Fourier representation of the βth substep relaxation in F
2
h
m is obtained as
(87)
S
^
h
β
(
ω
)
=
N
-
1
N
β
in which N
β is a square matrix which is obtained by substituting ξ
⃑
β
=
(
A
α
β
ξ
0
β
,
A
α
β
ξ
1
β
,
…
,
A
α
β
ξ
m
-
1
β
) for the βth row of the matrix N, and A
α
β
=
S
~
h
β
(
θ
⃑
α
,
ω
). Therefore, from (80) and (87), the Fourier representation of the m-color point relaxation in the subspace of the 2h-harmonics F
2
h
m is stated as
(88)
S
^
h
m
c
(
ω
)
=
∏
β
=
0
m
-
1
N
-
1
N
β
.
Theorem 8 holds.


## 6. Conclusions

A novel smoothing analysis process of the two-color point relaxation for a 2D system is presented. The results are generalized to them-color point relaxation and extended to a 3D system. The applications to the 2D and 3D Poisson equations show that the computational domain over multigrids needs to be divided into the multisubsets to correspond with the different frequency modes in partial differential equations and to use the corresponding discretizing stencils. Meanwhile, the definition of the subspace based on the 2h-harmonics has to be agreeable to the subdomains of the multigrids. It is an important fact that establishes a mathematical constitution among the various Fourier modes with the different 2h-harmonics and constructs a usable Fourier representation of the m-color point relaxation in subspace of the 2h-harmonics.



---

*Source: 490156-2014-09-25.xml*