Algoritma SPIKE adalah solver paralel hibrida untuk sistem linear berpita yang dikembangkan oleh Eric Polizzi dan Ahmed Sameh.[1]^[2]
Algoritma SPIKE berkaitan dengan sistem linear AX = F , di mana A adalah sebuah banded
matriks bandwidth jauh lebih sedikit daripada
, dan F adalah
matriks yang mengandung
sisi kanan. Ini dibagi menjadi tahap preprocessing dan tahap postprocessing.
Pada tahap preprocessing, sistem linear AX = F dipartisi menjadi bentuk tridiagonal blok
![{\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}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/97b511eaf3fb2777955a0d335fc74b08645190f5)
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
![{\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}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/124e391a472aced2370716c14f531df4bec1fd73)
yang harus diselesaikan pada tahap postprocessing. Penggandaan-kiri oleh D−1 setara dengan pemecahan
sistem formulir
- Aj[Vj Wj Gj] = [Bj Cj Fj]
(menghilangkan W1 dan C1 untuk
, dan Vp dan Bp untuk
), 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.
Tanpa kehilangan sifat umum, asumsikan bahwa setiap lonjakan mengandung tepat
kolom (
jauh lebih sedikit dari
) (bantalan spike dengan kolom nol jika perlu). Partisi paku di semua Vj dan Wj ke
and ![{\displaystyle {\begin{bmatrix}{\boldsymbol {W}}_{j}^{(t)}\\{\boldsymbol {W}}_{j}'\\{\boldsymbol {W}}_{j}^{(b)}\\\end{bmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dec1eb05d78e2269186c5aaf9782cc3a053ad5b3)
dimana V (t)
j , V (b)
j , W (t)
j dan W (b)
j adalah dari dimensi
. Partisi juga semua Xj dan Gj menjadi
and ![{\displaystyle {\begin{bmatrix}{\boldsymbol {G}}_{j}^{(t)}\\{\boldsymbol {G}}_{j}'\\{\boldsymbol {G}}_{j}^{(b)}\\\end{bmatrix}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4b4055538a6528629d29af4d80870e305236491e)
Perhatikan bahwa sistem yang dihasilkan oleh tahap preprocessing dapat direduksi menjadi sistem pentadiagonal blok dengan ukuran yang jauh lebih kecil (ingat bahwa
jauh lebih sedikit dari
)
![{\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{,}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fb78200382ba19a89c5670436e88d65b12afa5df)
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
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a7478664bdd280e5307dbd90dd6991e05a20afc4)