Matrix Chain Multiplication

Perkalian matriks berantai (Matrix Chain Multiplication), sesuai dengan namanya, adalah perkalian dari serangkaian matriks. Operasi perkalian matriks adalah operasi yang bersifat asosiatif, yaitu urutan operasi yang dilakukan dapat diubah-ubah dengan bebas dan tetap tidak akan berpengaruh pada hasil akhir operasi.

Jika kita melakukan perkalian antara dua buah matrix, syarat yang harus dipenuhi adalah banyaknya jumlah kolom pada matrix pertama harus sama dengan jumlah baris matrix yang kedua. Yang harus dicari jalan keluarnya dalam hal ini adalah jika kita mengalikan matriks-matriks tersebut sesuai urutannya, proses yang dilakukan sering kali tidak efektif dan memakan waktu lama. Ini dikarenakan oleh banyaknya operasi perkalian integer yang dilakukan. Misalnya diberikan 2 buah matriks :


A(2x4)
B(4x5)

Jumlah perkalian (usaha) yang diperlukan untuk mendapatkan hasil perkalian dari matriks tersebut adalah :

2x4x5 = 40 perkalian.

Ternyata pilihan urutan perkalian matriks yang berbeda akan membutuhkan jumlah perkalian (usaha) yang berbeda pula. Sehingga dengan memilih urutan perkalian matriks yang tepat, kita bisa menyelesaikan perkalian matriks berantai tersebut dengan lebih cepat dan efisien. Karena dengan memilih urutan perkalian yang tepat, kita dapat mereduksi jumlah perkalian yang harus dilakukan untuk mendapatkan solusi akhir dari perkalian matriks berantai tersebut.

Dengan menggunakan metode Matrix Chain Multiplication ini, kita dapat menyelesaikan permasalahan Bagaimana kita mendapatkan rantai perkalian pada beberapa matrix yang akan menghasilkan biaya komputasi yang paling optimum. MCM ini dapat dikerjakan dengan 3 cara yaitu iterative (bottom up), memorized, dan rekursif (top down).














Table of scalar multiplications.









table generated by applet.