Algoritma SPIKE

Algoritma SPIKE adalah solver paralel hibrida untuk sistem linear berpita yang dikembangkan oleh Eric Polizzi dan Ahmed Sameh.^

Ikhtisar

Algoritma SPIKE berkaitan dengan sistem linear AX = F , di mana A adalah sebuah banded ${\displaystyle n\times n}$ matriks bandwidth jauh lebih sedikit daripada ${\displaystyle n}$, dan F adalah ${\displaystyle n\times s}$ matriks yang mengandung ${\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

${\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₁,...,A_p),

maka D juga nonsingular. Kiri-mengalikan D⁻¹ untuk kedua sisi sistem memberi

${\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⁻¹ setara dengan pemecahan $p$ sistem formulir

A_j[V_j W_j G_j] = [B_j C_j F_j]

(menghilangkan W₁ dan C₁ untuk $j=1$, dan V_p dan B_p untuk $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

Tanpa kehilangan sifat umum, asumsikan bahwa setiap lonjakan mengandung tepat $m$ kolom ($m$ jauh lebih sedikit dari $n$) (bantalan spike dengan kolom nol jika perlu). Partisi paku di semua V_j dan W_j ke

${\begin{bmatrix}{\boldsymbol {V}}_{j}^{(t)}\\{\boldsymbol {V}}_{j}'\\{\boldsymbol {V}}_{j}^{(b)}\end{bmatrix}}$ and ${\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\times m$. Partisi juga semua X_j dan G_j menjadi

${\begin{bmatrix}{\boldsymbol {X}}_{j}^{(t)}\\{\boldsymbol {X}}_{j}'\\{\boldsymbol {X}}_{j}^{(b)}\end{bmatrix}}$ and ${\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$ jauh lebih sedikit dari $n$)

${\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

${\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.