Jelaskan Algoritme dari Algoritma Strassen

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 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.