Perkalian Matriks Secara Rekursi

Dalam kesempatan kali ini saya akan memberikan sedikit pencerahan tentang bagaimana mengalikan matriks secara rekursi.

Di dalam dunia pemrograman, rekursi didefenisikan sebagai pemecahan masalah dengan cara membaginya ke dalam sub bagian yang lebih kecil. Hal ini ditandai dengan adanya panggilan terhadap fungsi/method dari dalam method/fungsi itu sendiri.

Kali ini saya akan memberikan contoh bagaimana operasi perkalian matriks bisa dilakukan secara rekursi. Artinya ketimbang melakukan iterasi satu per satu terhadap semua elemen matriks untuk memperoleh hasil akhir. Maka dengan rekursi, kita melakukan perkalian secara simultan terhadap kelompok-kelompok elemen dari matriks tersebut.

Metodenya adalah dengan membagi matriks ke dalam 4 kuadran,  yang masing-masing bagian akan dibagi lagi menjadi 4 kuadran secara berkelanjutan, hingga dijumpai base case. Pada base case ini baru kemudian dilakukan perhitungan secara langsung. Base-case diperlukan dalam rekursi, karena jika tidak ada base-case, maka akan terjadi pemanggilan berulang-ulang tanpa henti yang berakibat alokasi berlebihan terhadap memori stack pada komputer. Dan ujung-ujungnya terjadi stack-overflow.

Prinsip kerjanya adalah, ketika matriks A dengan dimensi (m,n) dengan m menyatakan jumlah baris dan n jumlah kolom dikalikan dengan matriks B dengan dimensi (o,p), maka matriks hasil akan berdimensi (m,p). Jadi yang kita lakukan adalah menerapkan rekursi dalam pengisian elemen dari matriks hasil tadi (katakanlah matriks C).  Perhatikan potongan script berikut

	
public void multiply(int barisA, int kolomB) {
	int sum = 0;
	for (int k = 0; k < dimensiTengah; k++) {
		sum += matriksA[barisA][k] * matriksB[k][kolomB];
	}
	matriksC[barisA][kolomB] = sum;
}

Dalam potongan script di atas, kita melakukan pengisian elemen ke (i,j) pada matriks C dengan mengalikan elemen pada baris ke-i matriks A dengan kolom ke-j matriks B lantas menjumlahkannya. Di sini kuncinya! Jadi dengan melakukan rekursi terhadap baris dan kolom matriks C  maka kita tidak perlu lagi pusing memikirkan bagaimana mengkondisikan elemen matriks B dan elemen dari matriks A untuk keperluan perkalian matriks secara rekursi. Yang perlu kita pikirkan hanya proses pengisian elemen dari matriks C tadi.

Kita akan melakukan proses pengisian tersebut dengan membagi matriks C ke dalam 4 kuadran secara rekursi sampai diperoleh base case. Base case dijumpai ketika jumlah baris serta jumlah kolom dari sub matriks C---matriks yang diperoleh dari pemecahan matriks C ke dalam 4 kuadran tadi (walaupun hakikatnya dalam memori hanya matriks C juga)---telah melampaui ambang tertentu. Perhatikan potongan script berikut.

public void compute() {
		
		int limit = 10;
		
		int limitKolom = (int) (Math.floor( ((awalKolom  - akhirKolom) / 2)));
		
		int limitBaris = (int) (Math.floor( ((akhirBaris - awalBaris) / 2)));
		
		int halfBaris = awalBaris + limitBaris; 

		int halfKolom = awalKolom + limitKolom;
		

		if (limitKolom <= limit && limitBaris <= limit) {

			computeDirectly(awalBaris, akhirBaris, awalKolom, akhirKolom);

			return;

		} else if (limitBaris <= limit && limitKolom > limit) { // split over column

			RecursiveMatrixMultiplication p2 = new RecursiveMatrixMultiplication(matriksA, matriksB,
					matriksC, dimensiTengah, awalBaris, akhirBaris, awalKolom,
					halfKolom);

			RecursiveMatrixMultiplication p4 = new RecursiveMatrixMultiplication(matriksA, matriksB,
					matriksC, dimensiTengah, awalBaris, akhirBaris, halfKolom,		
					akhirKolom);
			
			invokeAll(p2, p4);

		} else if (limitKolom <= limit && limitBaris > limit) { // split over
																// row 
			
			RecursiveMatrixMultiplication p1 = new RecursiveMatrixMultiplication(
					matriksA, matriksB,matriksC, 
					dimensiTengah,
					awalBaris, halfBaris, 
					awalKolom, akhirKolom);

			RecursiveMatrixMultiplication p3 = new RecursiveMatrixMultiplication(
					matriksA, matriksB, matriksC, 
					dimensiTengah, 
					halfBaris, akhirBaris,
					awalKolom, akhirKolom);

			invokeAll(p1, p3);

		} else if (limitKolom > limit && limitBaris > limit) { // split to 4 quadran

			RecursiveMatrixMultiplication p1 = new RecursiveMatrixMultiplication(
					matriksA, matriksB, matriksC, dimensiTengah,
					awalBaris, halfBaris,
					awalKolom, halfKolom); // kuadran 1

			RecursiveMatrixMultiplication p2 = new RecursiveMatrixMultiplication(
					matriksA, matriksB,matriksC, dimensiTengah, 
					halfBaris, akhirBaris,
					awalKolom, halfKolom); // kuadran 2

			RecursiveMatrixMultiplication p3 = new RecursiveMatrixMultiplication(
					matriksA, matriksB, matriksC , dimensiTengah,
					awalBaris, halfBaris,
					halfKolom, akhirKolom); // kuadran 3

			RecursiveMatrixMultiplication p4 = new RecursiveMatrixMultiplication(
					matriksA, matriksB, matriksC, dimensiTengah, 
					halfBaris, akhirBaris,
					halfKolom, akhirKolom); // kuadran 4

			invokeAll(p1, p2, p3, p4);
			
		}

	}

Dalam potongan di atas, ketika jumlah baris dari sub-matriks C dan jumlah kolomnya masih lebih besar dari ambang, maka bagi lagi secara rekursi menjadi sub-sub matriks berikutnya (dalam 4 kuadran). Ketika jumlah baris masih lebih besar dari ambang, bagi sub-matriks C ke dalam dua sub-matriks berikutnya dalam arah horizontal  (bagi baris-barisnya ke dalam dua bagian). Sementara jika jumlah kolomnya masih lebih besar dari ambang, maka bagi sub-matriks C dalam arah vertikal (bagi kolom-kolomnya menjadi dua bagian).

Ketika dijumpai base-case, yakni ketika jumlah kolom dan jumlah baris dari sub-sub-sub-sub… matrik C lebih kecil dari nilai ambang, maka lakukan perkalian elemen-elemen matriks A dan matriks B untuk mengisi elemen-elemen dari sub-sub-sub… matriks C tersebut.

Secara keseluruhan kode yang digunakan adalah sebagai berikut (di dalamnya terdapat juga method untuk mengecek kevalidan operasi yakni dengan membandingkannya dengan perkalian secara konvensional, tanpa rekursi).  

package algo.test.multiply;

import java.util.Random;

public class RecursiveMatrixMultiplication {

	int[][] matriksA;
	int[][] matriksB;
	int[][] matriksC;

	int awalBaris;
	int awalKolom;
	int akhirBaris;
	int akhirKolom;

	int dimensiTengah;

	public RecursiveMatrixMultiplication(int[][] matriksA, int[][] matriksB,
			int[][] matriksC, int dimensiTengah, int awalBaris, int akhirBaris,
			int awalKolom, int akhirKolom) {

		this.matriksA = matriksA;
		this.matriksB = matriksB;
		this.matriksC = matriksC;

		this.awalBaris = awalBaris;
		this.awalKolom = awalKolom;
		this.akhirBaris = akhirBaris;
		this.akhirKolom = akhirKolom;

		this.dimensiTengah = dimensiTengah;
	}
	
	public void multiply(int barisA, int kolomB) {
		int sum = 0;
		for (int k = 0; k < dimensiTengah; k++) {
			sum += matriksA[barisA][k] * matriksB[k][kolomB];
		}
		matriksC[barisA][kolomB] = sum;
	}
	
	
	private void computeDirectly(int awalBaris, int akhirBaris, int awalKolom,
			int akhirKolom) {
		for (int i = awalBaris; i < akhirBaris; i++) {
			for (int j = awalKolom; j < akhirKolom; j++) {
				multiply(i, j);
			}
		}
	}
	
	
	 public void invokeAll(RecursiveMatrixMultiplication...matrixMultiplications ){
		for(RecursiveMatrixMultiplication m: matrixMultiplications){
			m.compute();
		}
	}
	 
	 public void invoke(){
		 invokeAll(this); 
	 }
	
	public void compute() {
			
			int limit = 10;
			
			int limitKolom = (int) (Math.floor( ((awalKolom  - akhirKolom) / 2)));
			
			int limitBaris = (int) (Math.floor( ((akhirBaris - awalBaris) / 2)));
			
			int halfBaris = awalBaris + limitBaris; 

			int halfKolom = awalKolom + limitKolom;
			

			if (limitKolom <= limit && limitBaris <= limit) {

				computeDirectly(awalBaris, akhirBaris, awalKolom, akhirKolom);

				return;

			} else if (limitBaris <= limit && limitKolom > limit) { // split over column

				RecursiveMatrixMultiplication p2 = new RecursiveMatrixMultiplication(matriksA, matriksB,
						matriksC, dimensiTengah, awalBaris, akhirBaris, awalKolom,
						halfKolom);

				RecursiveMatrixMultiplication p4 = new RecursiveMatrixMultiplication(matriksA, matriksB,
						matriksC, dimensiTengah, awalBaris, akhirBaris, halfKolom,		
						akhirKolom);
				
				invokeAll(p2, p4);

			} else if (limitKolom <= limit && limitBaris > limit) { // split over
																	// row 
				
				RecursiveMatrixMultiplication p1 = new RecursiveMatrixMultiplication(
						matriksA, matriksB,matriksC, 
						dimensiTengah,
						awalBaris, halfBaris, 
						awalKolom, akhirKolom);

				RecursiveMatrixMultiplication p3 = new RecursiveMatrixMultiplication(
						matriksA, matriksB, matriksC, 
						dimensiTengah, 
						halfBaris, akhirBaris,
						awalKolom, akhirKolom);

				invokeAll(p1, p3);

			} else if (limitKolom > limit && limitBaris > limit) { // split to 4 quadran

				RecursiveMatrixMultiplication p1 = new RecursiveMatrixMultiplication(
						matriksA, matriksB, matriksC, dimensiTengah,
						awalBaris, halfBaris,
						awalKolom, halfKolom); // kuadran 1

				RecursiveMatrixMultiplication p2 = new RecursiveMatrixMultiplication(
						matriksA, matriksB,matriksC, dimensiTengah, 
						halfBaris, akhirBaris,
						awalKolom, halfKolom); // kuadran 2

				RecursiveMatrixMultiplication p3 = new RecursiveMatrixMultiplication(
						matriksA, matriksB, matriksC , dimensiTengah,
						awalBaris, halfBaris,
						halfKolom, akhirKolom); // kuadran 3

				RecursiveMatrixMultiplication p4 = new RecursiveMatrixMultiplication(
						matriksA, matriksB, matriksC, dimensiTengah, 
						halfBaris, akhirBaris,
						halfKolom, akhirKolom); // kuadran 4

				invokeAll(p1, p2, p3, p4);
				
			}

		}
	
	
	/*
	 * bandingkan matriksA dan matriksB.. 
	 * jika semua elemennya sama, maka kembalikan matriksC yang isinya semua 1... 
	 * jika ada elemen yang beda isi elemen matriksC dengan 0
	 */
	public static int [][] compareMatriks(int [][] matriksA, int[][] matriksB){
		int  C[][] = new int [matriksA.length][matriksA[0].length]; 
		for( int i=0; i < matriksA.length ;i++){
			for(int j=0; j < matriksA[0].length ;j++){
				if(matriksA[i][j] == matriksB[i][j]){
					C[i][j] = 1;
				}else{
					C[i][j] = 0; 
				}
			}
		}
		return C; 
	}
	
	
	/*
	 * sebagai pembanding untuk mengetahui operasi berjalan dengan benar.. 
	 * yakni lakukan perkalian secara Langsung..  tanpa rekursive... 
	 */
	public static int[][] multiplyDirectly(int [][] matriksA, int[][] matriksB){
		int result[][] = new int[matriksA.length][matriksB[0].length]; 
		for(int i= 0; i< matriksA.length ;i++){
			for(int j=0; j< matriksB[0].length ;j++){
				int sum  = 0; 
				for( int k = 0 ; k < matriksB.length ;k ++){
					sum += matriksA[i][k] * matriksB[k][j]; 
				}
				result[i][j] = sum; 
			}
		}
		return  result; 
	}
	
	/*
	 * generate random matriks
	 */
	public static int [][] generateMatriks(int baris, int kolom){
		int  matriks[][] = new int[baris][kolom]; 
		Random rn = new Random(); 
		for(int i=0; i < matriks.length ; i++){
			for( int j=0; j < matriks[0].length ;j++){
				matriks[i][j] = rn.nextInt(100); 
			}
		}
		return matriks ;
	}
	
	
	/*
	 *	pretty print matrix 
	 */
	public static void printMatriks(int [][] matriks) {
		for (int i = 0; i < matriks.length; i++) {
			for (int j = 0; j < matriks[0].length; j++) {
				System.out.print(matriks[i][j] + "|");
			}
			System.out.print("\n");
		}
		System.out.print("\n"); 
	}
	
	
	public int[][] getResult() {
		return matriksC;
	}

	
	public static void main(String[] args){
		
		
		int[][] matriksA = generateMatriks(300, 200); 
		int[][] matriksB = generateMatriks(200, 500); 
		
		long now = System.nanoTime(); 
		
		int[][] matriksResultA = multiplyDirectly(matriksA, matriksB); 
		
		now = (System.nanoTime() - now) / 1000000; 
		
		long  now1 = System.nanoTime(); 
		
		int[][] matriksC = new int[matriksA.length][matriksB[0].length];  
		
		RecursiveMatrixMultiplication parallel = new RecursiveMatrixMultiplication(matriksA, matriksB, matriksC, 
				matriksB.length, 0 , matriksC.length, 0, matriksC[0].length); 
		
		parallel.invoke();
		
		int[][] matriksResultB = parallel.getResult(); 
		
		now1 = (System.nanoTime() - now1) / 1000000; 
		
		int[][] hasilCompare  = compareMatriks(matriksResultA, matriksResultB);   
		
		printMatriks(hasilCompare);
		
		System.out.println(now); 
		System.out.println(now1);
		System.out.println("FINISH"); 
		
	}


}