Implementacija slučajnog algoritma za singularne dekompozicije matrice

master's thesis

• Title (english): Implementation of a random algorithm for singular value decomposition
• Author: Darko Janeković
• Mentor: Dario Bojanjac (mentor)
• Committee member: Dario Bojanjac (predsjednik povjerenstva)
• Committee member: Marko Bosiljevac (član povjerenstva)
• Committee member: Sonja Grgić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2021-07-06, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

Singularna dekompozicija matrice ključan je korak u mnogim algoritmima iz statistike,
strojnog učenja, ali i numeričke linearne algebre. Iako je klasična singularna dekompozicija
efikasna iz perspektive asimptotske složenosti, klasični algoritmi nisu u mogućnosti
u potpunosti iskoristiti moderna računalna okruženja.
Cilj ovog rada je implementirati stohastičke algoritme za singularnu
dekompoziciju te ih staviti u usporedbu s klasičnim algoritmima. Stohastički algoritmi
predstavljaju noviju skupinu algoritama koja se efikasno preslikava na paralelne računalne sustave.
Algoritmi su uspoređeni s klasičnima po pitanju točnosti i brzine izvođenja.
Na primjeru robusne analize glavnih komponenata, pokazano je da korištenje stohastičkog
algoritma može drastično smanjiti vrijeme izvođenja.

Abstract (english)

Singular value decomposition is a key step in many algorithms in statistics, machine learning and numerical linear algebra. While classical singular value decomposition has been made efficient in terms of computational complexity, classical algorithms are not able to fully utilise modern computing environments.
The goal of this work is to implement a randomized algorithm for singular value decomposition and test its efficiency when compared to classical methods. Randomized algorithms represent a new class of algorithms made fit for parallel computing architectures.
Algorithms are compared in terms of accuracy and time of execution.
On example of randomized principal component analysis, it is shown that using randomized algorithms can yield a significant speedup.

• Keywords: Singularna dekompozicija; BLAS; GPU; PCA
• Keywords (english): Singular value decomposition; BLAS; GPU; PCA
• Language: croatian
• URN:NBN: urn:nbn:hr:168:590880
• Study programme: Title: Computing; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra inženjer/inženjerka računarstva (magistar/magistra inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2023-01-13 12:31:01