Unit:
Κατεύθυνση / ειδίκευση Θεωρητική Πληροφορική (ΘΕΩ)Library of the School of Science
Author:
Καρακωνσταντής Ιωάννης
Supervisors info:
Νικόλαος Μισυρλής Καθηγητής (Επιβλέπων), Φίλιππος Τζαφέρης Επίκ. Καθηγητής
Original Title:
Ένας τυχαιοποιημένος αλγόριθμος για την μέθοδο απαλοιφής του Gauss
Translated title:
A randomized algorithm for Gauss elimination method
Summary:
This Master thesis presents a modification over Gaussian elimination method
using randomness in order to be used in high performance parallel computers.
Gauss elimination method is one of the most known and documented method for
solving linear systems, but it cannot be applied directly for solving a
problem. In order to produce accurate results, additional pivoting (eg.
complete, partial) is required. In a parallel architecture, pivoting not only
introduces additional computational cost, but also high communication overhead
generated by data movement among the processors.
The method proposed in this thesis is called Random Butterfly Transformation –
RBT and with a probability near to 1 is able to transform a linear system to a
new form, in which pivoting is not required. That can be managed with a
procedure that involves the generation of “sufficient random” recursive
matrices called “recursive butterfly matrices” and the multiplication of the
linear system matrices with those recursive butterfly matrices.
Additionally, we present the impact of the transformation to the condition
number of the matrices and we discuss some issues about the fine tuning of the
algorithm like the range of the random numbers or the recursion depth.
Furthermore, additional implementation issues are examined like how to store in
an efficient way the recursive butterfly matrices and implementing the method
on GPU.
In order to be able to confirm the performance of the method, we conducted some
tests based on testing classes of matrices proposed in the literature. Comments
on the arithmetic accuracy and overall performance of the method are provided
too.
Keywords:
Linear system, Arithmetic algebra, Gauss elimination method, Random Butterfly Transformation, Pivoting
Number of index pages:
81
