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

[\begin{matrix} 𝑨_{1} & 𝑩_{1} \\ 𝑪_{2} & 𝑨_{2} & 𝑩_{2} \\ ⋱ & ⋱ & ⋱ \\ 𝑪_{p - 1} & 𝑨_{p - 1} & 𝑩_{p - 1} \\ 𝑪_{p} & 𝑨_{p} \end{matrix}] [\begin{matrix} 𝑿_{1} \\ 𝑿_{2} \\ ⋮ \\ 𝑿_{p - 1} \\ 𝑿_{p} \end{matrix}] = [\begin{matrix} 𝑭_{1} \\ 𝑭_{2} \\ ⋮ \\ 𝑭_{p - 1} \\ 𝑭_{p} \end{matrix}] .

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{matrix} 𝑰 & 𝑽_{1} \\ 𝑾_{2} & 𝑰 & 𝑽_{2} \\ ⋱ & ⋱ & ⋱ \\ 𝑾_{p - 1} & 𝑰 & 𝑽_{p - 1} \\ 𝑾_{p} & 𝑰 \end{matrix}] [\begin{matrix} 𝑿_{1} \\ 𝑿_{2} \\ ⋮ \\ 𝑿_{p - 1} \\ 𝑿_{p} \end{matrix}] = [\begin{matrix} 𝑮_{1} \\ 𝑮_{2} \\ ⋮ \\ 𝑮_{p - 1} \\ 𝑮_{p} \end{matrix}],

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{matrix} 𝑽_{j}^{(t)} \\ {𝑽_{j}}^{'} \\ 𝑽_{j}^{(b)} \end{matrix}]

and

[\begin{matrix} 𝑾_{j}^{(t)} \\ {𝑾_{j}}^{'} \\ 𝑾_{j}^{(b)} \end{matrix}]

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

[\begin{matrix} 𝑿_{j}^{(t)} \\ {𝑿_{j}}^{'} \\ 𝑿_{j}^{(b)} \end{matrix}]

and

[\begin{matrix} 𝑮_{j}^{(t)} \\ {𝑮_{j}}^{'} \\ 𝑮_{j}^{(b)} \end{matrix}] .

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{matrix} 𝑰_{m} & 0 & 𝑽_{1}^{(t)} \\ 0 & 𝑰_{m} & 𝑽_{1}^{(b)} & 0 \\ 0 & 𝑾_{2}^{(t)} & 𝑰_{m} & 0 & 𝑽_{2}^{(t)} \\ 𝑾_{2}^{(b)} & 0 & 𝑰_{m} & 𝑽_{2}^{(b)} & 0 \\ ⋱ & ⋱ & ⋱ & ⋱ & ⋱ \\ 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{matrix}] [\begin{matrix} 𝑿_{1}^{(t)} \\ 𝑿_{1}^{(b)} \\ 𝑿_{2}^{(t)} \\ 𝑿_{2}^{(b)} \\ ⋮ \\ 𝑿_{p - 1}^{(t)} \\ 𝑿_{p - 1}^{(b)} \\ 𝑿_{p}^{(t)} \\ 𝑿_{p}^{(b)} \end{matrix}] = [\begin{matrix} 𝑮_{1}^{(t)} \\ 𝑮_{1}^{(b)} \\ 𝑮_{2}^{(t)} \\ 𝑮_{2}^{(b)} \\ ⋮ \\ 𝑮_{p - 1}^{(t)} \\ 𝑮_{p - 1}^{(b)} \\ 𝑮_{p}^{(t)} \\ 𝑮_{p}^{(b)} \end{matrix}],

yang kami sebut sistem tereduksi dan dilambangkan dengan .

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

{\begin{matrix} {𝑿_{1}}^{'} = {𝑮_{1}}^{'} - {𝑽_{1}}^{'} 𝑿_{2}^{(t)}, \\ {𝑿_{j}}^{'} = {𝑮_{j}}^{'} - {𝑽_{j}}^{'} 𝑿_{j + 1}^{(t)} - {𝑾_{j}}^{'} 𝑿_{j - 1}^{(b)}, & j = 2, \dots, p - 1, \\ {𝑿_{p}}^{'} = {𝑮_{p}}^{'} - 𝑾_{p} 𝑿_{p - 1}^{(b)} . \end{matrix}

Bacaan lanjutan

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.