Hijerarhijske matrice

master's thesis

• Title (english): Hierarchical matrices
• Author: Marija Lujo
• Mentor: Zvonimir Bujanović (mentor)
• Committee member: Zvonimir Bujanović (predsjednik povjerenstva)
• Committee member: Goran Igaly (član povjerenstva)
• Committee member: Domagoj Vrgoč (član povjerenstva)
• Committee member: Dražen Adamović (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2022-09-27, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

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.

Abstract (english)

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.

• Keywords: aproksimacije niskog ranga; singularne vrijednosti (SVD); HODLR struktura matrice; programski jezik Python
• Keywords (english): low-rank approximation; singular value decomposition (SVD); HODLR matrices; Python programming language
• Language: croatian
• URN:NBN: urn:nbn:hr:217:574485
• Study programme: Title: Computer Science and Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra računarstva i matematike (magistar/magistra računarstva i matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2022-10-28 11:29:01