Lompat ke isi

Algoritma SPIKE

Dari Wikipedia bahasa Indonesia, ensiklopedia bebas

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

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

[sunting | sunting sumber]

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

Asumsikan, untuk saat ini, bahwa blok diagonal Aj (j = 1,...,p dengan p ≥ 2) adalah nonsingular. Tentukan matriks blok diagonal

D = diag(A1,...,Ap),

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

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

Aj[Vj Wj Gj] = [Bj Cj Fj]

(menghilangkan W1 dan C1 untuk , dan Vp dan Bp untuk ), yang dapat dilakukan secara paralel.

Karena sifat berpita A, hanya beberapa kolom paling kiri dari setiap Vj dan beberapa kolom paling kanan dari masing-masing Wj dapat berupa nol. Kolom ini disebut spike.

Tahap postprocessing

[sunting | sunting sumber]

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 Vj dan Wj ke

and

dimana V (t)
j
 
, V (b)
j
 
, W (t)
j
 
dan W (b)
j
 
adalah dari dimensi . Partisi juga semua Xj dan Gj 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 S̃X̃ = .

Setelah semua X (t)
j
 
dan X (b)
j
 
ditemukan, semua Xj dapat dipulihkan dengan paralelisme sempurna via

Bacaan lanjutan

[sunting | sunting sumber]