Preprocessing Algorithm for the Generalized SVD on the Graphics Processing Units

diplomski rad

• Autor: Goran Flegar
• Mentor: Sanja Singer (mentor)
• Član povjerenstva: Sanja Singer (predsjednik povjerenstva)
• Član povjerenstva: Nela Bosner (član povjerenstva)
• Član povjerenstva: Zvonimir Bujanović (član povjerenstva)
• Član povjerenstva: Marko Vrdoljak (č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: 2016-07-01, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

In this thesis we study a preprocessing algorithm for the generalized SVD and its parallelization on the graphics processing unit. The preprocessing algorithm reduces a general matrix pair (A; B) to an upper triangular matrix pair (\(\tilde{A}, \tilde{B}\)) where B is nonsingular. After the preprocessing step a specialized algorithm, such as the implicit Kogbetliantz or the Hari–Zimmerman algorithm, which requires this structure of the matrix pair can be used to compute the generalized SVD. In the first chapter of the thesis we define the generalized SVD and describe the upper triangular decomposition resulting from the preprocessing step. Additionally, we describe the complete orthogonal decomposition which is used in the preprocessing step. The second chapter describes the challenges that arise when developing algorithms for the GPU and presents an efficient implementation of the preprocessing step. In the final chapter we test the algorithm on a variety of matrices of different sizes and compare the speed, rank detection, backward error and the effect on generalized singular values of our algorithm and LAPACK’s and MKL’s versions of xGGSVP.

Sažetak (hrvatski)

U ovom radu proučavamo algoritam pretprocesiranja za generalizirani SVD i njegovu paralelizaciju na grafičkoj kartici. Algoritam pretprocesiranja reducira par proizvoljnih matrica (A; B) na gornje trokutasti par (\(\tilde{A}, \tilde{B}\)) pri čemu je $\tilde{B}$ regularna matrica. Nakon algoritma pretprocesiranja za računanje generaliziranog SVD-a mogu se iskoristiti specijalizirani algoritmi, kao sto je implicitni Kogbrliantzov ili implicitni Hari–Zimmermanov algoritam, koji zahtijevaju ovakvu strukturu para matrica. U prvom poglavlju rada definiramo generalizirani SVD i opisujemo gornje trokutastu faktorizaciju koja je rezultat pretprocesiranja. Dodatno, opisujemo potpunu ortogonalnu faktorizaciju korištenu u postupku pretprocesiranja. U drugom poglavlju opisuju se izazovi koji se pojavljuju pri razvoju algoritama za grafičke kartice te se daje efikasna implementacija algoritma pretprocesiranja. U zadnjem poglavlju testiramo razvijeni algoritam na matricama različitih veličina i uspoređujemo brzinu, detekciju ranga, povratnu grešku i utjecaj na generalizirane singularne vrijednosti našeg algoritma te LAPACK-ove i MKL-ove verzije procedure xGGS VP.

• Ključne riječi: preprocessing algorithm; generalized SVD; implicit Kogbetliantz algorithm; Hari–Zimmerman algorithm
• Ključne riječi (hrvatski): algoritam pretprocesiranja; generalizirani SVD; implicitni Kogbrliantzov algoritam; implicitni Hari–Zimmermanov algoritam
• Jezik: engleski
• URN:NBN: urn:nbn:hr:217:008225
• Studijski program: Naziv: Računarstvo i matematika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra računarstva i matematike (mag. inf. et math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2019-01-22 10:16:09