Yazan : Şadi Evren ŞEKER
Bilgisayar bilimlerinde sıkça örnek olarak kullanıldığı için bu konudaki kavramları ve algoritmaların C dili karşılıklarını bu yazıda açıklamaya çalışacağım. Yazımıza öncelikle iç çarpım veya nokta çarpım olarak geçen çarpma işlemi ile başlayalım.
İç Çarpım (Dot Product/Inner Product)
Bu çarpma işlemini bir örnek ile anlamaya çalışalım.
=
Yukarıdaki örnekte görüldüğü üzere çarpma işlemi satır / sütün eşleşmesi gerektirir. Yani birinci matrisin ilk satır ile ikinci matrisin ilk sütunu vb. çarpılarak sonuç bulunur. Bu durumu aşağıdaki şekilde daha net görebiliriz:
Yukarıdaki şekilde görüldüğü üzere, çarpma işlemi için iki matrisi yukarıdaki gibi yerleştirip, sonuç matrisi olan matris için ilgili satır ve sütunların çarpımı olarak düşünebiliriz. Diğer bir deyişle, a sonucu için 1,2 ve 5,7 veya b sonucu için 1,2 ve 6,8 çarpımı gerekmektedir.
C dilinde kodlanması
for (int i = 1;i<=m ; i++){
for (int j = 1;i<=n ;j++){
for(int k = 1;k<=p;k++){
c[i][j] = a[i][k]*b[k][j] + c[i][j];
}
}
}
Yukarıdaki kodda görüldüğü üzere, 3 adet iç içe döngü (nested loop) kullanılmış ve bu döngülerden dıştaki iki tanesi, satır ve sütun takibi, içteki döngü ise toplama işlemi için kullanılmıştır.
Yukarıdaki bu çarpma işlemini C=AB+C olarak özetleyebiliriz ve burada görüldüğü üzere AB çarpımı, C matrisine eklenmektedir.
Yukarıdaki örnek için A ve B matrislerini çarpılarak sonucun C matrisinde biriktirildiğini ve C matrisinin ilk başta 0 dolu bir matris olduğunu kabul ediyoruz.
Elbette diğer bir kabul de matrislerin indisleri için yapılan kabuldür. Yani iki matrisin çarpılabilmesi için bir boyutlarının eşit olması gerekir. Örneğin 3×3’lük bir matris ile 4×4’lük bir matris çarpılamaz. Ancak 4×3’lük bir matris ile 3×5’lik bir matris veya 7×4’lük bir matris çarpılabilir. Bu durumda yukarıdaki kodda bulunan m ve n boyutları olarak gösterilmiştir. Örneğin 4×3’lük bir matris ile 3×5’lik bir matris çarpılıyorsa, m: 4, n:5 ve p:3 olacaktır.
Saxpy (Scalar a x plus y) Çarpım yöntemi
Bu yöntemin amacı, iki matrisin çarpımını bir matris ile bir sabitin (scalar) çarpımı ve bu çarpımların toplamı haline indirgemektir.
Sonuç matrisi olan C matrisi ile çarpanlardan birisi olan A matrisini bire bir eleman dizilimini elde etmek için ayrıştırırsak :
A=[a
,…….a
] ve
C=[c
……..c
]
Şeklinde yazabiliriz. Buradaki çarpma işlemi için bir önceki örnekte
C=AB+C
Yazdığımızı hatırlarsak, bu işlemi saxpy yönteminde aşağıdaki şekilde yazmak mümkündür:
c
=
, j=1:n
Bu durumu örnek üzerinden gösterecek olursak
=
Yukarıda görüldüğü üzere, sonuç matrisinin iki kolonu (ki aralarında virgül işareti bulunmaktadır) ayrı ayrı matrislerin sabit ile çarpımlarının toplamı olarak düşünülebilir.
C dilinde SAXPY
for(int j = 1;j<=n;j++){
for(int k = 1;k<p;k++){
X[j] = matrisTopla( skalarCarp(A[k],B[k][j]),X[j]);
}
}
for(int j = 1;j<=n;j++){
C[j] = X[k]+C[j];
}
Yukarıdaki algoritmada, ilk iki döngü ile gösterilen kod, önce A matrisinin k kolonu ile B matrisinin k,j elemanını skalar çarpıma tabi tutmakta, ardından da Bu sonucu X ara matrisinin j. elemanı üzerine biriktirmektedir. Buradaki X ara matrisini yukarıdaki matematiksel gösterimde bulunan sonuç matrisinin ayrı ayrı kolonları olarak düşünmek mümkündür. İkinci döngü ise bu kolonları 2 boyutlu tek bir sonuç matrisi olan C matrisinde toplamaktadır.
Dış Çarpım (Outer Product) Yöntemi
Bu yöntem, satır ve sütunların çarpımı işlemini tek boyutlu matrislerin çarpımı haline indirgemektedir. Örneğin aşağıdaki iki boyutlu iki matrisin çarpımını ele alalım:
=
[5 6]+ 
[7 8]
Bu iki boyutlu matrislerin çarpımını, tek boyutlu matrislerin çarpımının toplamı olarak yukarıda gösterildiği gibi yazmak mümkündür.
C dilinde dış çarpım
for (int i = 1;i<=p;i++){
C = matrisTopla(matrisÇarp(a[][k],b[k][]));
}
Sonuç
Yukarıda, matematikte (veya matematiğin bir alt kolu olan doğrusal cebirde (linear algebra) ) geçen üç farklı yolla matris çarpımını gördük. Bu yolların tamamı, aslında bilgisayar bilimleri için tektir. Bütün bu yolların karmaşıklığı da aynıdır ve üç adet iç içe döngü demektir. Diğer bir deyişle O(n3) olarak düşünülebilir. Bunun sebebi aslında yukarıdaki ilk yöntemden sonra gösterilen saxpy ve dış çarpım yöntemlerinin, ilk gösterdiğimiz çarpım yöntemine göre ara adımlar alınmış olmasıdır.
Sonuçta ikinci ve üçüncü yöntemlerde de fonksiyon içleri kodlandığında en basit algoritmamız olan aşağıdaki hale dönüşürler:
for (int i = 1;i<=m ; i++){
for (int j = 1;i<=n ;j++){
for(int k = 1;k<=p;k++){
c[i][j] = a[i][k]*b[k][j] + c[i][j];
}
}
}