Parallel computation of the hyperbolic QR factorization

master's thesis

• Author: Gayatri Čaklović
• Mentor: Sanja Singer (mentor)
• Committee member: Sanja Singer (predsjednik povjerenstva)
• Committee member: Eduard Marušić-Paloka (član povjerenstva)
• Committee member: Boris Muha (član povjerenstva)
• Committee member: Tomislav Pejković (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2018-07-18-07-18, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

U ovom radu prezentirali smo kako računati hiperboličku QR \(J\)-faktorizaciju. Prvo je postavljena teorija koja nam daje dva načina redukcije matrice \(G \in \mathbb{C}^{m \times n}, m \geq n,\) na blok gornjetrokutastu formu. Jedan način je redukcija jednog stupca pomoću \(J\)-Householderovog reflektora. Razjašnjeni su nužni i dovoljni uvjeti postojanja takvih operatora. Drugi način je redukcija dva stupca koristeći Givensove rotacije. U tom poglavlju je obrađeno što sve zovemo pravilnom (’proper’) formom, kako svesti matrice na pravilnu formu, te kako tu pravilnu formu do kraja reducirati \(J\)-unitarnim matricama manjih dimenzija. Nadalje, indefinitni QR povezali smo sa još jednom faktorizacijom, hermitskom indefinitnom faktorizacijom. Pokazali smo kako su te dvije faktorizacije povezane i koja je optimalna strategija pivotiranja u hermitskoj indefinitnoj faktorizaciji (ona koja ima najmanji pivotni rast u svakom slučaju izbora strategije, nebitno biraju li se dva ili jedan stupac za redukciju). Ista pivotna strategija primijenjena je i na QR faktorizaciju. Naposljetku, prezentiran je sekvencijalni algoritam redukcije matrice \(G\) na gorenje blok trokutastu formu, kao i njegovi dijelovi koji su paralelizirani. Pri optimizaciji koda, u obzir je uzeta i arhitektura memorije računala, te način funkcioniranja biblioteka OpenMP i MKL koje smo koristili za paralelizaciju. Testiranja na umjetno generiranim matricama izvedena su na Intelovom Xeon Phi 7210 računalu, gdje je također u obzir uzeta posebna memorijska arhitektura računala.

Abstract (english)

In this thesis, a way of computing a \(J\)-unitary QR factorization was presented. The theoretical part was set first, in order to explain two possible ways of transforming a matrix \(G \in \mathbb{C}^{m \times n}, m \geq n,\) into a block upper triangular matrix. One way to do this is with \(J\)-unitary Householder like reflectors. The necessary and sufficient conditions for their existence were formed. The other way to do this is using Givens rotations. In that chapter, a term proper form was defined, how to transform matrices into proper forms and, in the end, how are those proper forms fully reduced with \(J\)-unitary matrices of smaller dimensions. Furthermore, we showed how indefinite QR is connected to the Hermitian indefinite factorization. An optimal pivoting strategy for the Hermitian indefinite factorization was presented, based on minimizing the pivot growth (regardless of the fact that one or two columns were chosen as pivotal). The same strategy was then used in the QR factorization. At last, a sequential version of the algorithm for reducing the matrix \(G\) to a block upper triangular form was presented, as well as with the parallelised segments of it. The memory architecture was took into account while optimizing the code as well as the optimal usage of OpenMP and MKL libraries. The tests on randomly generated matrices were performed on Intel’s Xeon Phi 7210. The special architecture of Xeon Phi was also taken into account.

• Keywords: QR faktorizacija; Householderov reflektor; Givensove rotacije; hermitska indefinitna faktorizacija; OpenMP; MKL
• Keywords (english): QR factorization; Householder like reflectors; Givens rotations; Hermitian indefinite factorization; OpenMP; MKL
• Language: croatian
• URN:NBN: urn:nbn:hr:217:024075
• Study programme: Title: Applied Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra matematike (magistar/magistra matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2018-11-22 12:58:01