Analisis Kompleicsitas Dan Implementasi Algoritma Strassen

Abstract

Perkalkm matriks merupakan suatu operasi yang penting karma banyak digunakan untuk mensecahkun masalah yang &Aaiun. dengan dunia nyata, terutama untie kepentingan sains clan rekayasa perangkat hawk Mown biaya perkalian matriks dengan arra klasilc adalah mahal. Strategi yang dilakukan para peneliti adakth mengurangijrunlah perkalian skater rneskiper nantinya dalam strategi tersebut akan meningicatkan jumlah operasi penjusdahan skater: Strategi ini digunakan mengingat bahwa biaya perkalian skater lebih besar darOada biaya penjumlahan skalar. Penulisan ini bertrOan wine menganalisa sake sate algoritma perkalian matriks yaitu Algoritma &MUM dimana algoritma ini berguna untuk mengurangi konrpleksitas suatu perkalian matriks. Metode penelitian yang digunakan adalah dengan melakukan studi literatur dart berbagai artikel-artikel di media elektronik dan juga bukst-biebr yang berkaitan dengwr Algoritma Strassen. Selain itu jugs dilakukan praktek program untuk menghitung dan membandingkm waktu elapsed dart Algoritma Klasik dengan Algoritma Strasser. Bahasa pemrogram yang digwmakan adalah C. . Strassen menurunkun algoritmarrya menggunakan matriks basis sebagai kombinasi linier, walaupun tidak ada penjelasan tentang basis yang dipilih. Sehingga dihasilkan 7 perkalian skalar dan 18 perOanlahan skalar dart Algoritma Strussin. Perhitungan kornpleksitas, dengan mengabaikan !cowmen penjumlahan pada algoritma Strassen menghasilkan 0(n2si).Dimana formula kompleksitas algoritma Strassen ini nampidarya harms direvisi mengingat hasil *i CPU menggunakan software Performance Test menunjukkan bahwa cacahan floating point operasi penjumlahan tidak bisa diabaikan terhadap operasi perkalian. Dan dart eksekusi program membuktikan secara hardware Algoritma Strassen tidak mampu nserturwskan waktu operasi perkalian matriksnya dibandingkan perkalian matriks dengan Algoritma Klasilc.