Catatan Kuliah: Algoritma Strassen untuk Perkalian Matriks

Pendahuluan

• Pembahasan mengenai algoritma Strassen untuk perkalian matriks persegi (N x N).
• Terdapat file Jupyter Notebook untuk ilustrasi dan problem set di Google Drive.

Ide Besar Algoritma Strassen

• Digunakan untuk perkalian matriks persegi, terutama dengan ukuran yang merupakan pangkat dua (2, 4, 8, ...).
• Matriks A dan B dibagi menjadi 4 blok yang lebih kecil, masing-masing berukuran N/2 x N/2.

Pembagian Blok Matriks

• Jika A adalah matriks 4x4, maka dibagi menjadi:
  • A11, A12, A21, A22
• Hasil perkalian C juga dituliskan dalam blok:
  • C11, C12, C21, C22

Rumus Perkalian Strassen

• Strassen menggunakan 7 rumus untuk mengalikan matriks:
  1. M1 = (A11 + A12) * B22
  2. M2 = (A21 + A22) * B11
  3. M3 = A11 * (B12 - B22)
  4. M4 = A22 * (B21 - B11)
  5. M5 = (A11 + A12) * B22
  6. M6 = (A21 - A11) * (B11 + B12)
  7. M7 = (A12 - A22) * (B21 + B22)
• C dihitung menggunakan kombinasi dari M1 hingga M7.*

Kasus Ukuran Matriks Tidak Standar

• Jika N tidak sama dengan 2^k, tambahkan baris/kolom 0 (padding) untuk membuat ukuran menjadi genap.

Implementasi Algoritma Strassen

• Fungsi partisi blok untuk mendapatkan blok dari matriks.
• Rekursif memanggil fungsi Strassen untuk setiap perkalian.
• Padding menggunakan numpy.pad untuk memperbaiki dimensi matriks.

Kompleksitas Waktu Algoritma Strassen

• Jika T(n) adalah banyaknya operasi penjumlahan dan perkalian, maka:
  • T(n) = 7T(n/2) + O(n^2)
• Solusi kompleksitas waktu adalah O(n^2.807), lebih baik dibandingkan algoritma standar O(n^3).

Perbandingan Waktu Eksekusi

• Algoritma Strassen lebih efisien untuk N besar, tetapi kurang optimal untuk N kecil dibandingkan algoritma standar.
• Contoh waktu eksekusi:
  • Matriks 4x4: 1.54 ms.

Kesimpulan

• Algoritma Strassen memberikan efisiensi lebih untuk perkalian matriks besar,
• Penting untuk memahami penerapan dan kompleksitas algoritma ini.