Preprocessing Algorithm for the Generalized SVD on the Graphics Processing Units

master's thesis

• Author: Goran Flegar
• Mentor: Sanja Singer (mentor)
• Committee member: Sanja Singer (predsjednik povjerenstva)
• Committee member: Nela Bosner (član povjerenstva)
• Committee member: Zvonimir Bujanović (član povjerenstva)
• Committee member: Marko Vrdoljak (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2016-07-01, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

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.

Abstract (croatian)

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.

• Keywords: preprocessing algorithm; generalized SVD; implicit Kogbetliantz algorithm; Hari–Zimmerman algorithm
• Keywords (croatian): algoritam pretprocesiranja; generalizirani SVD; implicitni Kogbrliantzov algoritam; implicitni Hari–Zimmermanov algoritam
• Language: english
• URN:NBN: urn:nbn:hr:217:008225
• Study programme: Title: Computer Science and Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra računarstva i matematike (magistar/magistra računarstva i matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2019-01-22 10:16:09