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  matriks bandwidth jauh lebih sedikit daripada , dan F adalah  matriks yang mengandung  sisi kanan. Ini dibagi menjadi tahap preprocessing dan tahap postprocessing.

Tahap preprocessing 
Pada tahap preprocessing, sistem linear AX = F dipartisi menjadi bentuk tridiagonal blok

 

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

 ,

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

 

yang harus diselesaikan pada tahap postprocessing. Penggandaan-kiri oleh  setara dengan pemecahan  sistem formulir

 

(menghilangkan  dan  untuk , dan  dan  untuk ), 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  kolom ( jauh lebih sedikit dari ) (bantalan spike dengan kolom nol jika perlu). Partisi paku di semua  dan  ke

  and 

dimana , ,  dan  adalah dari dimensi . Partisi juga semua  dan  menjadi

  and 

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 )

 

yang kami sebut sistem tereduksi dan dilambangkan dengan .

Setelah semua  dan  ditemukan, semua  dapat dipulihkan dengan paralelisme sempurna via

Bacaan lanjutan
 
Analisis
Analisis numerik
Aljabar
Algoritme
Linear