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 **<var>AX</var>** = **<var>F</var>** , di mana **<var>A</var>** adalah sebuah banded {\displaystyle n\times n} matriks bandwidth jauh lebih sedikit daripada {\displaystyle n}, dan **<var>F</var>** 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 **<var>AX</var>** = **<var>F</var>** 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  ( dengan ) adalah nonsingular. Tentukan matriks blok diagonal

: ,

maka  juga nonsingular. Kiri-mengalikan  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  setara dengan pemecahan p sistem formulir

: 

(menghilangkan  dan  untuk j=1, dan  dan  untuk j=p), yang dapat dilakukan secara paralel.

Karena sifat berpita , hanya beberapa kolom paling kiri dari setiap  dan beberapa kolom paling kanan dari masing-masing  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  dan  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 , ,  dan  adalah dari dimensi m\times m. Partisi juga semua  dan  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 .

Setelah semua  dan  ditemukan, semua  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
*