Algoritma SPIKE

Algoritma SPIKE adalah solver paralel hibrida untuk sistem linear berpita yang dikembangkan oleh Eric Polizzi dan Ahmed Sameh.Templat:RefTemplat:NoteTemplat:Ref

Ikhtisar

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

$\left[\begin{array}{cc}{𝑨}_1& {𝑩}_1\\ {𝑪}_2& {𝑨}_2& {𝑩}_2\\ & \ddots & \ddots & \ddots \\ & & {𝑪}_{p-1}& {𝑨}_{p-1}& {𝑩}_{p-1}\\ & & & {𝑪}_p& {𝑨}_p\end{array}\right]\left[\begin{array}{c}{𝑿}_1\\ {𝑿}_2\\ ⋮\\ {𝑿}_{p-1}\\ {𝑿}_p\end{array}\right]=\left[\begin{array}{c}{𝑭}_1\\ {𝑭}_2\\ ⋮\\ {𝑭}_{p-1}\\ {𝑭}_p\end{array}\right].$

Asumsikan, untuk saat ini, bahwa blok diagonal Templat:Math (Templat:Math dengan Templat:Math) adalah nonsingular. Tentukan matriks blok diagonal

Templat:Math,

maka Templat:Math juga nonsingular. Kiri-mengalikan Templat:Math untuk kedua sisi sistem memberi

$\left[\begin{array}{cc}𝑰& {𝑽}_1\\ {𝑾}_2& 𝑰& {𝑽}_2\\ & \ddots & \ddots & \ddots \\ & & {𝑾}_{p-1}& 𝑰& {𝑽}_{p-1}\\ & & & {𝑾}_p& 𝑰\end{array}\right]\left[\begin{array}{c}{𝑿}_1\\ {𝑿}_2\\ ⋮\\ {𝑿}_{p-1}\\ {𝑿}_p\end{array}\right]=\left[\begin{array}{c}{𝑮}_1\\ {𝑮}_2\\ ⋮\\ {𝑮}_{p-1}\\ {𝑮}_p\end{array}\right],$

yang harus diselesaikan pada tahap postprocessing. Penggandaan-kiri oleh Templat:Math setara dengan pemecahan $p$ sistem formulir

Templat:Math

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

Karena sifat berpita Templat:Math, hanya beberapa kolom paling kiri dari setiap Templat:Math dan beberapa kolom paling kanan dari masing-masing Templat:Math 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 Templat:Math dan Templat:Math ke

$\left[\begin{array}{c}{𝑽}_j^{(t)}\\ {{𝑽}_j}^{\prime }\\ {𝑽}_j^{(b)}\end{array}\right]$ and $\left[\begin{array}{c}{𝑾}_j^{(t)}\\ {{𝑾}_j}^{\prime }\\ {𝑾}_j^{(b)}\end{array}\right]$

dimana Templat:Math, Templat:Math, Templat:Math dan Templat:Math adalah dari dimensi $m\times m$. Partisi juga semua Templat:Math dan Templat:Math menjadi

$\left[\begin{array}{c}{𝑿}_j^{(t)}\\ {{𝑿}_j}^{\prime }\\ {𝑿}_j^{(b)}\end{array}\right]$ and $\left[\begin{array}{c}{𝑮}_j^{(t)}\\ {{𝑮}_j}^{\prime }\\ {𝑮}_j^{(b)}\end{array}\right].$

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$)

$\left[\begin{array}{ccc}{𝑰}_m& 0& {𝑽}_1^{(t)}\\ 0& {𝑰}_m& {𝑽}_1^{(b)}& 0\\ 0& {𝑾}_2^{(t)}& {𝑰}_m& 0& {𝑽}_2^{(t)}\\ & {𝑾}_2^{(b)}& 0& {𝑰}_m& {𝑽}_2^{(b)}& 0\\ & & \ddots & \ddots & \ddots & \ddots & \ddots \\ & & & 0& {𝑾}_{p-1}^{(t)}& {𝑰}_m& 0& {𝑽}_{p-1}^{(t)}\\ & & & & {𝑾}_{p-1}^{(b)}& 0& {𝑰}_m& {𝑽}_{p-1}^{(b)}& 0\\ & & & & & 0& {𝑾}_p^{(t)}& {𝑰}_m& 0\\ & & & & & & {𝑾}_p^{(b)}& 0& {𝑰}_m\end{array}\right]\left[\begin{array}{c}{𝑿}_1^{(t)}\\ {𝑿}_1^{(b)}\\ {𝑿}_2^{(t)}\\ {𝑿}_2^{(b)}\\ ⋮\\ {𝑿}_{p-1}^{(t)}\\ {𝑿}_{p-1}^{(b)}\\ {𝑿}_p^{(t)}\\ {𝑿}_p^{(b)}\end{array}\right]=\left[\begin{array}{c}{𝑮}_1^{(t)}\\ {𝑮}_1^{(b)}\\ {𝑮}_2^{(t)}\\ {𝑮}_2^{(b)}\\ ⋮\\ {𝑮}_{p-1}^{(t)}\\ {𝑮}_{p-1}^{(b)}\\ {𝑮}_p^{(t)}\\ {𝑮}_p^{(b)}\end{array}\right]\text{,}$

yang kami sebut sistem tereduksi dan dilambangkan dengan Templat:Math.

Setelah semua Templat:Math dan Templat:Math ditemukan, semua Templat:Math dapat dipulihkan dengan paralelisme sempurna via

$\{\begin{array}{c}{{𝑿}_1}^{\prime }={{𝑮}_1}^{\prime }-{{𝑽}_1}^{\prime }{𝑿}_2^{(t)}\text{,}\\ {{𝑿}_j}^{\prime }={{𝑮}_j}^{\prime }-{{𝑽}_j}^{\prime }{𝑿}_{j+1}^{(t)}-{{𝑾}_j}^{\prime }{𝑿}_{j-1}^{(b)}\text{,}& j=2,\dots ,p-1\text{,}\\ {{𝑿}_p}^{\prime }={{𝑮}_p}^{\prime }-{𝑾}_p{𝑿}_{p-1}^{(b)}\text{.}\end{array}$

Bacaan lanjutan

• Templat:Cite book