{"id":{"repo_id":"athens","oai_identifier":"oai:lib.uoa.gr:uoadl:1317562"},"canonical_url":"https://search.ndltd.org/etd/athens/oai:lib.uoa.gr:uoadl:1317562","repository":{"repo_id":"athens","name":"National and Kapodistrian University of Athens","base_url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh"},"display":{"title":"Ένας τυχαιοποιημένος αλγόριθμος για την μέθοδο απαλοιφής του Gauss","abstract":"Η παρούσα διπλωματική εργασία ασχολείται με την τροποποίηση της μεθόδου απαλοιφής του Gauss χρησιμοποιώντας την τυχαιότητα, έτσι ώστε να έχει μια μορφή κατάλληλη για να εφαρμοστεί σε υψηλής επίδοσης, παράλληλους υπολογιστές. Η μέθοδος απαλοιφής του Gauss είναι μια από τις πιο γνωστές μεθόδους για την επίλυση γραμμικών συστημάτων, η οποία όμως δεν μπορεί να εφαρμοστεί ανεξάρτητα για την επίλυση ενός προβλήματος. Για την παραγωγή ακριβών αποτελεσμάτων, απαιτείται επιπρόσθετα η χρήση της τεχνικής της οδήγησης (πχ. ολική, μερική). Σε παράλληλες αρχιτεκτονικές η οδήγηση δεν εισάγει μόνο επιπρόσθετο υπολογιστικό φόρτο, αλλά και σημαντική επιβάρυνση λόγω του κόστους επικοινωνίας που απαιτείται μεταξύ των επεξεργαστών. Η μέθοδος που περιγράφουμε στην εργασία αυτή ονομάζεται Τυχαίος Μετασχηματισμός Πεταλούδας (Random Butterfly Transformation (RBT)) είναι μια μέθοδος που με πιθανότητα σχεδόν 1 μπορεί να μετασχηματίσει ένα γραμμικό σύστημα σε μορφή στην οποία δεν είναι απαραίτητη η χρήση οδήγησης. Αυτό επιτυγχάνεται πολλαπλασιάζοντας κατάλληλα τους πίνακες του αρχικού γραμμικού συστήματος με «κατάλληλα τυχαίους» αναδρομικούς πίνακες πεταλούδας. Επιπρόσθετα, στην εργασία παρουσιάζεται η επίδραση της μεθόδου στον αριθμό συνθήκης (condition number) των πινάκων και ασχολούμαστε με ορισμένα θέματα επιλογής παραμέτρων (tuning) για την μέθοδο, όπως το εύρος των τυχαίων αριθμών και τα επίπεδα αναδρομής. Στη συνέχεια, παρουσιάζονται ορισμένα θέματα για την πιο αποτελεσματική υλοποίηση, όπως η αποδοτική αποθήκευση των αναδρομικών πινάκων πεταλούδας. Επίσης, υποδεικνύονται ορισμένα βασικά στοιχεία για την παράλληλη υλοποίηση της μεθόδου RBT σε κάρτες γραφικών (GPUs). Τέλος, για την πειραματική επαλήθευση της απόδοσης της μεθόδου, έχουν δημιουργηθεί ορισμένες δοκιμαστικές κλάσεις πινάκων στις οποίες εφαρμόζεται η μέθοδος RBT και προκύπτουν τα απαραίτητα αριθμητικά αποτελέσματα.","abstract_html":"Η παρούσα διπλωματική εργασία ασχολείται με την τροποποίηση της μεθόδου απαλοιφής του Gauss χρησιμοποιώντας την τυχαιότητα, έτσι ώστε να έχει μια μορφή κατάλληλη για να εφαρμοστεί σε υψηλής επίδοσης, παράλληλους υπολογιστές. Η μέθοδος απαλοιφής του Gauss είναι μια από τις πιο γνωστές μεθόδους για την επίλυση γραμμικών συστημάτων, η οποία όμως δεν μπορεί να εφαρμοστεί ανεξάρτητα για την επίλυση ενός προβλήματος. Για την παραγωγή ακριβών αποτελεσμάτων, απαιτείται επιπρόσθετα η χρήση της τεχνικής της οδήγησης (πχ. ολική, μερική). Σε παράλληλες αρχιτεκτονικές η οδήγηση δεν εισάγει μόνο επιπρόσθετο υπολογιστικό φόρτο, αλλά και σημαντική επιβάρυνση λόγω του κόστους επικοινωνίας που απαιτείται μεταξύ των επεξεργαστών. Η μέθοδος που περιγράφουμε στην εργασία αυτή ονομάζεται Τυχαίος Μετασχηματισμός Πεταλούδας (Random Butterfly Transformation (RBT)) είναι μια μέθοδος που με πιθανότητα σχεδόν 1 μπορεί να μετασχηματίσει ένα γραμμικό σύστημα σε μορφή στην οποία δεν είναι απαραίτητη η χρήση οδήγησης. Αυτό επιτυγχάνεται πολλαπλασιάζοντας κατάλληλα τους πίνακες του αρχικού γραμμικού συστήματος με «κατάλληλα τυχαίους» αναδρομικούς πίνακες πεταλούδας. Επιπρόσθετα, στην εργασία παρουσιάζεται η επίδραση της μεθόδου στον αριθμό συνθήκης (condition number) των πινάκων και ασχολούμαστε με ορισμένα θέματα επιλογής παραμέτρων (tuning) για την μέθοδο, όπως το εύρος των τυχαίων αριθμών και τα επίπεδα αναδρομής. Στη συνέχεια, παρουσιάζονται ορισμένα θέματα για την πιο αποτελεσματική υλοποίηση, όπως η αποδοτική αποθήκευση των αναδρομικών πινάκων πεταλούδας. Επίσης, υποδεικνύονται ορισμένα βασικά στοιχεία για την παράλληλη υλοποίηση της μεθόδου RBT σε κάρτες γραφικών (GPUs). Τέλος, για την πειραματική επαλήθευση της απόδοσης της μεθόδου, έχουν δημιουργηθεί ορισμένες δοκιμαστικές κλάσεις πινάκων στις οποίες εφαρμόζεται η μέθοδος RBT και προκύπτουν τα απαραίτητα αριθμητικά αποτελέσματα.","abstract_has_math":false,"creators":["Καρακωνσταντής Ιωάννης"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2015,"date_issued":"2015","date_published":"2015","updated_at":"2026-11-19T05:25:06Z","subjects":[],"languages":["Ελληνικά","Greek"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:1317562"],"render_values":[{"text":"uoadl:1317562","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1317562","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1317562","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Alib.uoa.gr%3Auoadl%3A1317562","prefix":"oai_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Καρακωνσταντής Ιωάννης"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2015"]},{"key":"dc:type","label":"Dc Type","values":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["Ελληνικά","Greek"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:1317562","https://pergamos.lib.uoa.gr/uoa/dl/object/1317562"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Η παρούσα διπλωματική εργασία ασχολείται με την τροποποίηση της μεθόδου απαλοιφής του Gauss χρησιμοποιώντας την τυχαιότητα, έτσι ώστε να έχει μια μορφή κατάλληλη για να εφαρμοστεί σε υψηλής επίδοσης, παράλληλους υπολογιστές. Η μέθοδος απαλοιφής του Gauss είναι μια από τις πιο γνωστές μεθόδους για την επίλυση γραμμικών συστημάτων, η οποία όμως δεν μπορεί να εφαρμοστεί ανεξάρτητα για την επίλυση ενός προβλήματος. Για την παραγωγή ακριβών αποτελεσμάτων, απαιτείται επιπρόσθετα η χρήση της τεχνικής της οδήγησης (πχ. ολική, μερική). Σε παράλληλες αρχιτεκτονικές η οδήγηση δεν εισάγει μόνο επιπρόσθετο υπολογιστικό φόρτο, αλλά και σημαντική επιβάρυνση λόγω του κόστους επικοινωνίας που απαιτείται μεταξύ των επεξεργαστών. Η μέθοδος που περιγράφουμε στην εργασία αυτή ονομάζεται Τυχαίος Μετασχηματισμός Πεταλούδας (Random Butterfly Transformation (RBT)) είναι μια μέθοδος που με πιθανότητα σχεδόν 1 μπορεί να μετασχηματίσει ένα γραμμικό σύστημα σε μορφή στην οποία δεν είναι απαραίτητη η χρήση οδήγησης. Αυτό επιτυγχάνεται πολλαπλασιάζοντας κατάλληλα τους πίνακες του αρχικού γραμμικού συστήματος με «κατάλληλα τυχαίους» αναδρομικούς πίνακες πεταλούδας. Επιπρόσθετα, στην εργασία παρουσιάζεται η επίδραση της μεθόδου στον αριθμό συνθήκης (condition number) των πινάκων και ασχολούμαστε με ορισμένα θέματα επιλογής παραμέτρων (tuning) για την μέθοδο, όπως το εύρος των τυχαίων αριθμών και τα επίπεδα αναδρομής. Στη συνέχεια, παρουσιάζονται ορισμένα θέματα για την πιο αποτελεσματική υλοποίηση, όπως η αποδοτική αποθήκευση των αναδρομικών πινάκων πεταλούδας. Επίσης, υποδεικνύονται ορισμένα βασικά στοιχεία για την παράλληλη υλοποίηση της μεθόδου RBT σε κάρτες γραφικών (GPUs). Τέλος, για την πειραματική επαλήθευση της απόδοσης της μεθόδου, έχουν δημιουργηθεί ορισμένες δοκιμαστικές κλάσεις πινάκων στις οποίες εφαρμόζεται η μέθοδος RBT και προκύπτουν τα απαραίτητα αριθμητικά αποτελέσματα.","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."]},{"key":"dc:title","label":"Title","values":["Ένας τυχαιοποιημένος αλγόριθμος για την μέθοδο απαλοιφής του Gauss"]}]}],"canonical_facts":{"dc:creator":["Καρακωνσταντής Ιωάννης"],"dc:date":["2015"],"dc:description":["Η παρούσα διπλωματική εργασία ασχολείται με την τροποποίηση της μεθόδου απαλοιφής του Gauss χρησιμοποιώντας την τυχαιότητα, έτσι ώστε να έχει μια μορφή κατάλληλη για να εφαρμοστεί σε υψηλής επίδοσης, παράλληλους υπολογιστές. Η μέθοδος απαλοιφής του Gauss είναι μια από τις πιο γνωστές μεθόδους για την επίλυση γραμμικών συστημάτων, η οποία όμως δεν μπορεί να εφαρμοστεί ανεξάρτητα για την επίλυση ενός προβλήματος. Για την παραγωγή ακριβών αποτελεσμάτων, απαιτείται επιπρόσθετα η χρήση της τεχνικής της οδήγησης (πχ. ολική, μερική). Σε παράλληλες αρχιτεκτονικές η οδήγηση δεν εισάγει μόνο επιπρόσθετο υπολογιστικό φόρτο, αλλά και σημαντική επιβάρυνση λόγω του κόστους επικοινωνίας που απαιτείται μεταξύ των επεξεργαστών. Η μέθοδος που περιγράφουμε στην εργασία αυτή ονομάζεται Τυχαίος Μετασχηματισμός Πεταλούδας (Random Butterfly Transformation (RBT)) είναι μια μέθοδος που με πιθανότητα σχεδόν 1 μπορεί να μετασχηματίσει ένα γραμμικό σύστημα σε μορφή στην οποία δεν είναι απαραίτητη η χρήση οδήγησης. Αυτό επιτυγχάνεται πολλαπλασιάζοντας κατάλληλα τους πίνακες του αρχικού γραμμικού συστήματος με «κατάλληλα τυχαίους» αναδρομικούς πίνακες πεταλούδας. Επιπρόσθετα, στην εργασία παρουσιάζεται η επίδραση της μεθόδου στον αριθμό συνθήκης (condition number) των πινάκων και ασχολούμαστε με ορισμένα θέματα επιλογής παραμέτρων (tuning) για την μέθοδο, όπως το εύρος των τυχαίων αριθμών και τα επίπεδα αναδρομής. Στη συνέχεια, παρουσιάζονται ορισμένα θέματα για την πιο αποτελεσματική υλοποίηση, όπως η αποδοτική αποθήκευση των αναδρομικών πινάκων πεταλούδας. Επίσης, υποδεικνύονται ορισμένα βασικά στοιχεία για την παράλληλη υλοποίηση της μεθόδου RBT σε κάρτες γραφικών (GPUs). Τέλος, για την πειραματική επαλήθευση της απόδοσης της μεθόδου, έχουν δημιουργηθεί ορισμένες δοκιμαστικές κλάσεις πινάκων στις οποίες εφαρμόζεται η μέθοδος RBT και προκύπτουν τα απαραίτητα αριθμητικά αποτελέσματα.","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."],"dc:identifier":["uoadl:1317562","https://pergamos.lib.uoa.gr/uoa/dl/object/1317562"],"dc:language":["Ελληνικά","Greek"],"dc:title":["Ένας τυχαιοποιημένος αλγόριθμος για την μέθοδο απαλοιφής του Gauss"],"dc:type":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]},"updated_at":"2026-11-19T05:25:06Z"}