Μονάδα:
Κατεύθυνση / ειδίκευση Θεωρητική Πληροφορική (ΘΕΩ)Βιβλιοθήκη Σχολής Θετικών Επιστημών
Ημερομηνία κατάθεσης:
2015-02-06
Συγγραφέας:
Καρακωνσταντής Ιωάννης
Στοιχεία επιβλεπόντων καθηγητών:
Νικόλαος Μισυρλής Καθηγητής (Επιβλέπων), Φίλιππος Τζαφέρης Επίκ. Καθηγητής
Πρωτότυπος Τίτλος:
Ένας τυχαιοποιημένος αλγόριθμος για την μέθοδο απαλοιφής του Gauss
Γλώσσες εργασίας:
Ελληνικά
Μεταφρασμένος τίτλος:
A randomized algorithm for Gauss elimination method
Περίληψη:
Η παρούσα διπλωματική εργασία ασχολείται με την τροποποίηση της μεθόδου
απαλοιφής του Gauss χρησιμοποιώντας την τυχαιότητα, έτσι ώστε να έχει μια μορφή
κατάλληλη για να εφαρμοστεί σε υψηλής επίδοσης, παράλληλους υπολογιστές.
Η μέθοδος απαλοιφής του Gauss είναι μια από τις πιο γνωστές μεθόδους για την
επίλυση γραμμικών συστημάτων, η οποία όμως δεν μπορεί να εφαρμοστεί ανεξάρτητα
για την επίλυση ενός προβλήματος. Για την παραγωγή ακριβών αποτελεσμάτων,
απαιτείται επιπρόσθετα η χρήση της τεχνικής της οδήγησης (πχ. ολική, μερική).
Σε παράλληλες αρχιτεκτονικές η οδήγηση δεν εισάγει μόνο επιπρόσθετο
υπολογιστικό φόρτο, αλλά και σημαντική επιβάρυνση λόγω του κόστους επικοινωνίας
που απαιτείται μεταξύ των επεξεργαστών.
Η μέθοδος που περιγράφουμε στην εργασία αυτή ονομάζεται Τυχαίος Μετασχηματισμός
Πεταλούδας (Random Butterfly Transformation (RBT)) είναι μια μέθοδος που με
πιθανότητα σχεδόν 1 μπορεί να μετασχηματίσει ένα γραμμικό σύστημα σε μορφή στην
οποία δεν είναι απαραίτητη η χρήση οδήγησης. Αυτό επιτυγχάνεται
πολλαπλασιάζοντας κατάλληλα τους πίνακες του αρχικού γραμμικού συστήματος με
«κατάλληλα τυχαίους» αναδρομικούς πίνακες πεταλούδας.
Επιπρόσθετα, στην εργασία παρουσιάζεται η επίδραση της μεθόδου στον αριθμό
συνθήκης (condition number) των πινάκων και ασχολούμαστε με ορισμένα θέματα
επιλογής παραμέτρων (tuning) για την μέθοδο, όπως το εύρος των τυχαίων αριθμών
και τα επίπεδα αναδρομής. Στη συνέχεια, παρουσιάζονται ορισμένα θέματα για την
πιο αποτελεσματική υλοποίηση, όπως η αποδοτική αποθήκευση των αναδρομικών
πινάκων πεταλούδας. Επίσης, υποδεικνύονται ορισμένα βασικά στοιχεία για την
παράλληλη υλοποίηση της μεθόδου RBT σε κάρτες γραφικών (GPUs).
Τέλος, για την πειραματική επαλήθευση της απόδοσης της μεθόδου, έχουν
δημιουργηθεί ορισμένες δοκιμαστικές κλάσεις πινάκων στις οποίες εφαρμόζεται η
μέθοδος RBT και προκύπτουν τα απαραίτητα αριθμητικά αποτελέσματα.
Λέξεις-κλειδιά:
Γραμμικό σύστημα, Αριθμητική άλγεβρα, Μέθοδος απαλοιφής του Gauss, Τυχαίος Μετασχηματισμός Πεταλούδας, Οδήγηση
Αρ. σελίδων ευρετηρίου:
81
Αρ. βιβλιογραφικών αναφορών:
49
