A study of advanced computational methods: high performance generic sparse approximate inverse preconditioning and multilevel techniques

Abstract

In this thesis we introduce new generic sparse approximate inverse matrix techniques as well as multilevel techniques for solving general sparse linear systems. Such linear systems are derived mainly from the Finite Difference method, the Finite Element method, multigrid or multilevel methods. Moreover, the relationship of these algorithmic procedures is provided. Furthermore, the convergence analysis of the proposed schemes is studied.In Chapter 1, basic mathematical concepts for the numerical solution of Partial Differential Equations (PDEs) are introduced. Moreover, various preconditioned iterative methods for solving linear systems are introduced including the Multigrid method. Furthermore, an introduction to software environments for modern parallel computer systems is provided.In Chapter 2, the approximate inverse sparsity patterns algorithm and discussions on generic schemes are given. The Generic Approximate Sparse Inverse (GenAspI) matrix and the Generic Factored Approximate Sparse Inverse (GenFAspI) matrix are proposed along with implementation issues. Moreover, modified versions of such schemes, namely Modified GenApsI (MGenAspI) and Modified GenFAspI (MGenFAspI), that enhance performance, are also presented. Furthermore, an approximate inverse matrix refinement scheme that retains the number of nonzero elements is given.In Chapter 3, explicit preconditioned iterative methods are presented. The Explicit Preconditioned Bi-Conjugate Gradient STABilized (EPBiCGSTAB), the Explicit Preconditioned Generalized Minimum RESidual restarted (EPGMRES(m)) and the Explicit Preconditioned Induced Dimension Reduction (EPIDR(s)) are introduced. Moreover, multigrid methods based on approximate inverse matrices, various cycle schemes and the Dynamic Over/Under Relaxation (DOUR) scheme are also presented. Furthermore, multigrid preconditioning based on approximate inverse matrices and Krylov subspace iterative methods is presented. Discussions and implementation details are also provided.In Chapter 4, a novel multilevel scheme based on the Modified Generic Factored Approximate Sparse Inverse (MGenFAspI) matrix and a Block Breadth First Search reordering scheme is given. The Multilevel Algebraic Recursive Generic Approximate Inverse Solver (MARGAIS) exploits the idea of block independent set reordering along with a block inversion scheme. To compute the hierarchy of the multilevel scheme a partial Incomplete LU factorization is used. Moreover, the algorithm can be implemented using a recursive scheme, simplifying the data organization. Discussions concerning techniques to reduce memory requirements along with implementation details are also provided.In Chapter 5, the sensitivity of the Optimized Banded Generalized Approximate Inverse Matrix (OBGAIM) is studied and theoretical estimates are presented. Moreover, theoretical estimates on the convergence rate and computational complexity of the Explicit Preconditioned Conjugate Gradient method based on the Generic Approximate Sparse Inverse matrix are given. Furthermore, theoretical estimates on the convergence rate of the multigrid method in conjunction with the Generic Approximate Sparse Inverse matrix are also studied. The modified Moore-Penrose conditions based on Explicit and Generic Approximate Inverse schemes are also given. Theoretical estimates on the quality of the Multilevel Algebraic Recursive Generic Approximate Inverse Solver (MARGAIS) are provided.In Chapter 6, a class of methods for solving nonlinear problems in conjunction with the mutligrid method based on the Generic Approximate Sparse Inverse matrix is presented. The Inexact Newton and Inexact Broyden method with Backtracking, the Inexact Jacobian-Free type methods with Backtracking as well as Full Approximation Scheme are given. The performance of these schemes is improved using a novel updating scheme based on “Good Broyden Update” formula. The modified “Good Broyden Update” formula is used to update the approximate inverse matrices in each step, instead of recomputing them, resulting in improved performance. The aforementioned nonlinear methods in conjunction with the Krylov accelerated multigrid method, the Generic Approximate Sparse Inverse matrix and the proposed update formula for solving ill-conditioned nonlinear problems are also presented.In Chapter 7, applications including hybrid implicit time explicit approximate inverse matrix schemes, based on the mutligrid method, are provided for solving Initial Value Problems (IVPs). Moreover, stable Finite Difference and Finite Element discretization schemes for convection diffusion type problems, based on upwind schemes and the Streamline Upwind Petrov-Galerkin method, respectively, are given. Furthermore, the effect of various reordering schemes, such as Reverse Cuthil-McKee (RCM), Approximate Minimum Degree (AMD) and Block Breadth First Search (BBFS), on the growth of nonzero elements of the Modified Generic Factored Approximate Sparse Inverse (MGenFAspI) matrix is studied. The impact on the performance of the computation of the proposed schemes is also discussed. The numerical solution of the Incompressible Navier-Stokes equation, for the two-dimensional lid driven cavity problem, in conjunction with the MGenFAspI, Approximate Minimum Degree (AMD) reordering scheme and the Explicit Preconditioned Bi-Conjugate Gradient STABilized (EPBiCGSTAB) is provided, following the Chorin’s projection method approach. Implementation details and discussions for these schemes are also given.In Chapter 8, the parallel design of the Generic Approximate Sparse Inverse matrix, namely PGenAspI, for Shared memory parallel systems is provided, utilizing the novel “strip” approach. Moreover, the functional level parallelized Explicit Preconditioned Bi-Conjugate Gradient STABilized method (PEPBiCGSTAB) is presented. The parallel modified truncated V-Cycle multigrid method is given, which utilizes a Parallel Explicit Preconditioned Bi-Conjugate Gradient STABilized (PEPBiCGSTAB), based on PGenAspI, replacing the levels of the multigrid method that do not possess enough parallelizable computational work. Replacing those levels with PEPBiCGSTAB retains the convergence behavior of the multigrid method, while improving parallel performance. Moreover, the Distributed Generic Approximate Sparse Inverse (DGenAspI) matrix is presented, based on a decoupled column-wise approach which does not require any intermediate communications enhancing parallel performance. Furthermore, a load balancing scheme is given for computing the DGenAspI matrix in case of a matrix with high standard deviation of nonzero elements per column. The hybrid parallelized Preconditioned Conjugate Gradient Chronopoulos-Gear variant method is also provided, for Distributed memory parallel systems with multicore nodes. Furthermore, the CUDA Parallel Fishbone Optimized Banded Generalized Approximate Inverse Finite Element Matrix, along with CUDA Explicit Preconditioned Bi-Conjugate Gradient STABilized method, for General Purpose Graphics Processing Units, is given. Discussions along with implementation details are also presented.Finally, in Chapter 9, numerical results for various model problems, in order to assess the performance, efficiency and convergence behavior of the proposed schemes, are provided. Moreover, comparative results with schemes presented by other researchers are provided. Furthermore, discussions on the numerical results are given.Finally, concluding remarks along with suggestions for future work are presented.

Στην παρούσα διατριβή προτείνονται νέοι γενικοί αραιοί προσεγγιστικοί αντίστροφοι πίνακες όπως και πολυεπίπεδες τεχνικές για την επίλυση γενικών αραιών γραμμικών συστημάτων. Τέτοια γραμμικά συστήματα προέρχονται κυρίως από την μέθοδο των Πεπερασμένων Διαφορών, των Πεπερασμένων στοιχείων καθώς και από τις Πολυπλεγματικές ή Πολυεπίπεδες μεθόδους. Ακόμη, δίνονται οι σχέσεις μεταξύ των αλγοριθμικών αυτών σχημάτων. Επίσης, μελετάται η ανάλυση σύγκλισης για τα προτεινόμενα σχήματα.Στο Κεφάλαιο 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, παρουσιάζονται αριθμητικά αποτελέσματα για διάφορα πρότυπα προβλήματα ώστε να εκτιμηθεί η απόδοση, η αποδοτικότητα και η συμπεριφορά σύγκλισης των προτεινόμενων σχημάτων. Ακόμη, δίνονται συγκριτικά αποτελέσματα με μεθόδους που προτάθηκαν από άλλους ερευνητές. Επίσης, παρατίθεται παρατηρήσεις επι των αριθμητικών αποτελεσμάτων.Τέλος, παρουσιάζονται συμπερασματικές παρατηρήσεις καθώς και προτάσεις για μελλοντική έρευνα.