A study of advanced computational methods
Authors: Παπαδόπουλος-Φιλέλης Χρήστος 
Published: August 2021

Στην παρούσα διατριβή προτείνονται νέοι γενικοί αραιοί προσεγγιστικοί αντίστροφοι πίνακες όπως και πολυεπίπεδες τεχνικές για την επίλυση γενικών αραιών γραμμικών συστημάτων. Τέτοια γραμμικά συστήματα προέρχονται κυρίως από την μέθοδο των Πεπερασμένων Διαφορών, των Πεπερασμένων στοιχείων καθώς και από τις Πολυπλεγματικές ή Πολυεπίπεδες μεθόδους. Ακόμη, δίνονται οι σχέσεις μεταξύ των αλγοριθμικών αυτών σχημάτων. Επίσης, μελετάται η ανάλυση σύγκλισης για τα προτεινόμενα σχήματα.Στο Κεφάλαιο 1, παρουσιάζονται οι βασικές μαθηματικές έννοιες για την αριθμητική επίλυση Μερικών Διαφορικών Εξισώσεων. Ακόμη, παρουσιάζονται Προσυντονισμένες επαναληπτικές μέθοδοι για την επίλυση γραμμικών συστημάτων συμπεριλαμβάνοντας και τις πολυπλεγματικές μεθόδους. Επίσης, παρουσιάζεται μια εισαγωγή στα περιβάλλοντα λογισμικού για μοντέρνα παράλληλα υπολογιστικά συστήματα.Στο Κεφάλαιο 2, παρουσιάζεται ο αλγόριθμος υπολογισμού της αραιότητας των προσεγγιστικών αντιστρόφων και παρατίθενται παρατειρήσεις για γενικευμένα σχήματα. Προτείνονται ο Γενικός Προσεγγιστικός Αραιός Αντίστροφος (GenAspI) πίνακας και ο Γενικός Παραγοντοποιημένος Προσεγγιστικός Αραιός Αντίστροφος (GenFAspI) πίνακας σε συνδυασμό με θέματα που αφορούν υλοποίηση αυτών. Επίσης, προτείνονται Τροποποιημένες μέθοδοι όπως ο Τροποποιημένος Γενικός Προσεγγιστικός Αραιός Αντίστροφος (MGenAspI) πίνακας και ο Τροποποιημένος Γενικός Παραγοντοποιημένος Προσεγγιστικός Αραιός Αντίστροφος (MGenFAspI) πίνακας, οι οποίοι βελτιώνουν την απόδοση. Επιπρόσθετα, παρουσιάζεται ένα σχήμα βελτιστοποίησης του προσεγγιστικού αντιστρόφου πίνακα, που διατηρεί τον αριθμό των μη μηδενικών στοιχείων σταθερό.Στο Κεφάλαιο 3, παρουσιάζονται ανοικτές προσυντονισμένες επαναληπτικές μέθοδοι. Η Ανοικτή Προσυντονισμένη μέθοδος Δι-Συζυγών Διευθύνσεων STABilized (EPBiCGSTAB), η Ανοικτή Προσυντονισμένη μέθοδος Γενικευμένου Ελαχίστου Υπολοίπου με επανεκκίνηση (EPGMRES(m)) καθώς και η Ανοικτή Προσυντονισμένη μέθοδος Induced Dimension Reduction (EPIDR(s)). Επιπλέον, παρουσιάζονται πολυπλεγματικές μέθοδοι (Multigrid methods) που βασίζονται σε προσεγγιστικούς αντιστρόφους, διαφορετικές στρατηγικές κύκλων και την μέθοδο Δυναμικής Υπερ/Υπο-Χαλάρωσης (Dynamic Over/Under Relaxation - DOUR). Περαιτέρω, παρουσιάζονται πολυπλεγματικά προσυντονισμένα σχήματα που βασίζονται σε προσεγγιστικούς αντιστρόφους πίνακες και επαναληπτικές μεθόδους του υποχώρου Krylov. Επίσης, παρατίθενται θέματα που αφορούν την υλοποίηση των μεθόδων αυτών.Στο Κεφάλαιο 4, παρουσιάζεται ένα νέο πολυεπίπεδο σχήμα που βασίζεται στον Τροποποιημένο Γενικό Παραγοντοποιημένο Προσεγγιστικό Αραιό Αντίστροφο (MGenFAspI) πίνακα και το με Ομαδοποιημένη Αναζήτηση κατά Πλάτος (Block Breadth First Search – BBFS) σχήμα αναδιάταξης. Ο Πολυεπίπεδος Αλγεβρικός Αναδρομικός Γενικός Προσεγγιστικός Αντίστροφος Επιλυτής (Multilevel Algebraic Recursive Generic Approximate Inverse Solver (MARGAIS)) αξιοποιεί την ιδέα της αναδιάταξης σε ομαδοποιημένα ανεξάρτητα συνόλα (Block Independent Sets) σε συνδυασμό με το σχήμα ομαδοποιημένης αντιστροφής (block inversion). Ο υπολογισμός της ιεραρχίας των επιπέδων του πολυεπίπεδου σχήματος χρησιμοποιεί την μερική ατελή παραγοντοποίηση LU-τύπου (partial Incomplete LU factorization). Επιπλέον, ο αλγόριθμός υλοποιείται μέσω μιας αναδρομικής διαδικασίας που απλοποιεί την οργάνωση των δεδομένων. Επίσης, παρατίθεται τεχνικές ελάττωσης των απαιτήσεων σε μνήμη καθώς και θέματα που αφορούν την υλοποίηση.Στο Κεφάλαιο 5, μελετάται η ευαισθησία του Βελτιστοποιημένου Ταινιωτού Γενικευμένου Προσεγγιστικού Αντιστρόφου Πίνακα (Optimized Banded Generalized Inverse Matrix - OBGAIM) και δίνονται θεωρητικές εκτιμήσεις. Ακόμη, δίνονται εκτιμήσεις για την ταχύτητα σύγκλισης και την υπολογιστική πολυπλοκότητα της Ανοικτής Προσυντονισμένης μεθόδου Συζυγών Διευθύνσεων (Explicit Preconditioned Conjugate Gradient - EPCG) που βασίζεται στον Γενικό Προσεγγιστικό Αραιό Αντίστροφο (GenAspI) πίνακα. Περαιτέρω, μελετάται η ταχύτητα σύγκλισης των πολυπλεγματικών μεθόδων σε συνδυασμό με τους Γενικούς Προσεγγιστικούς Αραιούς Αντιστρόφους (GenAspI) πίνακες. Επίσης, παρουσιάζονται οι τροποποιημένες συνθήκες Moore-Penrose (modified Moore-Penrose conditions) βασισμένες σε Ανοικτούς και Γενικούς Προσεγγιστικούς Αντιστρόφους. Δίνονται θεωρητικές εκτιμήσεις για την ποιότητα του Πολυεπίπεδου Αλγεβρικού Αναδρομικού Γενικού Προσεγγιστικού Αντιστρόφου Επιλυτή (MARGAIS).Στο Κεφάλαιο 6, παρουσιάζεται μια κλάση μεθόδων για την επίλυση μη γραμμικών προβλημάτων σε συνδυασμό με Πολυπλεγματικές μεθόδους που βασίζονται σε Γενικούς Προσεγγιστικούς Αραιούς Αντιστρόφους (GenAspI) πίνακες. Δίνεται η μέθοδος Inexact Newton και η μέθοδος Inexact Broyden με Backtracking, η κλάση των μεθόδων Inexact Jacobian-Free με Backtracking καθώς και η μέθοδος Full Approximation Scheme. Η απόδοση των μεθόδων αυτών βελτιώνεται με χρήση ενός νέου σχήματος “ενημέρωσης” βασισμένο στο σχήμα “Good Broyden Update”. Η ενημέρωση των προσεγγιστικών αντιστρόφων πινάκων, αντί του επαναϋπολογισμού σε κάθε βήμα, αυξάνει την απόδοση. Οι μη γραμμικές αυτές μέθοδοι σε συνδυασμό με Krylov επιταχυνόμενες πολυπλεγματικές μεθόδους, Γενικούς Προσεγγιστικούς Αραιούς Αντιστρόφους (GenAspI) πίνακες και το προτεινόμενο σχήμα “ενημέρωσης” παρουσιάζονται για την επίλυση μη γραμμικών προβλημάτων με “άσχημη συμπεριφορά” (ill-conditioned).Στο Κεφάλαιο 7, παρουσιάζονται υβριδικά Κλειστά στο χρόνο σχήματα βασισμένα σε Ανοικτούς Προσεγγιστικούς αντιστρόφους σε συνδυασμό με πολυπλεγματικές μεθόδους, για την επίλυση προβλημάτων αρχικών τιμών (Initial Value Problems - IVPs). Ακόμη, δίνονται ευσταθή σχήματα διακριτοποίησης Πεπερασμένων Διαφορών και Πεπερασμένων Στοιχείων, για την επίλυση προβλημάτων convection diffusion, βασισμένα σε upwind σχήματα και την μέθοδο Streamline Upwind Petrov-Galerkin (SUPG), αντίστοιχα. Περαιτέτω, μελετάται η επίδραση διαφόρων σχημάτων αναδιάταξης, όπως το Reverse Cuthil-McKee (RCM), το σχήμα Προσεγγιστικού Ελαχίστου Βαθμού (Approximate Minimum Degree - AMD) και το σχήμα Ομαδοποιημένης Αναζήτησης κατά Πλάτος (Block Breadth First Search - BBFS), στον ρυθμό αύξησης των μη μηδενικών στοιχείων του Τροποποιημένου Γενικού Παραγοντοποιημένου Προσεγγιστικού Αραιού Αντιστρόφου (MGenFAspI) πίνακα. Επίσης, σχολιάζεται η επιρροή επί της απόδοσης των προτεινομένων σχημάτων. Παρουσιάζεται, η αριθμητική επίλυση της ασυμπίεστης εξίσωσης Νavier-Stokes με χρήση της μεθόδου προβολής του Chorin, για το δισδιάστατο πρόβλημα lid driven cavity, σε συνδυασμό με τον Τροποποιημένο Γενικό Παραγοντοποιημένο Προσεγγιστικό Αραιό Αντίστροφο (MGenFAspI) πίνακα, το σχήμα αναδιάταξης Προσεγγιστικού Ελαχίστου Βαθμού (Approximate Minimum Degree - AMD) και την Ανοικτή Προσυντονισμένη μέθοδο Δι-Συζυγών Διευθύνσεων STABilized (EPBiCGSTAB). Ακόμη, παρατίθενται παρατηρήσεις για την υλοποίησης των σχημάτων αυτών.Στο Κεφάλαιο 8, παρουσιάζεται ο νέος Παράλληλος Γενικός Προσεγγιστικός Αραιός Αντίστροφος (PGenAspI) πίνακας, για συστήματα κοινής μνήμης (shared memory systems) χρησιμοποιώντας την νέα τεχνική της “λωρίδας” (“strip” approach). Ακόμη, παρουσιάζεται η παραλληλοποιημένη συναρτησιακά EPBiCGSTAB μέθοδος (PEPBiCGSTAB). Επίσης, προτείνεται ο παράλληλος τροποποιημένος περιορισμένος πολυπλεγματικός κύκλος τύπου V, ο οποίος με χρήση της μεθόδου PEPBiCGSTAB βασισμένη στον PGenAspI, αντικαθιστώντας τα επίπεδα εκείνα στην πολυπλεγματική μέθοδο, που δεν έχουν αρκετό παραλληλοποιήσιμο φόρτο. Με την αντικατάσταση αυτή διατηρείται η συμπεριφορά σύγκλισης της πολυπλεγματικής μεθόδου και ταυτόχρονα βελτιώνεται η παράλληλη απόδοση. Περαιτέρω, προτείνεται ο Κατανεμημένος Γενικός Προσεγγιστικός Αραιός Αντίστροφος (DGenAspI) πίνακας, που είναι βασίζεται σε μια αποπλεγμένη κατά στήλη στρατηγική απαλείφοντας την ενδιάμεση επικοινωνία μεταξύ των σταθμών επεξεργασίας (workstations) που αυξάνει την παράλληλη απόδοση. Επιπλέον, δίνεται σχήμα εξισορρόπησης του φόρτου (load balancing scheme) για τον υπολογισμό του DGenAspI πινακα, για πίνακα με μεγάλη τυπική απόκλιση μη μηδενικών στοιχείων ανά στήλη. Ακόμη, παρουσιάζεται η Υβριδική Παραλληλοποιημένη Προσυντονισμένη μέθοδος Συζυγών Διευθύνσεων Chronopoulos - Gear variant για συστήματα κατανεμημένης μνήμης (distributed memory systems) με κόμβους κοινής μνήμης (shared memory systems). Περαιτέρω, προτείνεται η κατά CUDA σχεδίαση του Παράλληλου “Ιχθυοσκελετοειδή” Βελτιστοποιημένου Ταινιωτού Γενικευμένου Προσεγγιστικού Αντιστρόφου Πεπερασμένων Στοιχείων Πίνακα (CU-PaFiBO-OBGAIFEM) σε συνδυασμό με την κατά CUDA σχεδίαση της Ανοικτής Προσυντονισμένης μεθόδου Δι-Συζυγών Διευθύνσεων STABilized (CU-PEPBiCGSTAB) για Κάρτες Επεξεργασίας Γραφικών Γενικού Σκοπού. Ακόμη, παρατίθενται παρατηρήσεις για την υλοποίηση των ανωτέρω σχημάτων.Στο Κεφάλαιο 9, παρουσιάζονται αριθμητικά αποτελέσματα για διάφορα πρότυπα προβλήματα ώστε να εκτιμηθεί η απόδοση, η αποδοτικότητα και η συμπεριφορά σύγκλισης των προτεινόμενων σχημάτων. Ακόμη, δίνονται συγκριτικά αποτελέσματα με μεθόδους που προτάθηκαν από άλλους ερευνητές. Επίσης, παρατίθεται παρατηρήσεις επι των αριθμητικών αποτελεσμάτων.Τέλος, παρουσιάζονται συμπερασματικές παρατηρήσεις καθώς και προτάσεις για μελλοντική έρευνα.