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

2026-08-24T23:00:21Z

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

← Revisi sebelumnya		Revisi per 24 Agustus 2026 23.00
Baris 5:		Baris 5:

	== Algoritma ==		== Algoritma ==

	Misalkan ''A'', ''B'' dua [[matriks persegi]] pada ring ''R''. Kita ingin menghitung produk matriks ''C'' sebagai		Misalkan ''A'', ''B'' dua [[matriks persegi]] pada ring ''R''. Kita ingin menghitung produk matriks ''C'' sebagai

Baris 13:		Baris 12:

	Kita partisi ''A'', ''B'' dan ''C'' kedalam [[matriks blok]] yang berukuran sama.		Kita partisi ''A'', ''B'' dan ''C'' kedalam [[matriks blok]] yang berukuran sama.
	:<math>		:<math>
	\mathbf{A} =		\mathbf{A} =
	\begin{bmatrix}		\begin{bmatrix}
Baris 68:		Baris 67:

	== Analisi Numerik ==		== Analisi Numerik ==

	Perkalian matriks standar melakukan		Perkalian matriks standar melakukan
	:<math>n^3 = n^{\log_{2}8}</math>		:<math>n^3 = n^{\log_{2}8}</math>
Baris 79:		Baris 77:

	== Contoh program sederhana pada Matlab ==		== Contoh program sederhana pada Matlab ==

	function c = strass(a,b)		function c = strass(a,b)
	nmin = 2;		nmin = 2;
Baris 102:		Baris 99:

	Catatan: program diatas hanya untuk matriks berukuran 1x1, 2x2, 4x4. Untuk matriks yang berukuran lebih besar, masih diperlukan penyempurnaan. Agar programnya bisa berjalan.		Catatan: program diatas hanya untuk matriks berukuran 1x1, 2x2, 4x4. Untuk matriks yang berukuran lebih besar, masih diperlukan penyempurnaan. Agar programnya bisa berjalan.

	~~== Referensi ==~~

	* Strassen, Volker, ''Gaussian Elimination is not Optimal'', Numer. Math. 13, p. 354-356, 1969
	* [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]]. ''[[Introduction to Algorithms]]'', Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 28: Section 28.2: Strassen's algorithm for matrix multiplication, pp. 735–741.

	== Pranala luar ==		== Pranala luar ==
	* (also includes formulas for fast [[matrix inversion]])		* (also includes formulas for fast [[matrix inversion]])



	== Sumber dan atribusi ==		== Sumber dan atribusi ==

	Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Algoritma+Strassen&oldid=28365219 Wikipedia bahasa Indonesia], revisi 28365219 (2025-11-07T03:40:57Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.		Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Algoritma+Strassen&oldid=28365219 Wikipedia bahasa Indonesia], revisi 28365219 (2025-11-07T03:40:57Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.

			<!-- WIKI_UNISSULA_PRESENTATION_V4 -->

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

2026-08-24T22:26:11Z

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

Halaman baru

'''Algoritma Strassen''' dalam [[matematika]], khususnya [[aljabar]] [[linear]] adalah sebuah algoritma yang dinamakan oleh [[Volker Strassen]] yang merupakan sebuah algoritma yang digunakan untuk perkalian [[matriks]] yang secara [[asimtot]] lebih cepat daripada algoritma [[perkalian matriks]] standar dan sangat berguna dalam penggunaanya untuk matriks yang berukuran besar.

== Sejarah ==
Volker Strassen memublikasikan algoritma Strassen tahun [[1969]]. Meskipun algoritma ini hanya sedikit lebih cepat daripada algoritma standar untuk perkalian matriks, dialah yang pertama menjelaskan bahwa [[eliminasi]] Gauss adalah tidak [[optimal]]. Dalam tulisannya, dia memulai penelitian untuk melengkapi algoritma-algoritma yang lebih cepat seperti [[algoritme Winograd]] dari [[Shmuel Winograd]] pada [[1980]], dan yang lebih kompleks [[algoritme Coppersmith-Winograd]] dipublikasikan pada [[1987]].

== Algoritma ==

Misalkan ''A'', ''B'' dua [[matriks persegi]] pada ring ''R''. Kita ingin menghitung produk matriks ''C'' sebagai

:<math>\mathbf{C} = \mathbf{A} \mathbf{B} \qquad \mathbf{A},\mathbf{B},\mathbf{C} \in R^{2^n \times 2^n}</math>

Jika matriks ''A'', ''B'' bukan bertipe 2n x 2n kita isi baris-baris dan kolom-kolom yang kosong dengan nol.

Kita partisi ''A'', ''B'' dan ''C'' kedalam [[matriks blok]] yang berukuran sama.
:<math>
\mathbf{A} =
\begin{bmatrix}
\mathbf{A}_{1,1} & \mathbf{A}_{1,2} \\
\mathbf{A}_{2,1} & \mathbf{A}_{2,2}
\end{bmatrix}
\mbox {, }
\mathbf{B} =
\begin{bmatrix}
\mathbf{B}_{1,1} & \mathbf{B}_{1,2} \\
\mathbf{B}_{2,1} & \mathbf{B}_{2,2}
\end{bmatrix}
\mbox {, }
\mathbf{C} =
\begin{bmatrix}
\mathbf{C}_{1,1} & \mathbf{C}_{1,2} \\
\mathbf{C}_{2,1} & \mathbf{C}_{2,2}
\end{bmatrix}
</math>

dengan

:<math>\mathbf{A}_{i,j}, \mathbf{B}_{i,j}, \mathbf{C}_{i,j} \in R^{2^{n-1} \times 2^{n-1}}</math>

lalu

:<math>\mathbf{C}_{1,1} = \mathbf{A}_{1,1} \mathbf{B}_{1,1} + \mathbf{A}_{1,2} \mathbf{B}_{2,1} </math>
:<math>\mathbf{C}_{1,2} = \mathbf{A}_{1,1} \mathbf{B}_{1,2} + \mathbf{A}_{1,2} \mathbf{B}_{2,2} </math>
:<math>\mathbf{C}_{2,1} = \mathbf{A}_{2,1} \mathbf{B}_{1,1} + \mathbf{A}_{2,2} \mathbf{B}_{2,1} </math>
:<math>\mathbf{C}_{2,2} = \mathbf{A}_{2,1} \mathbf{B}_{1,2} + \mathbf{A}_{2,2} \mathbf{B}_{2,2} </math>

Dengan konstruksi ini kita tidak mengurangi jumlah dari perkalian-perkalian. Kita masih memerlukan 8 perkalian-perkalian untuk menghitung matriks-matriks ''Ci,j'', dengan jumlah perkalian yang sama kita perlukan ketika menggunakan matriks perkalian standar.

Sekarang sampai pada bagian terpenting. Kita tetapkan matriks baru

:<math>\mathbf{M}_{1}:= (\mathbf{A}_{1,1} + \mathbf{A}_{2,2}) (\mathbf{B}_{1,1} + \mathbf{B}_{2,2})</math>
:<math>\mathbf{M}_{2}:= (\mathbf{A}_{2,1} + \mathbf{A}_{2,2}) \mathbf{B}_{1,1}</math>
:<math>\mathbf{M}_{3}:= \mathbf{A}_{1,1} (\mathbf{B}_{1,2} - \mathbf{B}_{2,2})</math>
:<math>\mathbf{M}_{4}:= \mathbf{A}_{2,2} (\mathbf{B}_{2,1} - \mathbf{B}_{1,1})</math>
:<math>\mathbf{M}_{5}:= (\mathbf{A}_{1,1} + \mathbf{A}_{1,2}) \mathbf{B}_{2,2}</math>
:<math>\mathbf{M}_{6}:= (\mathbf{A}_{2,1} - \mathbf{A}_{1,1}) (\mathbf{B}_{1,1} + \mathbf{B}_{1,2})</math>
:<math>\mathbf{M}_{7}:= (\mathbf{A}_{1,2} - \mathbf{A}_{2,2}) (\mathbf{B}_{2,1} + \mathbf{B}_{2,2})</math>

Yang kemudian digunakan untuk mengekspresikan ''C''i,j dalam bentuk ''M''k. Karena kita telah mendefenisikan ''M''k kita bisa mengeliminasi satu perkalian matriks dan mengurangi jumlah perkalian-perkalian menjadi 7 (satu perkalian matriks untuk tiap ''M''k) dan ekspresi ''C''i,j sebagai

:<math>\mathbf{C}_{1,1} = \mathbf{M}_{1} + \mathbf{M}_{4} - \mathbf{M}_{5} + \mathbf{M}_{7}</math>
:<math>\mathbf{C}_{1,2} = \mathbf{M}_{3} + \mathbf{M}_{5}</math>
:<math>\mathbf{C}_{2,1} = \mathbf{M}_{2} + \mathbf{M}_{4}</math>
:<math>\mathbf{C}_{2,2} = \mathbf{M}_{1} - \mathbf{M}_{2} + \mathbf{M}_{3} + \mathbf{M}_{6}</math>

Kita iterasikan bagian diatas ke-n kali proses sampai submatriks-submatriks menjadi angka-angka.

Algoritma Strassen pada penerapannya mengubah metode standar dari perkalian matriks agar submatriks-submatriks yang cukup kecil menjadi lebih efisien. Fakta-fakta agar algoritma Strassen lebih efisien bergantung pada implementasi khusus dan hardware.

== Analisi Numerik ==

Perkalian matriks standar melakukan
:<math>n^3 = n^{\log_{2}8}</math>
perkalian-perkalian dari elemen-elemen dalam ring ''R''. Kita anggap penjumlahan-penjumlahan diperlukan karena bergantung pada ''R'', yang bisa jauh lebih cepat daripada perkalian-perkalian dalam implementasi pada komputer terutama jika ukuran dari entri matriks melebihi ukuran kata dari mesin.

Dengan algoritma Strassen kita bisa mengurangi jumlah perkalian-perkalian
:<math>n^{\log_{2}7}\approx n^{2.807}</math>.

Pengurangan dalam jumlah perkalian bagaimanapun akan sampai saat pilihan dari sedikit pengurangan kestabilan numerik.

== Contoh program sederhana pada Matlab ==

function c = strass(a,b)
nmin = 2;
%misalkan matriks a dan b berukuran 2 x 2
[n,n] = size(a);
if n <= nmin;
c = a*b;
else
%entri matriks a dan b berukuran n x n; n=2^k; k=2,3,...
%misalkan entri matriks a dan b berukuran n=2^2 atau 4 x 4
a11=a(1:2,1:2); a12=a(1:2,3:4); a21=a(3:4,1:2); a22=a(3:4,3:4);
b11=b(1:2,1:2); b12=b(1:2,3:4); b21=b(3:4,1:2); b22=b(3:4,3:4);
p1 = (a11+a22)*(b11+b22);
p2 = (a21+a22)*b11;
p3 = a11*(b12-b22);
p4 = a22*(b21-b11);
p5 = (a11+a12)*b22;
p6 = (a21-a11)*(b11+b12);
p7 = (a12-a22)*(b21+b22);
c = [p1+p4-p5+p7 p3+p5; p2+p4 p1-p2+p3+p6];
end

Catatan: program diatas hanya untuk matriks berukuran 1x1, 2x2, 4x4. Untuk matriks yang berukuran lebih besar, masih diperlukan penyempurnaan. Agar programnya bisa berjalan.

== Referensi ==

* Strassen, Volker, ''Gaussian Elimination is not Optimal'', Numer. Math. 13, p. 354-356, 1969
* [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]]. ''[[Introduction to Algorithms]]'', Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 28: Section 28.2: Strassen's algorithm for matrix multiplication, pp. 735–741.

== Pranala luar ==
* (also includes formulas for fast [[matrix inversion]])

== Sumber dan atribusi ==

Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Algoritma+Strassen&oldid=28365219 Wikipedia bahasa Indonesia], revisi 28365219 (2025-11-07T03:40:57Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.

Algoritma Strassen - Riwayat revisi

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

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