prikaz prve stranice dokumenta Blokirani algoritmi za QR faktorizaciju
  Preuzmi
PDF 635.16 KB
diplomski rad
Blokirani algoritmi za QR faktorizaciju
Zagreb: Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, 2019. urn:nbn:hr:217:397741
Kiš, Ivan
Sveučilište u Zagrebu
Prirodoslovno-matematički fakultet
Matematički odsjek

Institucijski repozitorij: Repozitorij Prirodoslovno-matematičkog fakulteta

Citirajte ovaj rad

Kiš, I. (2019). Blokirani algoritmi za QR faktorizaciju (Diplomski rad). Zagreb: Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet. Preuzeto s https://urn.nsk.hr/urn:nbn:hr:217:397741

Kiš, Ivan. "Blokirani algoritmi za QR faktorizaciju." Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, 2019. https://urn.nsk.hr/urn:nbn:hr:217:397741

Kiš, Ivan. "Blokirani algoritmi za QR faktorizaciju." Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, 2019. https://urn.nsk.hr/urn:nbn:hr:217:397741

Kiš, I. (2019). 'Blokirani algoritmi za QR faktorizaciju', Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, citirano: 13.05.2024., https://urn.nsk.hr/urn:nbn:hr:217:397741

Kiš I. Blokirani algoritmi za QR faktorizaciju [Diplomski rad]. Zagreb: Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet; 2019 [pristupljeno 13.05.2024.] Dostupno na: https://urn.nsk.hr/urn:nbn:hr:217:397741

I. Kiš, "Blokirani algoritmi za QR faktorizaciju", Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, Zagreb, 2019. Dostupno na: https://urn.nsk.hr/urn:nbn:hr:217:397741

Za citiranje koristite ovu mrežnu adresu: https://urn.nsk.hr/urn:nbn:hr:217:397741
Podaci o radu
NaslovBlokirani algoritmi za QR faktorizaciju
AutorIvan Kiš
MentorNela Bosner (mentor)
Član povjerenstvaNela Bosner (predsjednik povjerenstva)
Član povjerenstvaOzren Perše (član povjerenstva)
Član povjerenstvaDražen Adamović (član povjerenstva)
Član povjerenstvaSnježana Lubura Strunjak (č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 obrane2019-09-24, Hrvatska
Znanstveno / umjetničko
područje, polje i grana		PRIRODNE ZNANOSTI
Matematika
Sažetak
Standardni način računanja QR faktorizacije je primjena niza elementarnih ortogonalnih transformacija na matricu, i to Householderovih reflektora ili Givensovih rotacija. Međutim, njihova primjena je prilično neefikasna jer se bazira na BLAS 1 i BLAS 2 operacijama. U ovom radu predstavljene su blokirane verzije QR algoritama koji se oslanjaju na BLAS 3 operacije i efikasno koriste brzu cache memoriju. To znači da se algoritam mora restruktuirati na način da se stupci organiziraju u blokove koji se najprije obrade, a tek onda se ostatak matrice ažurira korištenjem matrično-matričnog množenja. Na taj način smanjuje se komunikacija između brze cache memorije i sporije RAM memorije. Za algoritam baziran na Householderovim reflektorima opisali smo dvije verzije blokiranja: pomoću WY reprezentacije produkta reflektora, i pomoću YTY reprezentacije produkta koji koristi manje memorije od WY. Za algoritam baziran na Givensovim rotacijama smo opisali generiranje akumuliranih rotacija u obliku matrica malih dimenzija. Njihovom implementacijom i uspoređivanjem vremena izvršavanja neblokiranih i blokiranih verzija algoritma dobili smo višestruko vremensko ubrzanje, što je bilo i očekivano.
Sažetak (engleski)
A standard way of calculating QR factorization is to apply a series of elemental orthogonal transformations to a matrix, namely Householder reflectors or Givens rotations. However, their implementation is quite inefficient as it is based on BLAS 1 and BLAS 2 operations. In this paper, block versions of QR algorithms are presented that rely on BLAS 3 operations and use fast cache efficiently. This means that the algorithm must be restructured in such a way that the columns are organized into blocks which are first processed, and only then the rest of the matrix is updated by using matrix-matrix multiplication. This reduces the communication between fast cache and slower RAM. For the Householder reflector algorithm, we describe two blocking versions: using the WY representation of the reflector product, and using the YTY representation of the product which uses less memory than WY. For a Givens-based rotation algorithm, we have described the generation of accumulated rotations in the form of small-dimensional matrices. By implementing them and comparing the execution time of unblocked and blocked versions of the algorithm, we obtained multiple time acceleration, as we expected.
Ključne riječi
Ključne riječi (engleski)
Jezikhrvatski
URN:NBNurn:nbn:hr:217:397741
Studijski programNaziv: Primijenjena matematika
Vrsta studija: sveučilišni
Stupanj studija: diplomski
Akademski / stručni naziv: magistar/magistra matematike (mag. math.)
Vrsta resursaTekst
Način izrade datotekeIzvorno digitalna
Prava pristupaOtvoreni pristup
Uvjeti korištenjaIkona licence Zaštićeno autorskim pravom.
Datum i vrijeme pohrane2020-02-06 10:46:13