Hijerarhijske matrice

diplomski rad

• Naslov (engleski): Hierarchical matrices
• Autor: Marija Lujo
• Mentor: Zvonimir Bujanović (mentor)
• Član povjerenstva: Zvonimir Bujanović (predsjednik povjerenstva)
• Član povjerenstva: Goran Igaly (član povjerenstva)
• Član povjerenstva: Domagoj Vrgoč (član povjerenstva)
• Član povjerenstva: Dražen Adamović (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2022-09-27, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

U ovom radu bavili smo se aproksimacijama niskog ranga i najpoznatijim algoritmima za iste. Temelj za ove algoritme je dekompozicija na singularne vrijednosti (SVD). No, glavna tema ovog rada je pregled najpoznatijih hijerarhijskih formata matrice (HODLR, \(\mathcal{H}\), HSS, \(\mathcal{H}^2\)) i operacija nad njima. Pokazalo se da uz određene uvjete, poput malog (numeričkog) ranga vandijagonalnih blokova matrice, matrice možemo pohraniti u mnogo manje od \(O(n^2) \) prostornih jedinica, a matrične operacije se izvršavaju u skoro linearnom vremenu, što je posebno korisno za matrice velikih dimenzija kakve se najčešće javljaju u praksi. Najveći naglasak stavljen je na HODLR strukturu matrice jer smo istu implementirali u programskom jeziku Python. Na kraju rada dani su neki primjeri matrica koje se mogu pohraniti korištenjem HODLR strukture i dan je pregled najvažnijih primjena hijerarhijskih formata matrica.

Sažetak (engleski)

In this thesis, we dealt with low-rank approximation of matrices and well known algorithms for such purpose. The basis for these algorithms is singular value decomposition (SVD). The main topic of this thesis is an overview of hierarchical matrices (HODLR, \(\mathcal{H}\), HSS, \(\mathcal{H}^2\)) and operations on them. It has been shown that under certain conditions, such as a small (numerical) rank of off-diagonal matrix blocks, matrices can be stored in less than \(O(n^2) \) storage complexity and matrix operations are executed in almost linear time. This is especially useful for matrices of large dimension, such as those that are most often encountered in practice. The greatest emphasis was put on HODLR matrices because we implemented them in the Python programming language. At the end of the thesis, a number of examples of matrices that can be well stored in HODLR structure and an overview of the most important applications of hierarchical matrix formats is given.

• Ključne riječi: aproksimacije niskog ranga; singularne vrijednosti (SVD); HODLR struktura matrice; programski jezik Python
• Ključne riječi (engleski): low-rank approximation; singular value decomposition (SVD); HODLR matrices; Python programming language
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:574485
• Studijski program: Naziv: Računarstvo i matematika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra računarstva i matematike (mag. inf. et math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2022-10-28 11:29:01