Combinatorial reductions between graph partitioning by vertex separator and hypergraph partitioning problems for parallel and scientific computing applications

Hiperçizge Bölümleme (HB) ve Düğüm Ayıracı ile Çizge Bölümleme (DACB) problemleriliteratürde gayet bilinen, koşut ve bilimsel hesaplamalarda etkin biçimde kullanılan problemlerdir. Koşut hesaplamalarda tipik bir problem, verilerin ve görevlerin değişik sayıda işlemciye öyle şekilde dağıtılmasıdır ki hesaplamanın çalışma performansı zaman ve yer gereksinimleri açısından hızlı ve verimli olsun. Bunun yanında, DACB problemi seyrek doğrusal sistemlerin verimli çözülebilmesi için doluluk azaltan sıralama yapmak için etkin biçimde kullanılmaktadır. Bu da bilimsel hesaplamanın konu sahası içine girmektedir. Bu tez çalışmasında, HB ve DACB problemleri arasındaki ilişki incelenmektedir. Bu bağlamda, iki kombinatoriyal dönüştürüm açığa çıkarılmıştır. Birinci dönüştürme, HB probleminden DACB problemine, ikincisi ise DACB probleminden HB probleminedir. HB probleminden DACB problemine dönüştürmede girdi dönüşümü kolay olmamaktadır. Girdi dönüşümünden kasıt, verilen bir çizgeyi, problem dönüştürümü uygun olacak şekilde bir hiğerçizgeye dönüştürmektir. DACB probleminden HB problemine dönüştürümde ise çıktı dönüşümü kolay olmamaktadır. Burada da kasıt, verilen bir çizge bölümlemeyi asıl problemimiz olan hiperçizge bölümlemeye dönüştürmektir. Bu kısımda önemli ve faydalı imkansizlık sonuçları türetilmiştir. Bu kolay olmayan kısımlar derinliğince incelenmiş, etkili ve verimli çözümler ve yöntemler önerilmiştir.Bu çalışma çerçevesinde, bir HB tabanlı doluluk azaltan sıralama aracı olan oPaToH, gelişmiş girdi dönüşümleri ile genişletilmiştir. Bunun yanında, başka bir doluluk azaltan sıralama aracı olan onmetıs kullanılarak DACB tabanlı bir HB aracı olan ?hpmetis? üretilmiştir. Ayrıca, yine onmetis kullanılarak bir Dantzig-Wolfe ayrıştırma aracı olan ?dwmetis? üretilmiştir. Dantzig-Wolfe ayrıştırma ise doğrusal problemlerin etkin koşutlanmasında kullanılmaktadır. Deneysel sonuçlarımız gösterdi ki, genişletilen oPaToH, seyrek doğrusal sistem çözümünde hali hazırdaki iyi yöntemlere göre %20'lere varan iyileşme göstermiştir. Üretilen Dantzig-Wolfe ayrıştırma aracı dwmetis ise hali hazırda kullanılan HB tabanlı yöntemlere göre makul kalıte farklılıklarında 5 kata kadar hızlı sonuç üretebilmiştir. Bu sonuç da gayet değerlidir, çünkü toplam performans ölçülürken önçalışma zamanı da değer taşımaktadır. Sonuç olarak, bu çalışmada gösterildi ki koşut ve bilimsel hesaplama işlemlerinin, HB ve DACB problemlerini birbirlerine dönüştürümü kullanılarak daha hızlı çalışmaları sağlanabilmektedir.