Reevaluating spectral partitioning for unsymmetric matrices

Grafik temsiline sahip bilimsel problemlerin paralel çözümleri, verimli görev ve veri bölümleme gerektirir. Bu tezde, çeşitli paralel grafik bölümleme algoritmaları incelenmiştir. Bu algoritmalar hem yönlendirilmiş hem de yönsüz grafiklere uygulanabilir olsa da, bu çalışmada, matris gösterimleri seyrek ve simetrik olmayan, hesaplamalı akışkanlar dinamiği ve termal problemler gibi çeşitli uygulama alanlarını temsil eden doğrusal denklem sisteminde ortaya çıkan yönlendirilmiş duruma odaklanıyoruz. Bu çalışmada incelenen stratejiler, Çok Seviyeli Kernighan-Lin algoritmasına sahip ParMETIS, k-ortalamalı kümeleme algoritması ile birlikte kullanılan spektral bölümleme (SPEC), ve CHACO içerisinde kullanılan spektral bölümleme algoritmasıdır. PETSc ve SLEPc kitaplıkları kullanılarak C programlama dilinde SPEC algoritması uygulanmış olup, CHACO ve ParMETIS ise PETSc'den çağrılmaktadır. Grafiğin kenar ağırlıkları dikkate alınarak ağırlıklı bölümlendirme yapılır. Ağırlıklı bölümleme yapıldığında kitaplıkların sınırlamaları nedeniyle SPEC, kitaplıklarla yalnızca ağırlıksız bölümleme yapıldığında karşılaştırılır. Bu nedenle, ağırlıklı bölümleme için, sadece SLEPc'deki çeşitli özdeğer çözücü toleransları, kenar kesme ve bölümleme süresi açısından incelenir. Başka bir araştırma ise MATLAB içerisinde k-ortalamalı kümeleme algoritması tarafından kullanıldığında, özdeğer çözücü toleransına dayalı spektral bölümleme algoritması için yapılmıştır. Karşılaştırma, bölümlemenin kalitesine (kenar kesimi ve bölüm dengesizliği) ve yineleme sayısı cinsinden maliyete dayanmaktadır. Bir bölümlemenin kalitesi, uygulamaya bağlı olarak bölümlerin kenar ve tepe dengesizlik oranlarına bağlı olabilecek yük dengesizliğinin yanı sıra kesilen kenar sayısı ile belirlenir. Bir grafiğin bitişik matrisi yapısal olarak simetrik olduğundan, matris simetrik olmadığında özdeğer problemi ancak yaklaşık olarak çözülebilir. Bu nedenle, bu çalışmada yalnızca yaklaşık sonuçlar verilmiştir. Simetrik olmayan matrislerin ağırlıksız bölümlemesinde kenar kesim sayısı karşılaştırıldığında, SPEC kullanımının mevcut yazılım kitaplıklarından daha iyi performans gösterdiği sonucuna varılmıştır.