Πρωτότυπος Τίτλος:
Μελέτη υπολογιστικών και αλγοριθμικών μεθόδων για την επίλυση σύνθετων υπολογιστικών προβλημάτων
Συγγραφέας:
Λυπιτάκη, Αναστασία Δήμητρα Δανάη, Ηλίας
Επιβλέπων καθηγητής:
Αναγνωστόπουλος, Δημοσθένης
Περίληψη:
Στην παρούσα διδακτορική διατριβή, προτείνεται μια νέα τεχνική προσεγγιστικού αραιού ψευδοαντιστρόφου πίνακα για την επίλυση αραιών προβλημάτων ελαχίστων τετραγώνων. Για την επίλυση αυτών των προβλημάτων, χρησιμοποιούνται προσυντονισμένες επαναληπτικές μέθοδοι τόσο των υπερκαθορισμένων όσο και των υποκαθορισμένων γραμμικών συστημάτων. ΄Εχει σχεδιασθεί και υλοποιηθεί ένα νέο σχήμα προσυντονισμού του προσεγγιστικού ψευδοαντιστρόφου, το σχήμα του Γενικού Προσεγγιστικού Αραιού Ψευδοαντιστρόφου (GASP), το οποίο βασίζεται σε τροποποιημένες ατελείς παραγοντοποιήσεις QR με περιστροφές Givens. Οι τεχνικές αυτές προσαρμόζονται για παράλληλα υπολογιστικά περιβάλλοντα με την εισαγωγή του νέου παραλληλοποιημένου σχήματος του Γενικού Προσεγγιστικού Αραιού Ψευδοαντιστρόφου (ParGASP). Αυτό το σχήμα έχει αποδειχθεί ότι είναι εφαρμόσιμο για την επίλυση προβλημάτων που προέρχονται από διάφορες επιστημονικές περιοχές χρησιμοποιώντας σειριακά και παράλληλα υπολογιστικά συστήματα.
Στο Κεφάλαιο 1, παρουσιάζονται οι βασικές μαθηματικές έννοιες για την αριθμητική επίλυση αραιών γραμμικών συστημάτων ελαχίστων τετραγώνων. Επιπρόσθετα, παρουσιάζονται διάφορες προσυντονισμένες επαναληπτικές μέθοδοι για την επίλυση γραμμικών συστημάτων. Επιπλέον, πραγματοποιείται μια εισαγωγή στα περιβάλλοντα παράλληλου λογισμικού για σύγχρονα παράλληλα συστήματα υπολογιστών και συγκεκριμένα για το OpenMP. Επιπλέον, δίνεται μια σύντομη βιβλιογραφική ανασκόπηση για δύο εφαρμογές στην περιοχή της πρόβλεψης κίνησης και μηχανικής μάθησης εστιάζοντας σε προβλήματα μάθησης με επίβλεψη.
Στο Κεφάλαιο 2, παρουσιάζεται μια νέα κλάση τροποποιημένης ορθογώνιας παραγοντοποίησης με περιστροφές Givens. Προτείνεται μια κλάση του Γενικού Προσεγγιστικού Αραιού Ψευδοαντιστρόφου (GASP) πίνακα, που βασίζεται σε τροποποιημένη μέθοδο ανά γραμμή με χρήση κατωφλιού ατελούς Givens ορθογωνοποίησης, (mrTIGO). Τα κριτήρια φιλτραρίσματος για την ατελή παραγοντοποίηση QR έχουν τροποποιηθεί, για την βελτίωση της ποιότητας του ατελούς άνω τριγωνικού παράγοντα, καταργώντας τον περιορισμό στον αριθμό των μη μηδενικών στοιχείων ανά γραμμή. Υπολογίζεται ο καινοτόμος προσυντονισμένος πίνακας GASP για υπερκαθορισμένα και υποκαθορισμένα γραμμικά συστήματα, χρησιμοποιώντας μια «περιορισμένη» διαδικασία επίλυσης, βασιζόμενη στην μορφή αραιότητας των προσεγγιστικών ψευδοαντιστρόφων.
Στο Κεφάλαιο 3, παρουσιάζεται ο νέος Παράλληλος Γενικός Προσεγγιστικός Αραιός Ψευδοαντίστροφος (ParGASP) πίνακας, ακολουθώντας μια παράλληλη προσέγγιση υπολογισμού ανεξάρτητων στηλών, για παράλληλα συστήματα κοινής μνήμης. Ο ParGASP πίνακας μπορεί να χρησιμοποιηθεί σε συνδυασμό με τις παραλληλοποιημένες άμεσες προσυντονισμένες μεθόδους Συζυγών Διευθύνσεων για την επίλυση γραμμικών προβλημάτων ελαχίστων τετραγώνων.
Στο Κεφάλαιο 4, παρουσιάζονται οι άμεσες προσυντονισμένες επαναληπτικές μέθοδοι. Οι ΄Αμεσες Προσυντονισμένες μέθοδοι Συζυγών Διευθύνσεων προτείνονται για την επίλυση γραμμικών συστημάτων. Επιπρόσθετα, προτείνεται η άμεση προσυντονισμένη μέθοδος Συζυγών Διευθύνσεων Ελαχίστων Τετραγώνων (EPCGLS) σε συνδυασμό με τον Γενικό Προσεγγιστικό Αραιό Ψευδοαντίστροφο πίνακα για την επίλυση των υπερκαθορισμένων γραμμικών συστημάτων, καθώς και η παράλληλη παραλλαγή της για παράλληλα συστήματα κοινής μνήμης. Επιπλέον, παρουσιάζεται η άμεση προσυντονισμένη μέθοδος Συζυγών Διευθύνσεων Κανονικών Εξισώσεων (EPCGNE) σε συνδυασμό με το Γενικό Προσεγγιστικό Αραιό Ψευδοαντίστροφο πίνακα γραμμικών συστημάτων και η εκδοχή της για παράλληλα συστήματα με κοινή μνήμη.
Στο Κεφάλαιο 5, παρουσιάζονται οι τροποποιημένες συνθήκες Moore-Penrose, που βασίζονται στην τεχνική του Γενικού Προσεγγιστικού Αραιού Ψευδοαντιστρόφου πίνακα για τα υπερκαθορισμένα και τα υποκαθορισμένα γραμμικά συστήματα. ΄Εχει μελετηθεί η ευαισθησία του Γενικού Προσεγγιστικού Αραιού Ψευδοαντιστρόφου πίνακα και οι θεωρητικές εκτιμήσεις του πίνακα επανάληψης στα παραπάνω γραμμικά συστήματα.
Στο Κεφάλαιο 6, παρουσιάζονται δύο εφαρμογές για την επίλυση σύνθετων υπολογιστικών προβλημάτων. Λόγω της σημαντικότητας της, η πρόβλεψη της κυκλοφορίας έχει μελετηθεί εκτενώς για τον σχεδιασμό και την ανάπτυξη Ευφυών Συστημάτων Μεταφορών (ITS). Για την επίλυση του προβλήματος πρόβλεψης της κυκλοφορίας πολλαπλών βημάτων μεγάλης κλίμακας, προτείνεται μια προσέγγιση, χρησιμοποιώντας το Προσαρμοστικό μοντέλο Αυτοπαλινδρόμησης με βάση τις Συστάδες (ACSAR), που οδηγείται σε ένα υπερκαθορισμένο σύστημα, και επιλύεται με την ΄Αμεση Προσυντονισμένη μέθοδο Συζυγών Διευθύνσεων Ελαχίστων Τετραγώνων σε συνδυασμό με το Γενικό Προσεγγιστικό Αραιό Ψευδοαντίστροφο πίνακα. Επιπρόσθετα, παρουσιάζεται μια τεχνική για τη διαχείριση μιας κλάσης των προβλημάτων μάθησης με επίβλεψη (Supervised learning), με ιδιαίτερη έμφαση στα προβλήματα παλινδρόμησης, σε προβλήματα ταξινόμησης κειμένου με δυαδική και πολλών κλάσεων ταξινόμηση. Αυτή η νέα τεχνική του Προσυντονισμένου Προσεγγιστικού Αραιού Ψευδοαντιστρόφου (SAPP), χρησιμοποιεί την ΄Αμεση Προσυντονισμένη μέθοδο Συζυγών Διευθύνσεων Κανονικών Εξισώσεων σε συνδυασμό με το Γενικό Προσεγγιστικό Αραιό Ψευδοαντίστροφο πίνακα για την επίλυση υποκαθορισμένων συστημάτων.
Στο Κεφάλαιο 7, παρουσιάζονται αριθμητικά αποτελέσματα για διάφορα προβλήματα, προκειμένου να αξιολογηθεί η απόδοση και η συμπεριφορά σύγκλισης των νέων προτεινόμενων σχημάτων για αραιά προβλήματα ελαχίστων τετραγώνων και των αντίστοιχων παράλληλων εκδοχών τους. Επιπρόσθετα, δίνονται συγκριτικά αποτελέσματα με άλλες ευρέως καθιερωμένες μεθόδους. Επιπλέον, δίνονται αριθμητικά αποτελέσματα που αποδεικνύουν την εφαρμοσιμότητα και την αποδοτικότητα των νέων προτεινόμενων σχημάτων για την επίλυση του προβλήματος της πρόβλεψης κίνησης σε πολλαπλά βήματα και της μάθησης με επίβλεψη, ενώ παρατίθενται σχετικές παρατηρήσεις.
Τέλος, παρουσιάζονται συμπερασματικές παρατηρήσεις καθώς και προτάσεις για μελλοντική έρευνα.
Στο Κεφάλαιο 1, παρουσιάζονται οι βασικές μαθηματικές έννοιες για την αριθμητική επίλυση αραιών γραμμικών συστημάτων ελαχίστων τετραγώνων. Επιπρόσθετα, παρουσιάζονται διάφορες προσυντονισμένες επαναληπτικές μέθοδοι για την επίλυση γραμμικών συστημάτων. Επιπλέον, πραγματοποιείται μια εισαγωγή στα περιβάλλοντα παράλληλου λογισμικού για σύγχρονα παράλληλα συστήματα υπολογιστών και συγκεκριμένα για το OpenMP. Επιπλέον, δίνεται μια σύντομη βιβλιογραφική ανασκόπηση για δύο εφαρμογές στην περιοχή της πρόβλεψης κίνησης και μηχανικής μάθησης εστιάζοντας σε προβλήματα μάθησης με επίβλεψη.
Στο Κεφάλαιο 2, παρουσιάζεται μια νέα κλάση τροποποιημένης ορθογώνιας παραγοντοποίησης με περιστροφές Givens. Προτείνεται μια κλάση του Γενικού Προσεγγιστικού Αραιού Ψευδοαντιστρόφου (GASP) πίνακα, που βασίζεται σε τροποποιημένη μέθοδο ανά γραμμή με χρήση κατωφλιού ατελούς Givens ορθογωνοποίησης, (mrTIGO). Τα κριτήρια φιλτραρίσματος για την ατελή παραγοντοποίηση QR έχουν τροποποιηθεί, για την βελτίωση της ποιότητας του ατελούς άνω τριγωνικού παράγοντα, καταργώντας τον περιορισμό στον αριθμό των μη μηδενικών στοιχείων ανά γραμμή. Υπολογίζεται ο καινοτόμος προσυντονισμένος πίνακας GASP για υπερκαθορισμένα και υποκαθορισμένα γραμμικά συστήματα, χρησιμοποιώντας μια «περιορισμένη» διαδικασία επίλυσης, βασιζόμενη στην μορφή αραιότητας των προσεγγιστικών ψευδοαντιστρόφων.
Στο Κεφάλαιο 3, παρουσιάζεται ο νέος Παράλληλος Γενικός Προσεγγιστικός Αραιός Ψευδοαντίστροφος (ParGASP) πίνακας, ακολουθώντας μια παράλληλη προσέγγιση υπολογισμού ανεξάρτητων στηλών, για παράλληλα συστήματα κοινής μνήμης. Ο ParGASP πίνακας μπορεί να χρησιμοποιηθεί σε συνδυασμό με τις παραλληλοποιημένες άμεσες προσυντονισμένες μεθόδους Συζυγών Διευθύνσεων για την επίλυση γραμμικών προβλημάτων ελαχίστων τετραγώνων.
Στο Κεφάλαιο 4, παρουσιάζονται οι άμεσες προσυντονισμένες επαναληπτικές μέθοδοι. Οι ΄Αμεσες Προσυντονισμένες μέθοδοι Συζυγών Διευθύνσεων προτείνονται για την επίλυση γραμμικών συστημάτων. Επιπρόσθετα, προτείνεται η άμεση προσυντονισμένη μέθοδος Συζυγών Διευθύνσεων Ελαχίστων Τετραγώνων (EPCGLS) σε συνδυασμό με τον Γενικό Προσεγγιστικό Αραιό Ψευδοαντίστροφο πίνακα για την επίλυση των υπερκαθορισμένων γραμμικών συστημάτων, καθώς και η παράλληλη παραλλαγή της για παράλληλα συστήματα κοινής μνήμης. Επιπλέον, παρουσιάζεται η άμεση προσυντονισμένη μέθοδος Συζυγών Διευθύνσεων Κανονικών Εξισώσεων (EPCGNE) σε συνδυασμό με το Γενικό Προσεγγιστικό Αραιό Ψευδοαντίστροφο πίνακα γραμμικών συστημάτων και η εκδοχή της για παράλληλα συστήματα με κοινή μνήμη.
Στο Κεφάλαιο 5, παρουσιάζονται οι τροποποιημένες συνθήκες Moore-Penrose, που βασίζονται στην τεχνική του Γενικού Προσεγγιστικού Αραιού Ψευδοαντιστρόφου πίνακα για τα υπερκαθορισμένα και τα υποκαθορισμένα γραμμικά συστήματα. ΄Εχει μελετηθεί η ευαισθησία του Γενικού Προσεγγιστικού Αραιού Ψευδοαντιστρόφου πίνακα και οι θεωρητικές εκτιμήσεις του πίνακα επανάληψης στα παραπάνω γραμμικά συστήματα.
Στο Κεφάλαιο 6, παρουσιάζονται δύο εφαρμογές για την επίλυση σύνθετων υπολογιστικών προβλημάτων. Λόγω της σημαντικότητας της, η πρόβλεψη της κυκλοφορίας έχει μελετηθεί εκτενώς για τον σχεδιασμό και την ανάπτυξη Ευφυών Συστημάτων Μεταφορών (ITS). Για την επίλυση του προβλήματος πρόβλεψης της κυκλοφορίας πολλαπλών βημάτων μεγάλης κλίμακας, προτείνεται μια προσέγγιση, χρησιμοποιώντας το Προσαρμοστικό μοντέλο Αυτοπαλινδρόμησης με βάση τις Συστάδες (ACSAR), που οδηγείται σε ένα υπερκαθορισμένο σύστημα, και επιλύεται με την ΄Αμεση Προσυντονισμένη μέθοδο Συζυγών Διευθύνσεων Ελαχίστων Τετραγώνων σε συνδυασμό με το Γενικό Προσεγγιστικό Αραιό Ψευδοαντίστροφο πίνακα. Επιπρόσθετα, παρουσιάζεται μια τεχνική για τη διαχείριση μιας κλάσης των προβλημάτων μάθησης με επίβλεψη (Supervised learning), με ιδιαίτερη έμφαση στα προβλήματα παλινδρόμησης, σε προβλήματα ταξινόμησης κειμένου με δυαδική και πολλών κλάσεων ταξινόμηση. Αυτή η νέα τεχνική του Προσυντονισμένου Προσεγγιστικού Αραιού Ψευδοαντιστρόφου (SAPP), χρησιμοποιεί την ΄Αμεση Προσυντονισμένη μέθοδο Συζυγών Διευθύνσεων Κανονικών Εξισώσεων σε συνδυασμό με το Γενικό Προσεγγιστικό Αραιό Ψευδοαντίστροφο πίνακα για την επίλυση υποκαθορισμένων συστημάτων.
Στο Κεφάλαιο 7, παρουσιάζονται αριθμητικά αποτελέσματα για διάφορα προβλήματα, προκειμένου να αξιολογηθεί η απόδοση και η συμπεριφορά σύγκλισης των νέων προτεινόμενων σχημάτων για αραιά προβλήματα ελαχίστων τετραγώνων και των αντίστοιχων παράλληλων εκδοχών τους. Επιπρόσθετα, δίνονται συγκριτικά αποτελέσματα με άλλες ευρέως καθιερωμένες μεθόδους. Επιπλέον, δίνονται αριθμητικά αποτελέσματα που αποδεικνύουν την εφαρμοσιμότητα και την αποδοτικότητα των νέων προτεινόμενων σχημάτων για την επίλυση του προβλήματος της πρόβλεψης κίνησης σε πολλαπλά βήματα και της μάθησης με επίβλεψη, ενώ παρατίθενται σχετικές παρατηρήσεις.
Τέλος, παρουσιάζονται συμπερασματικές παρατηρήσεις καθώς και προτάσεις για μελλοντική έρευνα.
Ημερομηνία κατάθεσης:
2024-06-13
Γλώσσες Τεκμηρίου:
Αγγλικά
Θεματικές Κατηγορίες:
Ηλεκτρονικοί υπολογιστές. Επιστήμη των υπολογιστών
Λοιπά Θέματα:
Αλγόριθμοι - Επεξεργασία δεδομένων
Λέξεις-κλειδιά:
Αμεσος Γενικός Προσεγγιστικός Αραιός Ψευδό-αντίστροφος, Αμεσα σχήματα προσυντονισμού, Υποκαθορισμένα συστήματα, Υπερκαθορισμένα συστήματα, Προβλήματα Ελαχίστων Τετραγώνων μεγάλης κλίμακας
Περιγραφή:
214 σ.,εικ.,πίν.,διαγρ.,σχ.
Άδεια χρήσης:
Αναφορά Δημιουργού – Μη Εμπορική Χρήση – Όχι Παράγωγα Έργα 4.0
