Αλγόριθμοι γραφημάτων για την αναδιάταξη σποραδικών μητρών: μία συγκριτική μελέτη
Creators: name: Κοντοκώστα, Μαρίνα Βασιλείου
Publisher: name: Aristotle University of Thessaloniki
Year: 2012
Subjects: Σποραδική Μήτρα
Αλγόριθμοι Ελαχίστου Βαθμού
Αλγόριθμος Cuthill-Mckee
Sparse Matrix
Minimum Degree Algorithm
Cuthill – Mckee Algorithm

description: Στην εργασία αυτή παρουσιάζουμε αλγορίθμους αναδιάταξης σποραδικών μητρών που έχουν ως στόχο την ελαχιστοποίηση της καταστροφής των μηδενικών στοιχείων κατά την παραγοντοποίηση. Η σημαντικότητα διατήρησης των μηδενικών στοιχείων κατά την παραγοντοποίηση είναι και ο λόγος σύνθεσης της εργασίας αυτής. Αρχικά, στο πρώτο κεφάλαιο, θα συναντήσουμε κάποιες εισαγωγικές έννοιες όπως αυτή της σποραδικής μήτρας καθώς και αυτές της πλήρωσης και της αναδιάταξης. Οι έννοιες αυτές συνοδεύονται από παραδείγματα για την καλύτερη κατανόησή τους. Έπειτα, στο δεύτερο κεφάλαιο, κάνουμε τον διαχωρισμό των αλγορίθμων σε αλγορίθμους γενικών και τοπικών προσεγγίσεων. Οι αλγόριθμοι γενικών προσεγγίσεων προσπαθούν να μεταθέσουν την μήτρα σε κάποια μορφή έτσι ώστε η πλήρωση να φράσσεται ολικά. Αντίθετα, οι αλγόριθμοι τοπικών προσεγγίσεων ελαχιστοποιούν την πλήρωση σε κάθε στάδιο απαλοιφής. Στους αλγορίθμους γενικών προσεγγίσεων ανήκουν οι Cuthill-Mckee και ο ανάστροφός του, η μονόδρομη διαμέριση (one-way dissection) και η εμφωλιασμένη διαμέριση(nested dissection). Επιπλέον, παρουσιάζουμε τον πίνακα που συγκρίνει τους χρόνους αναδιάταξης και την συνολική αποθήκευση για τους αλγορίθμους, ανάστροφο Cuthill-Mckee, μονόδρομη και εγκιβωτισμένη διαμέρισης. Στην συνέχεια, αναφέρουμε τους αλγορίθμους των τοπικών προσεγγίσεων όπως είναι ο αλγόριθμος του Markowitz και ο αλγόριθμος των Tinney και Walker. Ο τελευταίος ονομάστηκε αλγόριθμος ελαχίστου βαθμού (minimum degree algorithm). Στο τρίτο κεφάλαιο επικεντρωνόμαστε στις τελευταίες έρευνες που έχουν γίνει στον αλγόριθμο ελαχίστου βαθμού. Δίνουμε τον ψευδοκώδικα του αλγορίθμου και παραθέτουμε τα προβλήματα που προκύπτουν κατά την εκτέλεση του καθώς και τους τρόπους επίλυσης τους. Τέλος, στο τέταρτο κεφάλαιο, παρουσιάζουμε έναν αλγόριθμο ελαχίστου βαθμού που χρησιμοποιεί το Matlab, τον Colamd και στο πέμπτο κεφάλαιο τα τεστ επίδοσης του ως προς τον χρόνο και την ποιότητα αναδιάταξης σε σχέση με άλλους αλγορίθμους του Matlab.
description: In this paper ordering algorithms for sparse matrices which aim to minimize the fill in during the factorization are presented. The importance of keeping zero elements during the factorization is the reason for composing this paper. To begin with, in the first chapter there are some introductory concepts such as the sparse matrix, the fill in and the ordering. They are accompanied by examples for better understanding. In the second chapter, we divide the algorithms in algorithms of global and local approaches. The algorithms of global approaches attempt to permute the matrix into some form which can globally bound the fill in. Conversely, the algorithms of local approaches minimize the fill in at each elimination step. Some algorithms of local approaches are the Cuthill – Mckee algorithm, the reverse Cuthill – Mckee algorithm, the one way dissection algorithm and the nested dissection algorithm. Furthermore, there is a table which compares the ordering time and the total storage for the algorithms reverse Cuthill – Mckee, one way dissection and nested dissection. Then, the algorithms of local approaches are mentioned like Markowitz algorithm and the Tinney and Walker algorithm which is called minimum degree algorithm. In the third chapter, the latest researches that have been conducted about the minimum degree algorithm are focused on. The pseudo-code of the algorithm as well as the solution to them are cited. In the fourth chapter, colamd, a minimum degree algorithm that matlab uses, is introduced. Finally, in the fifth chapter, the performance tests regarding the ordering time and the quality of ordering of this algorithm in relation to other algorithms, are mentioned.