Implementasi Hypergraph Partitioning pada Paralelisasi Perkalian Matriks-Vektor

Abstract

Proses perhitungan perkalian matriks-vektor dalam penyelesaian masalah di dunia nyata seringkali melibatkan matriks dengan ukuran sembarang dan besar. Oleh sebab itu, paralelisasi dilakukan untuk mempercepat proses perhitungan tersebut yang biasanya memerlukan waktu lama. Makalah ini membahas paralelisasi yang efisien untuk perkalian matriks-vektor melalui teknik graf. Teknik graph partitioning yang telah dibahas pada penelitian sebelumnya tidak dapat digunakan dalam menyelesaikan perhitungan perkalian matriks-vektor dengan ukuran matriks sembarang. Hal ini disebabkan oleh asumsi dari teknik graph partitioning yang hanya dapat menyelesaikan matriks persegi dan simetris saja. Adapun implementasi yang ditunjukkan pada makalah ini adalah perkalian matriks dengan ukuran 4×3 dan vector berukuran 3×1 dimana matriks tersebut bukan matriks persegi ataupun simetris sehingga teknik graph partitioning tidak dapat digunakan. Dengan demikian, teknik hypergraph partitioning dipilih untuk mengatasi kekurangan dari teknik graph partitioning tersebut.