Paralelni algoritmi za QR faktorizaciju

diplomski rad

• Autor: Vedran Rukavina
• Mentor: Nela Bosner (mentor)
• Član povjerenstva: Nela Bosner (predsjednik povjerenstva)
• Član povjerenstva: Ana Prlić (član povjerenstva)
• Član povjerenstva: Snježana Lubura Strunjak (član povjerenstva)
• Član povjerenstva: Miljenko Marušić (č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

U ovom radu opisujemo serijske i paralelne algoritme za računanje QR faktorizacije. Opisujemo serijski algoritam za računanje QR faktorizaciju pomoću klasičnog i modificiranog Gram-Schmidtovog postupka te serijski algoritam koji koristi Householderove reflektore za računanje već spomenute faktorizacije. Opisujemo paralelne algoritme za računanje QR faktorizacije kao što su TSQR, CAQR i HRCAQR koja je ograničena varijanta CAQR. Neke od algoritama smo implementirali koristeći C programski jezik, a za paralelni algoritam smo koristili C s CUDA sučeljem. Na kraju rada su pokazani rezultati implementiranih algoritama uspoređeni s MATLAB - ovom implementacijom QR algoritama. Cijeli rad smo zaključili s diskusijom o dobivenim rezultatima.

Sažetak (engleski)

In this paper, we describe serial and parallel algorithms for computing QR factorization. We describe a serial algorithm for computing QR factorization using the classical and modified Gram-Schmidt methods and a serial algorithm that uses Householder reflectors to calculate the factorization that we have already mentioned. We describe parallel algorithms for computing QR factorization such as TSQR, CAQR, and HRCAQR which is a restricted variant of CAQR. Some of the algorithms were implemented using the C programming language, and for the parallel algorithm, we used C with the CUDA interface. At the end of the paper, the results of the implemented algorithms are shown compared to MATLABs implementation of QR algorithms. We concluded the whole paper with a discussion of the obtained results.

• Ključne riječi: QR faktorizacija; Gram-Schmidtov postupak; Householderovi reflektori; MATLAB
• Ključne riječi (engleski): QR factorization; Gram-Schmidt methods; Householder reflectors; MATLAB
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:224975
• 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-24 13:34:02