20.500.12556/RUL-173283 Analiza algoritmov za množenje redkih matrik Analyzation of algorithms for Sparse Matrix Multiplication Naloga predstavlja raziskavo množenja redkih matrik, ki je temeljna operacija na področjih, kot so strojno učenje, računalniška fizika in analiza omrežij. Najprej bomo predstavili matematično ozadje in običajne predstavitve redkih matrik ter pogledali nekaj osnovnih in sodobnih algoritmov za njihovo množenje. Opisali bomo tudi računsko zahtevnost in tipične aplikacijske zahteve, ki oblikujejo merila za izbiro algoritma. Glavni prispevek naloge je sistematična eksperimentalna analiza, ki smo jo izvedli z uporabo orodja ALGator. V jeziku Java smo implementirali več pristopov za množenje redkih matrik. Definirali smo testne množice z različnimi lastnostmi in s pomočjo orodja ALGator definirali protokol postavitve eksperimenta in strategijo obdelave merilnih podatkov, kar omogoča ponovljivost in primerljivost rezultatov. Za reprezentativnost rezultatov smo zasnovali in ustvarili skrbno opredeljene testne množice ter izvedli merjenja na treh razredih primerov: majhne, srednje in velike matrike, vključno z robnimi primeri. Analiza rezultatov kaže, da so nekateri algoritmi močno odvisni od gostote in porazdelitve neničelnih elementov, medtem ko pri majhnih matrikah odločilno vlogo igra režijski strošek izvajalnega okolja. Naloga prinaša praktične smernice, ponovljive eksperimentalne postopke in odprt nabor testnih množic, ki lahko služijo kot osnova za nadaljnje raziskave in optimizacije množenja redkih matrik. This thesis presents a study of sparse matrix multiplication, a fundamental operation in fields such as machine learning, computational physics, and network analysis. First, we present the mathematical background and common representations of sparse matrices and review several classical and modern algorithms for their multiplication. We also describe the computational complexity and the typical application requirements that shape the criteria for algorithm selection. The main contribution of this thesis is a systematic experimental analysis performed using the tool ALGator. We implemented several approaches to sparse matrix multiplication in Java. To ensure the representativeness of the results, we designed and created carefully defined test suites and carried out measurements across three classes of cases: small, medium, and large matrices, including edge cases. The analysis shows that some algorithms are strongly dependent on the density and distribution of nonzero elements, while for small matrices the overhead of the execution environment plays a decisive role. The thesis provides practical guidelines, reproducible experimental procedures, and an open set of test suites that can serve as a basis for further research and optimizations in sparse matrix multiplication. redka matrika algoritem implementacija sparse matrix algorithm implementation true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2025-09-15 12:45:06 2025-09-15 12:45:11 2025-11-07 03:54:04 0000-00-00 00:00:00 2025 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 38206 253571587 Podbregar_Gasper_-_Analiza_algoritmov_za_mnozenje_redkih_matrik.pdf Podbregar_Gasper_-_Analiza_algoritmov_za_mnozenje_redkih_matrik.pdf 1 F27CBB5FAEE4D94D98D04A6812C93997 433aebc4c4e28fd9ca4895716a05351674c968087996355098ef146c0fcde108 e2a3d354-9220-11f0-9328-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=217538 Fakulteta za računalništvo in informatiko 0 0 0