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 $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 ( dengan ) adalah nonsingular. Tentukan matriks blok diagonal

,

maka juga nonsingular. Kiri-mengalikan 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 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

$\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 , , dan adalah dari dimensi $m\times m$. Partisi juga semua dan 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 .

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

Sumber dan atribusi

Konten artikel ini diadaptasi dari Wikipedia bahasa Indonesia, revisi 29187969 (2026-05-02T15:36:07Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.