Algoritma Strassen: Perbedaan antara revisi
Image suggestions feature: 1 image added. |
|||
(7 revisi perantara oleh 5 pengguna tidak ditampilkan) | |||
Baris 1: | Baris 1: | ||
''' |
'''Algoritme Strassen''' dalam [[matematika]], khususnya [[aljabar]] [[linear]] adalah sebuah algoritme yang dinamakan oleh [[Volker Strassen]] yang merupakan sebuah algoritme yang digunakan untuk perkalian [[matriks]] yang secara [[asimtot]] lebih cepat daripada algoritme perkalian matriks standar dan sangat berguna dalam penggunaanya untuk matriks yang berukuran besar. |
||
== Sejarah == |
== Sejarah == |
||
Volker Strassen mempublikasikan |
Volker Strassen mempublikasikan algoritme Strassen tahun [[1969]]. Meskipun algoritme ini hanya sedikit lebih cepat daripada algoritme standar untuk perkalian matriks, dialah yang pertama menjelaskan bahwa [[eliminasi]] Gauss adalah tidak [[optimal]]. Dalam tulisannya, dia memulai penelitian untuk melengkapi algoritme-algoritme yang lebih cepat seperti [[algoritme Winograd]] dari [[Shmuel Winograd]] pada [[1980]], dan yang lebih kompleks [[algoritme Coppersmith-Winograd]] dipublikasikan pada [[1987]]. |
||
== Algoritma == |
|||
== Algoritme == |
|||
[[Berkas:Strassen-scheme.png|jmpl|ilustrasi dari algoritmastrassen]] |
|||
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 19: | Baris 19: | ||
\mathbf{A}_{2,1} & \mathbf{A}_{2,2} |
\mathbf{A}_{2,1} & \mathbf{A}_{2,2} |
||
\end{bmatrix} |
\end{bmatrix} |
||
\mbox { |
\mbox {, } |
||
\mathbf{B} = |
\mathbf{B} = |
||
\begin{bmatrix} |
\begin{bmatrix} |
||
Baris 25: | Baris 25: | ||
\mathbf{B}_{2,1} & \mathbf{B}_{2,2} |
\mathbf{B}_{2,1} & \mathbf{B}_{2,2} |
||
\end{bmatrix} |
\end{bmatrix} |
||
\mbox { |
\mbox {, } |
||
\mathbf{C} = |
\mathbf{C} = |
||
\begin{bmatrix} |
\begin{bmatrix} |
||
Baris 44: | Baris 44: | ||
:<math>\mathbf{C}_{2,2} = \mathbf{A}_{2,1} \mathbf{B}_{1,2} + \mathbf{A}_{2,2} \mathbf{B}_{2,2} </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 ''C<sub>i,j</sub>'' |
Dengan konstruksi ini kita tidak mengurangi jumlah dari perkalian-perkalian. Kita masih memerlukan 8 perkalian-perkalian untuk menghitung matriks-matriks ''C<sub>i,j</sub>'', dengan jumlah perkalian yang sama kita perlukan ketika menggunakan matriks perkalian standar. |
||
Sekarang sampai pada bagian terpenting. Kita tetapkan matriks baru |
Sekarang sampai pada bagian terpenting. Kita tetapkan matriks baru |
||
:<math>\mathbf{M}_{1} |
:<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} |
:<math>\mathbf{M}_{2}:= (\mathbf{A}_{2,1} + \mathbf{A}_{2,2}) \mathbf{B}_{1,1}</math> |
||
:<math>\mathbf{M}_{3} |
:<math>\mathbf{M}_{3}:= \mathbf{A}_{1,1} (\mathbf{B}_{1,2} - \mathbf{B}_{2,2})</math> |
||
:<math>\mathbf{M}_{4} |
:<math>\mathbf{M}_{4}:= \mathbf{A}_{2,2} (\mathbf{B}_{2,1} - \mathbf{B}_{1,1})</math> |
||
:<math>\mathbf{M}_{5} |
:<math>\mathbf{M}_{5}:= (\mathbf{A}_{1,1} + \mathbf{A}_{1,2}) \mathbf{B}_{2,2}</math> |
||
:<math>\mathbf{M}_{6} |
:<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} |
:<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''<sub>i,j</sub> dalam bentuk ''M''<sub>k</sub>. Karena kita telah mendefenisikan ''M''<sub>k</sub> kita bisa mengeliminasi satu perkalian matriks dan mengurangi jumlah perkalian-perkalian menjadi 7 (satu perkalian matriks untuk tiap ''M''<sub>k</sub>) dan ekspresi ''C''<sub>i,j</sub> sebagai |
Yang kemudian digunakan untuk mengekspresikan ''C''<sub>i,j</sub> dalam bentuk ''M''<sub>k</sub>. Karena kita telah mendefenisikan ''M''<sub>k</sub> kita bisa mengeliminasi satu perkalian matriks dan mengurangi jumlah perkalian-perkalian menjadi 7 (satu perkalian matriks untuk tiap ''M''<sub>k</sub>) dan ekspresi ''C''<sub>i,j</sub> sebagai |
||
Baris 65: | Baris 65: | ||
Kita iterasikan bagian diatas ke-n kali proses sampai submatriks-submatriks menjadi angka-angka. |
Kita iterasikan bagian diatas ke-n kali proses sampai submatriks-submatriks menjadi angka-angka. |
||
Algoritme Strassen pada penerapannya mengubah metode standar dari perkalian matriks agar submatriks-submatriks yang cukup kecil menjadi lebih efisien. Fakta-fakta agar algoritme Strassen lebih efisien bergantung pada implementasi khusus dan hardware. |
|||
== Analisi Numerik == |
== Analisi Numerik == |
||
Baris 73: | Baris 73: | ||
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. |
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 |
Dengan algoritme Strassen kita bisa mengurangi jumlah perkalian-perkalian |
||
:<math>n^{\log_{2}7}\approx n^{2.807}</math>. |
:<math>n^{\log_{2}7}\approx n^{2.807}</math>. |
||
Baris 105: | Baris 105: | ||
== Referensi == |
== Referensi == |
||
{{reflist}} |
{{reflist}} |
||
* Strassen, Volker, ''Gaussian Elimination is not Optimal'', Numer. Math. 13, p. |
* 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. |
* [[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 == |
||
* {{MathWorld|urlname=StrassenFormulas|title=Strassen's Formulas}} (also includes formulas for fast [[matrix inversion]]) |
* {{MathWorld|urlname=StrassenFormulas|title=Strassen's Formulas}} (also includes formulas for fast [[matrix inversion]]) |
||
{{Authority control}} |
|||
[[Kategori:Matematika]] |
[[Kategori:Matematika]] |
Revisi terkini sejak 5 Agustus 2024 07.45
Algoritme Strassen dalam matematika, khususnya aljabar linear adalah sebuah algoritme yang dinamakan oleh Volker Strassen yang merupakan sebuah algoritme yang digunakan untuk perkalian matriks yang secara asimtot lebih cepat daripada algoritme perkalian matriks standar dan sangat berguna dalam penggunaanya untuk matriks yang berukuran besar.
Sejarah
[sunting | sunting sumber]Volker Strassen mempublikasikan algoritme Strassen tahun 1969. Meskipun algoritme ini hanya sedikit lebih cepat daripada algoritme standar untuk perkalian matriks, dialah yang pertama menjelaskan bahwa eliminasi Gauss adalah tidak optimal. Dalam tulisannya, dia memulai penelitian untuk melengkapi algoritme-algoritme yang lebih cepat seperti algoritme Winograd dari Shmuel Winograd pada 1980, dan yang lebih kompleks algoritme Coppersmith-Winograd dipublikasikan pada 1987.
Algoritme
[sunting | sunting sumber]![](http://upload.wikimedia.org/wikipedia/commons/thumb/6/6a/Strassen-scheme.png/220px-Strassen-scheme.png)
Misalkan A, B dua matriks persegi pada ring R. Kita ingin menghitung produk matriks C sebagai
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.
dengan
lalu
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
Yang kemudian digunakan untuk mengekspresikan Ci,j dalam bentuk Mk. Karena kita telah mendefenisikan Mk kita bisa mengeliminasi satu perkalian matriks dan mengurangi jumlah perkalian-perkalian menjadi 7 (satu perkalian matriks untuk tiap Mk) dan ekspresi Ci,j sebagai
Kita iterasikan bagian diatas ke-n kali proses sampai submatriks-submatriks menjadi angka-angka.
Algoritme Strassen pada penerapannya mengubah metode standar dari perkalian matriks agar submatriks-submatriks yang cukup kecil menjadi lebih efisien. Fakta-fakta agar algoritme Strassen lebih efisien bergantung pada implementasi khusus dan hardware.
Analisi Numerik
[sunting | sunting sumber]Perkalian matriks standar melakukan
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 algoritme Strassen kita bisa mengurangi jumlah perkalian-perkalian
- .
Pengurangan dalam jumlah perkalian bagaimanapun akan sampai saat pilihan dari sedikit pengurangan kestabilan numerik.
Contoh program sederhana pada Matlab
[sunting | sunting sumber]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
[sunting | sunting sumber]- 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
[sunting | sunting sumber]- (Inggris) Weisstein, Eric W. "Strassen's Formulas". MathWorld. (also includes formulas for fast matrix inversion)