Domain Decomposition计算公式备忘
分类:
文章
•
2024-07-17 16:06:10
Domain Decompostion 计算公式
示意图
推导
- 基本公式：
{
s
=
S
−
1
F
s
−
S
−
1
W
R
h
h
=
(
H
−
W
L
S
−
1
W
R
)
−
1
(
F
h
−
W
L
S
−
1
F
s
)
\begin{cases} s=\bold{S}^{-1}F_s-\bold{S}^{-1}\bold{W}_Rh \\ h=(\bold{H}-\bold{W}_L\bold{S}^{-1}\bold{W}_R)^{-1}(F_h-\bold{W}_L\bold{S}^{-1}F_s) \end{cases}
{s=S−1Fs−S−1WRhh=(H−WLS−1WR)−1(Fh−WLS−1Fs)对正定对称阵有
S
=
L
L
t
\bold{S}=\bold{L}\bold{L}^t
S=LLt,
W
L
=
W
R
t
\bold{W}_L=\bold{W}_R^t
WL=WRt, 因而上面公式可化为：
{
s
=
L
−
t
(
L
−
1
F
s
−
L
−
1
W
R
h
)
h
=
(
H
−
(
L
−
1
W
R
)
t
(
L
−
1
W
R
)
)
−
1
(
F
h
−
(
L
−
1
W
R
)
t
(
L
−
1
F
s
)
)
\begin{cases} s=\bold{L}^{-t}(\bold{L}^{-1}F_s-\bold{L}^{-1}\bold{W}_Rh)\\ h=(\bold{H}-(\bold{L^{-1}W}_R)^{t}(\bold{L^{-1}W}_R))^{-1}(F_h-(\bold{L^{-1}W}_R)^{t}(\bold{L}^{-1}F_s)) \end{cases}
{s=L−t(L−1Fs−L−1WRh)h=(H−(L−1WR)t(L−1WR))−1(Fh−(L−1WR)t(L−1Fs))所以仅需要计算
L
−
1
W
R
\bold{L^{-1}W}_R
L−1WR 和
L
−
1
F
s
\bold{L}^{-1}F_s
L−1Fs。
计算步骤
- 并行分解
S
=
L
L
t
\bold{S}=\bold{L}\bold{L}^t
S=LLt
- 并行求解
L
−
1
F
s
\bold{L}^{-1}F_s
L−1Fs
- 并行求解
L
−
1
W
R
\bold{L^{-1}W}_R
L−1WR, 同时更新
H
\bold{H}
H矩阵。此处注意
W
R
\bold{W}_R
WR的非零稀疏性，可以利用加速计算。更新
H
\bold{H}
H矩阵需要考虑多个线程对
H
\bold{H}
H相同块的更新，需要锁和同步机制
- 更新后的
H
\bold{H}
H也是对称正定块状三对角阵，可以用块状分解计算LLT
- 先计算
h
h
h,之后计算
s
s
s
