Teknik Perbaikan Metode Ziegler, Suatu Algoritme untuk Kompresi Matriks Sparse

Abstract

Salah satu metode untuk mengkompresi matriks sparse adalah Metode Ziegler. Prinsip utama metode ini adalah membandingkan antara vektor baris pada matriks dengan vektor baris yang ada di bawahnya, sehingga dihasilkan suatu susunan linier. Agar elemen-elemen tak nol suatu baris dapat dipasangkan dengan elemen nol baris di bawahnya (atau sebaliknya), baris ini dapat digeser ke kanan. Apabila keadaan elemen-elemen suatu baris tidak dapat semuanya dipasangkan (elemen nol dan elemen tak nol) dengan baris di bawahnya, maka Metode Ziegler ini tidak dapat berfungsi dengan baik. Untuk mengatasi kelemahan Metode Ziegler, Chang et al. (1996) mengemukakan teknik perbaikannya. Pada dasarnya teknik perbaikan ini masih menggunakan Metode Ziegler, tetapi teknik perbaikan ini mengandaikan vektor baris dan susunan linier sebagai cincin sehingga dapat diputar ke kanan. Berdasarkan analisis algoritme secara teori, Metode Ziegler dengan worst-case O (n² m²) lebih baik daripada Perbaikan Metode Ziegler dengan worst-care O (n m³). Sedangkan analisis secara aktual yang berdasarkan output program, susunan linier yang dihasilkan oleh Perbaikan Metode Ziegler mempunyai panjang yang lebih pendek daripada susunan linier yang dihasilkan Metode Ziegler, tetapi waktu eksekusi yang dibutuhkan Perbaikan Metode Ziegler lebih lama dibandingkan dengan waktu eksekusi Metode Ziegler.