- Source: Algoritma SPIKE
Algoritma SPIKE adalah solver paralel hibrida untuk sistem linear berpita yang dikembangkan oleh Eric Polizzi dan Ahmed Sameh.[1]^[2]
Ikhtisar
Algoritma SPIKE berkaitan dengan sistem linear AX = F , di mana A adalah sebuah banded
n
×
n
{\displaystyle {\displaystyle n\times n}}
matriks bandwidth jauh lebih sedikit daripada
n
{\displaystyle {\displaystyle n}}
, dan F adalah
n
×
s
{\displaystyle {\displaystyle n\times s}}
matriks yang mengandung
s
{\displaystyle {\displaystyle s}}
sisi kanan. Ini dibagi menjadi tahap preprocessing dan tahap postprocessing.
= Tahap preprocessing
=Pada tahap preprocessing, sistem linear AX = F dipartisi menjadi bentuk tridiagonal blok
[
A
1
B
1
C
2
A
2
B
2
⋱
⋱
⋱
C
p
−
1
A
p
−
1
B
p
−
1
C
p
A
p
]
[
X
1
X
2
⋮
X
p
−
1
X
p
]
=
[
F
1
F
2
⋮
F
p
−
1
F
p
]
.
{\displaystyle {\begin{bmatrix}{\boldsymbol {A}}_{1}&{\boldsymbol {B}}_{1}\\{\boldsymbol {C}}_{2}&{\boldsymbol {A}}_{2}&{\boldsymbol {B}}_{2}\\&\ddots &\ddots &\ddots \\&&{\boldsymbol {C}}_{p-1}&{\boldsymbol {A}}_{p-1}&{\boldsymbol {B}}_{p-1}\\&&&{\boldsymbol {C}}_{p}&{\boldsymbol {A}}_{p}\end{bmatrix}}{\begin{bmatrix}{\boldsymbol {X}}_{1}\\{\boldsymbol {X}}_{2}\\\vdots \\{\boldsymbol {X}}_{p-1}\\{\boldsymbol {X}}_{p}\end{bmatrix}}={\begin{bmatrix}{\boldsymbol {F}}_{1}\\{\boldsymbol {F}}_{2}\\\vdots \\{\boldsymbol {F}}_{p-1}\\{\boldsymbol {F}}_{p}\end{bmatrix}}.}
Asumsikan, untuk saat ini, bahwa blok diagonal Aj (j = 1,...,p dengan p ≥ 2) adalah nonsingular. Tentukan matriks blok diagonal
D = diag(A1,...,Ap),
maka D juga nonsingular. Kiri-mengalikan D−1 untuk kedua sisi sistem memberi
[
I
V
1
W
2
I
V
2
⋱
⋱
⋱
W
p
−
1
I
V
p
−
1
W
p
I
]
[
X
1
X
2
⋮
X
p
−
1
X
p
]
=
[
G
1
G
2
⋮
G
p
−
1
G
p
]
,
{\displaystyle {\begin{bmatrix}{\boldsymbol {I}}&{\boldsymbol {V}}_{1}\\{\boldsymbol {W}}_{2}&{\boldsymbol {I}}&{\boldsymbol {V}}_{2}\\&\ddots &\ddots &\ddots \\&&{\boldsymbol {W}}_{p-1}&{\boldsymbol {I}}&{\boldsymbol {V}}_{p-1}\\&&&{\boldsymbol {W}}_{p}&{\boldsymbol {I}}\end{bmatrix}}{\begin{bmatrix}{\boldsymbol {X}}_{1}\\{\boldsymbol {X}}_{2}\\\vdots \\{\boldsymbol {X}}_{p-1}\\{\boldsymbol {X}}_{p}\end{bmatrix}}={\begin{bmatrix}{\boldsymbol {G}}_{1}\\{\boldsymbol {G}}_{2}\\\vdots \\{\boldsymbol {G}}_{p-1}\\{\boldsymbol {G}}_{p}\end{bmatrix}},}
yang harus diselesaikan pada tahap postprocessing. Penggandaan-kiri oleh D−1 setara dengan pemecahan
p
{\displaystyle p}
sistem formulir
Aj[Vj Wj Gj] = [Bj Cj Fj]
(menghilangkan W1 dan C1 untuk
j
=
1
{\displaystyle j=1}
, dan Vp dan Bp untuk
j
=
p
{\displaystyle j=p}
), yang dapat dilakukan secara paralel.
Karena sifat berpita A, hanya beberapa kolom paling kiri dari setiap Vj dan beberapa kolom paling kanan dari masing-masing Wj dapat berupa nol. Kolom ini disebut spike.
= Tahap postprocessing
=Tanpa kehilangan sifat umum, asumsikan bahwa setiap lonjakan mengandung tepat
m
{\displaystyle m}
kolom (
m
{\displaystyle m}
jauh lebih sedikit dari
n
{\displaystyle n}
) (bantalan spike dengan kolom nol jika perlu). Partisi paku di semua Vj dan Wj ke
[
V
j
(
t
)
V
j
′
V
j
(
b
)
]
{\displaystyle {\begin{bmatrix}{\boldsymbol {V}}_{j}^{(t)}\\{\boldsymbol {V}}_{j}'\\{\boldsymbol {V}}_{j}^{(b)}\end{bmatrix}}}
and
[
W
j
(
t
)
W
j
′
W
j
(
b
)
]
{\displaystyle {\begin{bmatrix}{\boldsymbol {W}}_{j}^{(t)}\\{\boldsymbol {W}}_{j}'\\{\boldsymbol {W}}_{j}^{(b)}\\\end{bmatrix}}}
dimana V (t)j , V (b)j , W (t)j dan W (b)j adalah dari dimensi
m
×
m
{\displaystyle m\times m}
. Partisi juga semua Xj dan Gj menjadi
[
X
j
(
t
)
X
j
′
X
j
(
b
)
]
{\displaystyle {\begin{bmatrix}{\boldsymbol {X}}_{j}^{(t)}\\{\boldsymbol {X}}_{j}'\\{\boldsymbol {X}}_{j}^{(b)}\end{bmatrix}}}
and
[
G
j
(
t
)
G
j
′
G
j
(
b
)
]
.
{\displaystyle {\begin{bmatrix}{\boldsymbol {G}}_{j}^{(t)}\\{\boldsymbol {G}}_{j}'\\{\boldsymbol {G}}_{j}^{(b)}\\\end{bmatrix}}.}
Perhatikan bahwa sistem yang dihasilkan oleh tahap preprocessing dapat direduksi menjadi sistem pentadiagonal blok dengan ukuran yang jauh lebih kecil (ingat bahwa
m
{\displaystyle m}
jauh lebih sedikit dari
n
{\displaystyle n}
)
[
I
m
0
V
1
(
t
)
0
I
m
V
1
(
b
)
0
0
W
2
(
t
)
I
m
0
V
2
(
t
)
W
2
(
b
)
0
I
m
V
2
(
b
)
0
⋱
⋱
⋱
⋱
⋱
0
W
p
−
1
(
t
)
I
m
0
V
p
−
1
(
t
)
W
p
−
1
(
b
)
0
I
m
V
p
−
1
(
b
)
0
0
W
p
(
t
)
I
m
0
W
p
(
b
)
0
I
m
]
[
X
1
(
t
)
X
1
(
b
)
X
2
(
t
)
X
2
(
b
)
⋮
X
p
−
1
(
t
)
X
p
−
1
(
b
)
X
p
(
t
)
X
p
(
b
)
]
=
[
G
1
(
t
)
G
1
(
b
)
G
2
(
t
)
G
2
(
b
)
⋮
G
p
−
1
(
t
)
G
p
−
1
(
b
)
G
p
(
t
)
G
p
(
b
)
]
,
{\displaystyle {\begin{bmatrix}{\boldsymbol {I}}_{m}&{\boldsymbol {0}}&{\boldsymbol {V}}_{1}^{(t)}\\{\boldsymbol {0}}&{\boldsymbol {I}}_{m}&{\boldsymbol {V}}_{1}^{(b)}&{\boldsymbol {0}}\\{\boldsymbol {0}}&{\boldsymbol {W}}_{2}^{(t)}&{\boldsymbol {I}}_{m}&{\boldsymbol {0}}&{\boldsymbol {V}}_{2}^{(t)}\\&{\boldsymbol {W}}_{2}^{(b)}&{\boldsymbol {0}}&{\boldsymbol {I}}_{m}&{\boldsymbol {V}}_{2}^{(b)}&{\boldsymbol {0}}\\&&\ddots &\ddots &\ddots &\ddots &\ddots \\&&&{\boldsymbol {0}}&{\boldsymbol {W}}_{p-1}^{(t)}&{\boldsymbol {I}}_{m}&{\boldsymbol {0}}&{\boldsymbol {V}}_{p-1}^{(t)}\\&&&&{\boldsymbol {W}}_{p-1}^{(b)}&{\boldsymbol {0}}&{\boldsymbol {I}}_{m}&{\boldsymbol {V}}_{p-1}^{(b)}&{\boldsymbol {0}}\\&&&&&{\boldsymbol {0}}&{\boldsymbol {W}}_{p}^{(t)}&{\boldsymbol {I}}_{m}&{\boldsymbol {0}}\\&&&&&&{\boldsymbol {W}}_{p}^{(b)}&{\boldsymbol {0}}&{\boldsymbol {I}}_{m}\end{bmatrix}}{\begin{bmatrix}{\boldsymbol {X}}_{1}^{(t)}\\{\boldsymbol {X}}_{1}^{(b)}\\{\boldsymbol {X}}_{2}^{(t)}\\{\boldsymbol {X}}_{2}^{(b)}\\\vdots \\{\boldsymbol {X}}_{p-1}^{(t)}\\{\boldsymbol {X}}_{p-1}^{(b)}\\{\boldsymbol {X}}_{p}^{(t)}\\{\boldsymbol {X}}_{p}^{(b)}\end{bmatrix}}={\begin{bmatrix}{\boldsymbol {G}}_{1}^{(t)}\\{\boldsymbol {G}}_{1}^{(b)}\\{\boldsymbol {G}}_{2}^{(t)}\\{\boldsymbol {G}}_{2}^{(b)}\\\vdots \\{\boldsymbol {G}}_{p-1}^{(t)}\\{\boldsymbol {G}}_{p-1}^{(b)}\\{\boldsymbol {G}}_{p}^{(t)}\\{\boldsymbol {G}}_{p}^{(b)}\end{bmatrix}}{\text{,}}}
yang kami sebut sistem tereduksi dan dilambangkan dengan S̃X̃ = G̃.
Setelah semua X (t)j dan X (b)j ditemukan, semua X′j dapat dipulihkan dengan paralelisme sempurna via
{
X
1
′
=
G
1
′
−
V
1
′
X
2
(
t
)
,
X
j
′
=
G
j
′
−
V
j
′
X
j
+
1
(
t
)
−
W
j
′
X
j
−
1
(
b
)
,
j
=
2
,
…
,
p
−
1
,
X
p
′
=
G
p
′
−
W
p
X
p
−
1
(
b
)
.
{\displaystyle {\begin{cases}{\boldsymbol {X}}_{1}'={\boldsymbol {G}}_{1}'-{\boldsymbol {V}}_{1}'{\boldsymbol {X}}_{2}^{(t)}{\text{,}}\\{\boldsymbol {X}}_{j}'={\boldsymbol {G}}_{j}'-{\boldsymbol {V}}_{j}'{\boldsymbol {X}}_{j+1}^{(t)}-{\boldsymbol {W}}_{j}'{\boldsymbol {X}}_{j-1}^{(b)}{\text{,}}&j=2,\ldots ,p-1{\text{,}}\\{\boldsymbol {X}}_{p}'={\boldsymbol {G}}_{p}'-{\boldsymbol {W}}_{p}{\boldsymbol {X}}_{p-1}^{(b)}{\text{.}}\end{cases}}}
Bacaan lanjutan
Gallopoulos, E.; Philippe, B.; Sameh, A.H. (2015). Parallelism in Matrix Computations. Springer. ISBN 978-94-017-7188-7.
