Algoritma Strassen

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

C = A B A , B , C ∈ R 2 n × 2 n {\displaystyle \mathbf {C} =\mathbf {A} \mathbf {B} \qquad \mathbf {A} ,\mathbf {B} ,\mathbf {C} \in R^{2^{n}\times 2^{n}}}

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

Kita partisi A, B dan C kedalam matriks blok yang berukuran sama.

A = [ A 1 , 1 A 1 , 2 A 2 , 1 A 2 , 2 ] ,  B = [ B 1 , 1 B 1 , 2 B 2 , 1 B 2 , 2 ] ,  C = [ C 1 , 1 C 1 , 2 C 2 , 1 C 2 , 2 ] {\displaystyle \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}}}

dengan

A i , j , B i , j , C i , j ∈ R 2 n − 1 × 2 n − 1 {\displaystyle \mathbf {A} _{i,j},\mathbf {B} _{i,j},\mathbf {C} _{i,j}\in R^{2^{n-1}\times 2^{n-1}}}

lalu

C 1 , 1 = A 1 , 1 B 1 , 1 + A 1 , 2 B 2 , 1 {\displaystyle \mathbf {C} _{1,1}=\mathbf {A} _{1,1}\mathbf {B} _{1,1}+\mathbf {A} _{1,2}\mathbf {B} _{2,1}}

C 1 , 2 = A 1 , 1 B 1 , 2 + A 1 , 2 B 2 , 2 {\displaystyle \mathbf {C} _{1,2}=\mathbf {A} _{1,1}\mathbf {B} _{1,2}+\mathbf {A} _{1,2}\mathbf {B} _{2,2}}

C 2 , 1 = A 2 , 1 B 1 , 1 + A 2 , 2 B 2 , 1 {\displaystyle \mathbf {C} _{2,1}=\mathbf {A} _{2,1}\mathbf {B} _{1,1}+\mathbf {A} _{2,2}\mathbf {B} _{2,1}}

C 2 , 2 = A 2 , 1 B 1 , 2 + A 2 , 2 B 2 , 2 {\displaystyle \mathbf {C} _{2,2}=\mathbf {A} _{2,1}\mathbf {B} _{1,2}+\mathbf {A} _{2,2}\mathbf {B} _{2,2}}

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

Sekarang sampai pada bagian terpenting. Kita tetapkan matriks baru

M 1 := ( A 1 , 1 + A 2 , 2 ) ( B 1 , 1 + B 2 , 2 ) {\displaystyle \mathbf {M} _{1}:=(\mathbf {A} _{1,1}+\mathbf {A} _{2,2})(\mathbf {B} _{1,1}+\mathbf {B} _{2,2})}

M 2 := ( A 2 , 1 + A 2 , 2 ) B 1 , 1 {\displaystyle \mathbf {M} _{2}:=(\mathbf {A} _{2,1}+\mathbf {A} _{2,2})\mathbf {B} _{1,1}}

M 3 := A 1 , 1 ( B 1 , 2 − B 2 , 2 ) {\displaystyle \mathbf {M} _{3}:=\mathbf {A} _{1,1}(\mathbf {B} _{1,2}-\mathbf {B} _{2,2})}

M 4 := A 2 , 2 ( B 2 , 1 − B 1 , 1 ) {\displaystyle \mathbf {M} _{4}:=\mathbf {A} _{2,2}(\mathbf {B} _{2,1}-\mathbf {B} _{1,1})}

M 5 := ( A 1 , 1 + A 1 , 2 ) B 2 , 2 {\displaystyle \mathbf {M} _{5}:=(\mathbf {A} _{1,1}+\mathbf {A} _{1,2})\mathbf {B} _{2,2}}

M 6 := ( A 2 , 1 − A 1 , 1 ) ( B 1 , 1 + B 1 , 2 ) {\displaystyle \mathbf {M} _{6}:=(\mathbf {A} _{2,1}-\mathbf {A} _{1,1})(\mathbf {B} _{1,1}+\mathbf {B} _{1,2})}

M 7 := ( A 1 , 2 − A 2 , 2 ) ( B 2 , 1 + B 2 , 2 ) {\displaystyle \mathbf {M} _{7}:=(\mathbf {A} _{1,2}-\mathbf {A} _{2,2})(\mathbf {B} _{2,1}+\mathbf {B} _{2,2})}

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

C 1 , 1 = M 1 + M 4 − M 5 + M 7 {\displaystyle \mathbf {C} _{1,1}=\mathbf {M} _{1}+\mathbf {M} _{4}-\mathbf {M} _{5}+\mathbf {M} _{7}}

C 1 , 2 = M 3 + M 5 {\displaystyle \mathbf {C} _{1,2}=\mathbf {M} _{3}+\mathbf {M} _{5}}

C 2 , 1 = M 2 + M 4 {\displaystyle \mathbf {C} _{2,1}=\mathbf {M} _{2}+\mathbf {M} _{4}}

C 2 , 2 = M 1 − M 2 + M 3 + M 6 {\displaystyle \mathbf {C} _{2,2}=\mathbf {M} _{1}-\mathbf {M} _{2}+\mathbf {M} _{3}+\mathbf {M} _{6}}

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

n 3 = n log 2 ⁡ 8 {\displaystyle n^{3}=n^{\log _{2}8}}

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

n log 2 ⁡ 7 ≈ n 2.807 {\displaystyle n^{\log _{2}7}\approx n^{2.807}} .

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

• (Inggris)Weisstein, Eric W. "Strassen's Formulas". MathWorld. (also includes formulas for fast matrix inversion)