Library Automation and Digital Archive
LONTAR
Fakultas Ilmu Komputer
Universitas Indonesia

Pencarian Sederhana

Find Similar Add to Favorite

Call Number SK-0605 (Softcopy SK-84) Source Code SK-26
Collection Type Skripsi
Title Optimisasi perkalian sparse matrix-vektor menggunakan compresed storage row/ Charles Gunawan
Author Charles Gunawan;
Publisher Depok: Fasilkom, 2005
Subject Sparse matrices
Location FASILKOM-UI;
Lokasi : Perpustakaan Fakultas Ilmu Komputer
Nomor Panggil ID Koleksi Status
SK-0605 (Softcopy SK-84) Source Code SK-26 TERSEDIA
Tidak ada review pada koleksi ini: 8984
Perkalian matriks sparse dan vektor adalah operasi yang banyak digunakan, misalnya pada metode iterative untuk penyelesaian sistem persamaan linier yang sparse. Ukuran matriks sparse yang digunakan biasanya cukup besar dan memiliki densitas yang rendah. Hal ini mengakibatkan algoritma yang biasa digunakan untuk matriks padat menjadi tidak efisien. Dengan menggunakan karakteristik dari matriks sparse kita dapat menggunakan algoritma yang lebih efisien. Salah satu cara yang biasa digunakan adalah dengan menggunakan struktur data yang khusus untuk matriks sparse. Salah satu struktur data untuk menyimpan matriks sparse adalah compressed storage row (CSR). Tulisan ini memberikan gambaran hasil yang diperoleh pada percobaan perkalian matriks sparse dan vektor (SMVM) menggunakan format CSR dibandingan dengan perkalian matriks dense dan vektor. Selain itu dilakukan optimisasi pada SMVM tersebut dengan menggunakan reordering matriks, fungsi perkalian vektor– vektor yang telah dioptimisasi, penghilangan akses memori tidak langsung, serta static linking. Untuk tiap percobaan dilakukan pengukuran terhadap jumlah operasi bilangan floating point serta waktu yang diperlukan untuk melakukan SMVM. Tiap percobaan diimplementasikan menggunakan bahasa C++ pada sistem operasi Linux. Hasil yang diperoleh pada percobaan tersebut adalah terjadi penurunan waktu yang diperlukan untuk SMVM dengan menggunakan format CSR dibandingkan perkalian matriks dense–vektor. Selain itu reordering matriks dapat lebih mengurangi waktu dengan meningkatkan lokalitas nilai–nilai tidak nol pada matriks. Untuk optimisasi lain yang dilakukan tidak didapatkan hasil yang signifikan. Sedangkan nilai mega jumlah operasi bilangan floating point perdetik (mflop/s) berfluktuasi sesuai dengan struktur matriks yang dioperasikan.