ΑΛΓΟΡΙΘΜΟΙ ΕΠΙΛΥΣΗΣ ΑΡΑΙΩΝ ΓΡΑΜΜΙΚΩΝ ΣΥΣΤΗΜΑΤΩΝ ΜΕ ΑΜΕΣΕΣ ΜΕΘΟΔΟΥΣ ΚΑΙ Η ΥΛΟΠΟΙΗΣΗ ΤΟΥΣ

ALGORITHMS FOR SOLVING SPARCE LINEAR SYSTEMS WITH DIRECT METHODS AND THEIR IMPLEMENTATION (english)

  1. MSc thesis
  2. Καρύγιαννης, Νικόλαος
  3. Μεταπτυχιακές Σπουδές στα Μαθηματικά (ΜΣΜ)
  4. 26 September 2021 [2021-09-26]
  5. Ελληνικά
  6. 154
  7. Σωτηρόπουλος , Δημήτριος
  8. Ματζάκος , Νικόλαος
  9. αραιά γραμμικά συστήματα | άμεσοι μέθοδοι | Matlab
  10. 2
  11. 16
  12. 25 σχήματα-διαγράμματα , 7 πίνακες
    • Τα μαθηματικά μοντέλα πολλών πρακτικών προβλημάτων οδηγούν σε συστήματα γραμμικών αλγεβρικών εξισώσεων όπου ο πίνακας συντελεστών είναι μεγάλος και αραιός. Χαρακτηριστικά παραδείγματα είναι η επίλυση μερικών διαφορικών εξισώσεων με μεθόδους πεπερασμένης διαφοράς, προβλήματα γραμμικού προγραμματισμού, γραμμική παλινδρόμηση, και πολλές άλλες εφαρμογές. Η συγκεκριμένη διπλωματική́ εργασία επικεντρώνεται στην θεωρητική και εμπειρική ανάλυση αμέσων μεθόδων που χρησιμοποιούνται στην επίλυση αραιών γραμμικών συστημάτων και παράλληλα εξετάζει την αποδοτικότητα της κάθε μεθόδου τόσο από πλευράς υπολογιστικής πολυπλοκότητας όσο και χρονικής με την βοήθεια του υπολογιστικού εργαλείου Matlab. Στην αρχή́ της εργασίας παρουσιάζονται κάποιες βασικές έννοιες και ορισμοί́ από́ τον χώρο της Γραμμικής Άλγεβρας που χρησιμοποιούνται στα επόμενα κεφάλαια. Περιγράφουμε την δομή των αραιών πινάκων καθώς και τεχνικές αποθήκευσης που είναι βολικές για χρήση αμέσων μεθόδων. Στα επόμενα τρία κεφάλαια παρουσιάζονται αναλυτικά́ οι βασικές μέθοδοι επίλυσης αραιών γραμμικών συστημάτων. Ξεκινώντας από́ τις LU , QR παραγοντοποίηση και μέθοδος Cholesky. Αναλύονται τεχνικές και αλγόριθμοί προσανατολισμένες στην επίλυση αραιών συστημάτων που κύριο στόχο έχουν την διατήρηση της αραιότητας του πίνακα του συστήματος. Εντοπισμός μοναχικών στοιχείων, χρήση διατεμνουσών (transversals), στροφές Givens και ελαχιστοποίηση εύρους ζώνης. Εξετάζονται οι αλγόριθμοι Cuthill-McKee και Duff & Koster που βελτιώνουν την κατάσταση του πίνακα οδηγώντας σε συγκριτικά καλύτερα αποτελέσματα. Τέλος απομιμούνται και συγκρίνονται τα αποτελέσματα των παραπάνω μεθόδων μέσω Performance Profiles των Dolan & More τα οποία παρέχουν έναν ασφαλή τρόπο για να βγάλουμε συμπεράσματα για ποια είναι η καλύτερη μέθοδος έπειτα από́ εφαρμογή́ σε διαφορετικές κλάσεις πινάκων από τη συλλογή Harwell-Boeing.
    • Mathematical models of many practical problems lead to systems of linear algebraic equations where the table of factors is large and sparse. Typical examples are the solution of some differential equations with finite difference methods, linear programming problems, linear regression, and many other applications. This dissertation focuses on the theoretical and empirical analysis of direct methods used in solving sparse linear systems and at the same time examines the efficiency of each method both in terms of computational complexity and time with the help of the Matlab computing tool. At the beginning of the thesis are presented some basic concepts and definitions from the field of Linear Algebra that are used in the following chapters. We describe the structure of sparse tables as well as storage techniques that are convenient for the use of direct methods. The next three chapters present in detail the basic methods for solving sparse linear systems. Starting with LU, QR factorization and Cholesky method. Techniques and algorithms oriented to solve sparse systems are analyzed whose main goal is to maintain the sparsity of the system table. Detect solitary elements, use transversals, Givens turns and minimize bandwidth. The Cuthill-McKee and Duff & Koster algorithms that improve the state of the table leading to comparatively better results are examined. Finally, the results of the above methods are imitated and compared through Dolan & More Performance Profiles which provide a safe way to conclude what is the best method after application in different array classes from the Harwell-Boeing collection.
  14. Items in Apothesis are protected by copyright, with all rights reserved, unless otherwise indicated.