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
sunting
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 A j (j = 1,...,p dengan p ≥ 2 ) adalah nonsingular. Tentukan matriks blok diagonal
D = diag(A 1 ,...,A p ) ,
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
A j [V j W j G j ] = [B j C j F j ]
(menghilangkan W 1 dan C 1 untuk
j
=
1
{\displaystyle j=1}
, dan V p dan B p untuk
j
=
p
{\displaystyle j=p}
), yang dapat dilakukan secara paralel.
Karena sifat berpita A , hanya beberapa kolom paling kiri dari setiap V j dan beberapa kolom paling kanan dari masing-masing W j dapat berupa nol. Kolom ini disebut spike .
Tahap postprocessing
sunting
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 V j dan W j 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 X j dan G j 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
sunting