Yazan : Şadi Evren ŞEKER

Bu yazının amacı, parçala fethet yaklaşımı (divide and conquere) kullanarak matris çarpımı işlemini gerçekleştirmektir. Bu uygulamada JAVA dili kullanılacaktır.

Öncelikle matris çarpımını hatırlayalım. 2×2 boyutlarında A ve B matrislerinin çarpılıp C matrisine yerleştirilmesi aşağıdaki şekilde gösterilmiştir:

Bu çarpma işleminde, lise matematiğinden hatırlanacağı üzere her elemanın değeri için o satır ve sütun değerleri çarpılır. Örneğin C1,2 elemanını bulmak için A matrisindeki 1. satıra ve B matrisindeki 2. sütuna ihtiyaç vardır. Bu değerleri aşağıdaki şekilde yazabiliriz:

Yukarıda görüldüğü üzere, 2×2 büyüklüğündeki iki kare matrisin çarpımında, sonuç matrisini bulurken, her değer için belirli bir satır ve sütuna ihtiyaç duyulur. Örneğin C11 hesaplanırken, A matrisinin ikinci satırına veya B matrisinin 2. sütununa ihtiyaç duyulmaz.

Yukarıdaki bu durumu genelleyecek olursak aşağıdaki şekilde bir formül yazılabilir :

Görüldüğü üzere, c matris değerleri hesaplanırken, c matrisinin hangi elemanı hesaplanıyorsa, o elemanın indis değerine sahip A matrisindeki satır ve B matrisindeki sütun gerekmektedir ve işlem sadece bu değerler üzerinde uygulanır.

Bu bilgiyi kullanarak, problemi alt parçalara bölebiliriz. Örneğin C11 değeri bir bilgisayarda hesaplanırken, C22 değeri farklı bir bilgisayarda bağımsız olarak hesaplanabilir.

Örneğimizde birden fazla bilgisayara bölmek gibi bir işlem yapmayacağız. Bu işlemi yapan MPI dilinde yazılmış ve daha önceden bilgisayar kavramları sitesinde yayınlanmış örneği bu bağlantıdan okuyabilirsiniz.

Bizim örneğimizde problemi JAVA dilinde kodlayıp farklı nesnelere bölen kod yazma amacı bulunuyor. Bu kodu daha sonra farklı ipliklere (thread) veya farklı bilgisayarlara bölmek elbette mümkündür.

Öncelikle yukarıdaki matris çarpımını, parçala fethet yaklaşımı kullanmadan nasıl yapacağımızı kodlayalım.

void MatrixCarpim(
final double[][] a,
final double[][] b,
final double[][] c) {
final int m = a.length;
final int n = b.length;
final int p = b[0].length;
for (int j = 0; j < p; j++) {
       for (int i = 0; i < m; i++) {
           for (int k = 0; k < n; k++) {
               c[i][j] += a[i][k] * b[k][j];
           }
       }
    }
}

Yukarıdaki kodda görüldüğü üzere, iç içe 3 döngü ile matris çarpımı yapılabilir. Bu kodda amaç i ve j döngüleri için matrisi dolaşmak, k döngüsü içinde, o anda bulunulan i ve j indislerindeki değeri hesaplamaktır.

Diğer bir deyişle, yazının başında yazdığımız aşağıdaki formül, koda dökülmüştür:

Burada bulunan i ve j değerleri dıştaki iki döngüde dönülürken, k döngüsü içteki döngüyü oluşturur.

Sıra geldi bu kodu, parçala fethet yaklaşımına göre düzenlemeye.

Öncelikle, verilen bir satır ve sütunu çarpan ve sonuçta tek bir sayı döndüren fonksiyonu yazalım. Ardından, büyük matrisi parçalara bölüp bu fonksiyona yollayan tek bir döngü yeterli olacaktır.

double satirSutunCarpim(double a[][],double b[][],i,j)(
final int m = a.length;
final int n = b.length;
final int p = b[0].length;
double s = 0;
           for (int k = 0; k < n; k++) {
               s+= a[i][k] * b[k][j];
           }
return s;
}

Yukarıdaki bu fonksiyonu kullanarak, büyük matrisi parçalara bölebilir ve bu fonksiyonda çalıştırabiliriz. O halde MatrixCarpim fonksiyonumuz aşağıdaki şekilde olacaktır:

void MatrixCarpim(
final double[][] a,
final double[][] b,
final double[][] c)
{
final int m = a.length;
final int n = b.length;
final int p = b[0].length;
for (int j = 0; j < p; j++) {
       for (int i = 0; i < m; i++) {
               c[i][j] = satirSutunCarpim(a , b,i,j);
       }
    }
}

Görüldüğü üzere, yukarıdaki yeni MatrixCarpim fonksiyonumuz, problemi satirSutunCarpim fonksiyonuna göndererek çözmektedir. Şayet satirSutunCarpim fonksiyonu, farklı bilgisayarlarda veya en azından farklı ipliklerde (thread) değilse, yukarıdaki bölme ve çalıştırma işlemi, hiçbir avantaj sağlamadığı gibi yavaşlamalara sebep olabilir. Kısacası yukarıdaki parçala fethet (divide and concquere) yaklaşımının anlamlı olması için, müşterek programlama (concurrent programming) olan bir ortam gerekir. Örneğin yukarıdaki satirSutunCarpim fonksiyonu bir thread içerisine yerleştirilirse, daha anlamlı olabilir.

Ancak yukarıdaki kodları, farklı bilgisayar veya thread’lere bölmek için başlangıç kodu olarak kullanabilirsiniz.

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir