prikaz prve stranice dokumenta Blokirani algoritmi za QR faktorizaciju
  Download
PDF 635.16 KB
master's thesis
Blokirani algoritmi za QR faktorizaciju
Zagreb: University of Zagreb, Faculty of Science, 2019. urn:nbn:hr:217:397741
Kiš, Ivan
University of Zagreb
Faculty of Science
Department of Mathematics

Institutional repository: Repository of the Faculty of Science

Cite this document

Kiš, I. (2019). Blokirani algoritmi za QR faktorizaciju (Master's thesis). Zagreb: University of Zagreb, Faculty of Science. Retrieved from https://urn.nsk.hr/urn:nbn:hr:217:397741

Kiš, Ivan. "Blokirani algoritmi za QR faktorizaciju." Master's thesis, University of Zagreb, Faculty of Science, 2019. https://urn.nsk.hr/urn:nbn:hr:217:397741

Kiš, Ivan. "Blokirani algoritmi za QR faktorizaciju." Master's thesis, University of Zagreb, Faculty of Science, 2019. https://urn.nsk.hr/urn:nbn:hr:217:397741

Kiš, I. (2019). 'Blokirani algoritmi za QR faktorizaciju', Master's thesis, University of Zagreb, Faculty of Science, accessed 26 November 2024, https://urn.nsk.hr/urn:nbn:hr:217:397741

Kiš I. Blokirani algoritmi za QR faktorizaciju [Master's thesis]. Zagreb: University of Zagreb, Faculty of Science; 2019 [cited 2024 November 26] Available at: https://urn.nsk.hr/urn:nbn:hr:217:397741

I. Kiš, "Blokirani algoritmi za QR faktorizaciju", Master's thesis, University of Zagreb, Faculty of Science, Zagreb, 2019. Available at: https://urn.nsk.hr/urn:nbn:hr:217:397741

Metadata
TitleBlokirani algoritmi za QR faktorizaciju
AuthorIvan Kiš
MentorNela Bosner (mentor)
Committee memberNela Bosner (predsjednik povjerenstva)
Committee memberOzren Perše (član povjerenstva)
Committee memberDražen Adamović (član povjerenstva)
Committee memberSnježana Lubura Strunjak (član povjerenstva)
GranterUniversity of Zagreb
Faculty of Science
(Department of Mathematics)
Zagreb
Defense date and country2019-09-24, Croatia
Scientific / art field,
discipline and subdiscipline		NATURAL SCIENCES
Mathematics
Abstract
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.
Abstract (english)
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.
Keywords
Keywords (english)
Languagecroatian
URN:NBNurn:nbn:hr:217:397741
Study programmeTitle: Applied Mathematics
Study programme type: university
Study level: graduate
Academic / professional title: magistar/magistra matematike (magistar/magistra matematike)
Type of resourceText
File originBorn digital
Access conditionsOpen access
Terms of useLicence In copyright icon
Created on2020-02-06 10:46:13