Blokirani algoritmi za QR faktorizaciju

diplomski rad

• Autor: Ivan Kiš
• Mentor: Nela Bosner (mentor)
• Član povjerenstva: Nela Bosner (predsjednik povjerenstva)
• Član povjerenstva: Ozren Perše (član povjerenstva)
• Član povjerenstva: Dražen Adamović (član povjerenstva)
• Član povjerenstva: Snjež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 obrane: 2019-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: QR faktorizacija; Householderovi reflektori; Givensove rotacije
• Ključne riječi (engleski): QR factorization; Householder reflectors; Givens rotations
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:397741
• Studijski program: Naziv: Primijenjena matematika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra matematike (mag. math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2020-02-06 10:46:13