Perbandingan Kinerja Algoritme Eliminasi Gauss Konvensional dan Eliminasi Gauss Successive dalam Menyelesaikan Sistem Persamaan Linear

Abstract

Sistem persamaan linear adalah masalah yang banyak ditemukan pada berbagai aplikasi. Penelitian ini bertujuan untuk membandingkan kinerja algoritme eliminasi Gauss konvensional dan eliminasi Gauss Successive dalam menyelesaikan sistem persamaan linear. Algoritme eliminasi Gauss Successive adalah varian dari algoritme eliminasi Gauss konvensional yang menggunakan perulangan rekursif untuk meniadakan fase substitusi balik dalam penyelesaian sistem persamaan linear. Suandani (2001) telah menunjukkan bahwa eliminasi Gauss Successive dapat didekomposisi menjadi proses-proses yang dapat dieksekusi secara paralel dengan kompleksitas 2n²-2. Lismawati (2003) mendapatkan speedup eksekusi paralel mendekati 2 pada implementasi eliminasi Gauss Successive. Namun pada penelitian Suandani (2001) dan Lismawati (2003) eliminasi Gauss Successive tidak dibandingkan dengan algoritme lainnya. Penelitian ini membandingkan kompleksitas dekomposisi task paralel eliminasi Gauss Successive (Suandani 2001) dengan dekomposisi task paralel eliminasi Gauss konvensional (Carter et al. 1995) juga membandingkan speedup dan efisiensi implementasi paralel eliminasi Gauss Successive (Lismawati 2003) dengan speedup dan efisiensi implementasi paralel eliminasi Gauss konvensional (Carter et al. 1995). Hasil analisis algoritme menunjukkan bahwa rasio jumlah proses eliminasi Gauss Successive dibanding eliminasi Gauss konvensional mendekati 2.3. Hal serupa ditunjukkan oleh perbandingan running time secara sekuensial. Untuk pengukuran running time digunakan 6 input ukuran matriks yaitu 100, 300, 500, 700 dan 900. Eksekusi program dilakukan pada beberapa spesifikasi komputer yang berbeda untuk melihat kecenderungan perubahan running time. Speedup dan efisiensi paralel dari eliminasi Gauss konvensional lebih baik dari eliminasi Gauss Successive.