Eliminasi gauss successive untuk menyelesaikan sistem persamaan linear secara paralel

Abstract

Penggunaan metode langsung (direct method), misalnya Eliminasi Gauss (EG) dan Aturan Cramer, umumnya tidak efisien dalam meyelesaikan sistem persamaan linear Ax-b yang berukuran besar. Metode Eliminasi Gauss Successive (EGS) adalah modifikasi dari metode EG sehingga dapat dieksekusi secara paralel dengan efisien dalam sistem multiprosesor. Metode EGS menghilangkan fase substitusi balik yang terdapat pada EG dan penggantinya dengan satu langkah pembagian pada akhir eksekusi algoritma, serta tetap mendukung pivoting secara parsial untuk menjaga kestabilan numerik. Metode EGS, yang secara garis besar terdiri dari Eliminasi Depan dan Eliminasi Belakang, dapat dipartisi bagian-bagian algoritmanya menjadi tugas-tugas. Tugas-tugas ini kemudian disusun dalam sebuah graf tugas dengan memperhatikan precedence relation antar tugas. Distribusi tugas (penjadwalan) ke setiap prosesor yang terdapat dalam sistem multiprosesor dilakukan berdasarkan graf tugas tersebut untuk memperoleh utilitas prosesor yang optimal. Dengan penjadwalan demikian diperoleh speed-up sebesar O(N), dengan N adalah banyaknya prosesor. Dari sisi akurasi, galat relatif yang muncul dalam penggunaan metode EGS lebih kecil atau sama dengan galat relatif pada metode EG.