A study of computational and algorithmic techniques for solving complex computational problems

Abstract

In this doctoral thesis, a new sparse approximate pseudoinverse matrix technique for solving sparse least squares problems is introduced. In order to solve these least squares problems, preconditioned iterative methods are used for both overdetermined and underdetermined systems. A new approximate pseudoinverse preconditioning scheme, the Generic Approximate Sparse Pseudoinverse (GASP) schema, based on modified incomplete QR factorizations with Givens rotations, is designed and implemented. These techniques are adapted for parallel environments by introducing the new parallel Generic Sparse Approximate Pseudoinverse (ParGASP) schema. This scheme has been proved applicable for solving different types of problems from various scientific fields in sequential and parallel computational systems. In Chapter 1, basic mathematical concepts for the numerical solution of sparse linear Least Squares systems are introduced. Additionally, various preconditioned iterative methods for solving linear systems are discussed. Furthermore, an introduction to parallel software environments for modern parallel computer systems and specifically for OpenMP is provided. Moreover, a short literature review for two applications in the field of Traffic Forecasting and Machine Learning focusing on Supervised Learning problems is given. In Chapter 2, a new modified class of incomplete orthogonal factorization based on Givens rotations is introduced. The class of Generic Approximate Sparse Pseudoinverse (GASP) matrices based on Modified row-wise Threshold Incomplete Givens Orthogonalization (mrTIGO) is proposed. The filtering criteria for the Incomplete QR factorization have been modified to improve the quality of the incomplete upper triangular factor, by removing the restriction on the number of nonzero elements per row. The novel GASP preconditioner for overdetermined and underdetermined linear systems is computed, using a “restricted” solution process, based on approximate pseudoinverse sparsity patterns. In Chapter 3, the parallel design of the novel Generic Approximate Sparse Pseudoinverse Matrix, namely ParGASP matrix, following a parallel column-wise decoupled approach for shared memory parallel system is proposed. The ParGASP matrix can then be used in conjunction with Parallel Explicit Preconditioned Conjugated Gradient type methods for solving linear least squares problems. In Chapter 4, explicit preconditioned iterative methods are presented. The Explicit Preconditioned Conjugate Gradient type methods for solving linear least squares problems are introduced. Furthermore, the Explicit Preconditioned Conjugate Gradient Least Squares method in conjunction with GASP matrix for solving overdetermined linear systems is introduced along with its parallel variant for shared memory computer systems. Additionally, the Explicit Preconditioned Conjugate Gradient Method on the Normal Equations method based on GASP matrices for solving underdetermined linear systems is proposed along with its parallel variant for shared memory computer systems. In Chapter 5, the Modified Moore-Penrose conditions, based on Generic Approximate Sparse pseudoinverse technique for overdetermined and underdetermined linear systems are introduced. The sensitivity of the Generic Approximate Sparse Pseudoinverse matrix is studied and theoretical estimates of the iteration matrix for overdetermined and underdetermined linear systems are studied. In Chapter 6, two applications for solving complex computational problems are presented. Traffic forecasting has been extensively studied due to its importance for the design and development of Intelligent Transportation Systems (ITS). An approach for solving large-scale multi-stage traffic forecasting problem is proposed, by using the recently proposed Adaptive Cluster-based Sparse Auto-Regressive (ACSAR) model, leading to overdetermined linear system, which is solved using the Explicit Preconditioning Conjugate Gradient Least Square (EPCGLS) method in conjunction with the GASP matrix. Furthermore, a technique for handling a class of sparse supervised learning problems, specifically focusing on regression, binary and multi-class classification problems is presented. This new Sparse Approximate Pseudoinverse Preconditioning (SAPP) technique, uses the Explicit Preconditioning Conjugate Gradient on the Normal Equations (EPCGNE) method based on GASP matrix for solving underdetermined linear systems. In Chapter 7, numerical results are presented for various model problems in order to assess the performance and the convergence behavior of the proposed schemes for sparse least squares problems along with parallel results. Additionally, comparative results to other well established methods are provided. Moreover, numerical results indicating the applicability and efficiency of the proposed schemes for solving Multi-Step Ahead Traffic Forecasting problems and Supervised Learning Problems, are given along with discussions. Finally, concluding remarks along with future research directions are given.

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