Hypergraph partitioning and reordering for parallel sparse triangular solves and tensor decomposition

Bir çok bilimsel ve gerçek hayatta karşılaşılan problem, seyrek matris veya daha genel haliyle çok boyutlu seyrek tensör hesaplamalarını gerektirmektedir. Seyrek matris hesaplamaları için, içerdiği işlemlerin doğal seri yapısı sebebiyle, seyrek üçgensel sistemlerin paralelleştirilmesi önemli zorluklar ortaya çıkarmaktadır. Seyrek üçgensel sistemleri paralelleştirmek için bir yaklaşım, seyrek üçgensel SPIKE (stSPIKE) algoritmasını kullanmaktır. İlk olarak paylaşımlı bellekler için önerilmiş olan stSPIKE, problemi daha küçük bağımsız sistemlere ayrıştırır ve çok daha küçük bir indirgenmiş seyrek üçgensel sistemin çözümünü gerektirir. Biz bu çalışmada, stSPIKE algoritmasını dağıtık bellekli sistemler için genişleterek yazılımını gerçekleştirdik. Daha sonra, stSPIKE algoritmasını kullanarak dağıtık bellekli paralel Gauss-Seidel (dmpGS) ve ILU (dmpILU) algoritmalarını önerdik. Ayrıca, dmpGS ve dmpILU çözümünde ortaya çıkan indirgenmiş sistemlerin boyutunu ve sıfırdışı eleman sayısını en aza indirmek amacıyla özgün hiperçizge bölümleme modelleri ve blok-içi yeniden sıralama yöntemleri önerdik. Diğer yandan seyrek tensör hesaplamaları konusunda, tensör ayrıştırma, çok boyutlu verilerin analizi için oldukça yaygın kullanılmaktadır. Kanonik çok öğeli ayrıştırma (CPD), en sık kullanılan tensör ayrıştırma yöntemlerinden biridir ve yaygın olarak CPD-ALS algoritması ile çözülür. CPD-ALS algoritmasının yüksek hesaplama ve hafıza talepleri sebebiyle, dağıtık bellekli paralel bir algoritma kullanmak verimlilik için kaçınılmazdır. Çok boyutlu kartezyen tensör bölümleme yöntemini benimseyen orta ölçekli CPD-ALS algoritması, seyrek tensör ayrıştırması için önerilmiş en başarılı dağıtık bellekli CPD-ALS algoritmalarından biridir. Biz, çok boyutlu kartezyen tensör bölümlemesinin iletişim hacmini en aza indirgemeyi, bölümleme hedefiyle doğru bir şekilde karşılayan özgün bir hiperçizge bölümleme modeli (CartHP) öneriyoruz. Gerçek hayat problemlerinden elde edilmiş seyrek matris ve tensörler üzerindeki geniş kapsamlı deneyler, önerilen algortimaların paralel ölçeklenebilirliğini ve önerilen hiperçizge bölümleme ve yeniden sıralama modellerinin etkinliğini doğrular niteliktedir.