Maintenance script: Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

2026-08-23T03:10:08Z

Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

← Revisi sebelumnya		Revisi per 23 Agustus 2026 03.10
Baris 65:		Baris 65:
	yang harus diselesaikan pada tahap postprocessing. Penggandaan-kiri oleh setara dengan pemecahan <math>p</math> sistem formulir		yang harus diselesaikan pada tahap postprocessing. Penggandaan-kiri oleh setara dengan pemecahan <math>p</math> sistem formulir

	:		:

	(menghilangkan dan untuk <math>j=1</math>, dan dan untuk <math>j=p</math>), yang dapat dilakukan secara paralel.		(menghilangkan dan untuk <math>j=1</math>, dan dan untuk <math>j=p</math>), yang dapat dilakukan secara paralel.
Baris 154:		Baris 154:
	\end{cases}		\end{cases}
	</math>		</math>


	==Bacaan lanjutan==		==Bacaan lanjutan==
Baris 161:		Baris 160:
	== Sumber dan atribusi ==		== Sumber dan atribusi ==

	~~Artikel~~ ini diadaptasi ~~dalam mode teks~~ dari		Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Algoritma+SPIKE&oldid=29187969 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.
	[https://id.wikipedia.org/w/index.php?title=~~Algoritma_SPIKE~~&oldid=29187969 Wikipedia bahasa Indonesia],
	revisi 29187969 (2026-05-02T15:36:07Z).		<!-- WIKI_UNISSULA_PRESENTATION_V4 -->
	~~Gambar, media, infobox, templat navigasi~~, ~~dan kategori sumber~~
	~~tidak diimpor ke Wiki Unissula.~~
	~~Atribusi dan~~ lisensi ~~mengikuti ketentuan~~ Creative Commons
	Atribusi-BerbagiSerupa (CC BY-SA) ~~pada sumber Wikipedia~~.

Maintenance script: Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 29187969; atribusi sumber disertakan.

2026-08-23T02:34:06Z

Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 29187969; atribusi sumber disertakan.

Halaman baru

'''Algoritma SPIKE''' adalah solver [[Komputasi paralel|paralel]] hibrida untuk [[Sistem persamaan linear|sistem linear]] berpita yang dikembangkan oleh Eric Polizzi dan Ahmed Sameh.

== Ikhtisar ==
Algoritma SPIKE berkaitan dengan sistem linear '''<var>AX</var>''' = '''<var>F</var>''' , di mana '''<var>A</var>''' adalah sebuah banded <math>{\displaystyle n\times n}</math> matriks bandwidth jauh lebih sedikit daripada <math>{\displaystyle n}</math>, dan '''<var>F</var>''' adalah <math>{\displaystyle n\times s}</math> matriks yang mengandung <math>{\displaystyle s}</math> sisi kanan. Ini dibagi menjadi tahap preprocessing dan tahap postprocessing.

=== Tahap preprocessing ===
Pada tahap preprocessing, sistem linear '''<var>AX</var>''' = '''<var>F</var>''' dipartisi menjadi bentuk tridiagonal blok

: <math>
\begin{bmatrix}
\boldsymbol{A}_1 & \boldsymbol{B}_1\\
\boldsymbol{C}_2 & \boldsymbol{A}_2 & \boldsymbol{B}_2\\
& \ddots & \ddots & \ddots\\
& & \boldsymbol{C}_{p-1} & \boldsymbol{A}_{p-1} & \boldsymbol{B}_{p-1}\\
& & & \boldsymbol{C}_p & \boldsymbol{A}_p
\end{bmatrix}
\begin{bmatrix}
\boldsymbol{X}_1\\
\boldsymbol{X}_2\\
\vdots\\
\boldsymbol{X}_{p-1}\\
\boldsymbol{X}_p
\end{bmatrix}
=
\begin{bmatrix}
\boldsymbol{F}_1\\
\boldsymbol{F}_2\\
\vdots\\
\boldsymbol{F}_{p-1}\\
\boldsymbol{F}_p
\end{bmatrix}.
</math>

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

: ,

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

:: <math>
\begin{bmatrix}
\boldsymbol{I} & \boldsymbol{V}_1\\
\boldsymbol{W}_2 & \boldsymbol{I} & \boldsymbol{V}_2\\
& \ddots & \ddots & \ddots\\
& & \boldsymbol{W}_{p-1} & \boldsymbol{I} & \boldsymbol{V}_{p-1}\\
& & & \boldsymbol{W}_p & \boldsymbol{I}
\end{bmatrix}
\begin{bmatrix}
\boldsymbol{X}_1\\
\boldsymbol{X}_2\\
\vdots\\
\boldsymbol{X}_{p-1}\\
\boldsymbol{X}_p
\end{bmatrix}
=
\begin{bmatrix}
\boldsymbol{G}_1\\
\boldsymbol{G}_2\\
\vdots\\
\boldsymbol{G}_{p-1}\\
\boldsymbol{G}_p
\end{bmatrix},
</math>

yang harus diselesaikan pada tahap postprocessing. Penggandaan-kiri oleh setara dengan pemecahan <math>p</math> sistem formulir

:

(menghilangkan dan untuk <math>j=1</math>, dan dan untuk <math>j=p</math>), 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 <math>m</math> kolom (<math>m</math> jauh lebih sedikit dari <math>n</math>) (bantalan spike dengan kolom nol jika perlu). Partisi paku di semua dan ke

: <math>
\begin{bmatrix}
\boldsymbol{V}_j^{(t)}\\
\boldsymbol{V}_j'\\
\boldsymbol{V}_j^{(b)}
\end{bmatrix}
</math> and <math>
\begin{bmatrix}
\boldsymbol{W}_j^{(t)}\\
\boldsymbol{W}_j'\\
\boldsymbol{W}_j^{(b)}\\
\end{bmatrix}
</math>

dimana , , dan adalah dari dimensi <math>m\times m</math>. Partisi juga semua dan menjadi

: <math>
\begin{bmatrix}
\boldsymbol{X}_j^{(t)}\\
\boldsymbol{X}_j'\\
\boldsymbol{X}_j^{(b)}
\end{bmatrix}
</math> and <math>
\begin{bmatrix}
\boldsymbol{G}_j^{(t)}\\
\boldsymbol{G}_j'\\
\boldsymbol{G}_j^{(b)}\\
\end{bmatrix}.
</math>

Perhatikan bahwa sistem yang dihasilkan oleh tahap preprocessing dapat direduksi menjadi sistem pentadiagonal blok dengan ukuran yang jauh lebih kecil (ingat bahwa <math>m</math> jauh lebih sedikit dari <math>n</math>)

: <math>
\begin{bmatrix}
\boldsymbol{I}_m & \boldsymbol{0} & \boldsymbol{V}_1^{(t)}\\
\boldsymbol{0} & \boldsymbol{I}_m & \boldsymbol{V}_1^{(b)} & \boldsymbol{0}\\
\boldsymbol{0} & \boldsymbol{W}_2^{(t)} & \boldsymbol{I}_m & \boldsymbol{0} & \boldsymbol{V}_2^{(t)}\\
& \boldsymbol{W}_2^{(b)} & \boldsymbol{0} & \boldsymbol{I}_m & \boldsymbol{V}_2^{(b)} & \boldsymbol{0} \\
& & \ddots & \ddots & \ddots & \ddots & \ddots\\
& & & \boldsymbol{0} & \boldsymbol{W}_{p-1}^{(t)} & \boldsymbol{I}_m & \boldsymbol{0} & \boldsymbol{V}_{p-1}^{(t)}\\
& & & & \boldsymbol{W}_{p-1}^{(b)} & \boldsymbol{0} & \boldsymbol{I}_m & \boldsymbol{V}_{p-1}^{(b)} & \boldsymbol{0}\\
& & & & & \boldsymbol{0} & \boldsymbol{W}_p^{(t)} & \boldsymbol{I}_m & \boldsymbol{0}\\
& & & & & & \boldsymbol{W}_p^{(b)} & \boldsymbol{0} & \boldsymbol{I}_m
\end{bmatrix}
\begin{bmatrix}
\boldsymbol{X}_1^{(t)}\\
\boldsymbol{X}_1^{(b)}\\
\boldsymbol{X}_2^{(t)}\\
\boldsymbol{X}_2^{(b)}\\
\vdots\\
\boldsymbol{X}_{p-1}^{(t)}\\
\boldsymbol{X}_{p-1}^{(b)}\\
\boldsymbol{X}_p^{(t)}\\
\boldsymbol{X}_p^{(b)}
\end{bmatrix}
=
\begin{bmatrix}
\boldsymbol{G}_1^{(t)}\\
\boldsymbol{G}_1^{(b)}\\
\boldsymbol{G}_2^{(t)}\\
\boldsymbol{G}_2^{(b)}\\
\vdots\\
\boldsymbol{G}_{p-1}^{(t)}\\
\boldsymbol{G}_{p-1}^{(b)}\\
\boldsymbol{G}_p^{(t)}\\
\boldsymbol{G}_p^{(b)}
\end{bmatrix}\text{,}
</math>

yang kami sebut sistem tereduksi dan dilambangkan dengan .

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

: <math>
\begin{cases}
\boldsymbol{X}_1'=\boldsymbol{G}_1'-\boldsymbol{V}_1'\boldsymbol{X}_2^{(t)}\text{,}\\
\boldsymbol{X}_j'=\boldsymbol{G}_j'-\boldsymbol{V}_j'\boldsymbol{X}_{j+1}^{(t)}-\boldsymbol{W}_j'\boldsymbol{X}_{j-1}^{(b)}\text{,} & j=2,\ldots,p-1\text{,}\\
\boldsymbol{X}_p'=\boldsymbol{G}_p'-\boldsymbol{W}_p\boldsymbol{X}_{p-1}^{(b)}\text{.}
\end{cases}
</math>

==Bacaan lanjutan==
*

== Sumber dan atribusi ==

Artikel ini diadaptasi dalam mode teks dari
[https://id.wikipedia.org/w/index.php?title=Algoritma_SPIKE&oldid=29187969 Wikipedia bahasa Indonesia],
revisi 29187969 (2026-05-02T15:36:07Z).
Gambar, media, infobox, templat navigasi, dan kategori sumber
tidak diimpor ke Wiki Unissula.
Atribusi dan lisensi mengikuti ketentuan Creative Commons
Atribusi-BerbagiSerupa (CC BY-SA) pada sumber Wikipedia.

Algoritma SPIKE - Riwayat revisi

Maintenance script: Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

Maintenance script: Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 29187969; atribusi sumber disertakan.