Επιτάχυνση της οικογένειας αλγορίθμων Spike μέσω τεχνικών επίλυσης γραμμικών συστημάτων με πολλά δεξιά μέλη
Στη παρούσα διπλωματική εργασία ασχολούμαστε με την αποδοτική επίλυση ταινιακών και γενικών, αραιών γραμμικών συστημάτων σε παράλληλες αρχιτεκτονικές μέσω της οικογένειας αλγορίθμων Spike. Ζητούμενο είναι η βελτίωση (μείωση) του χρόνου επίλυσης μέσω τεχνικών επίλυσης γραμμικών συστημάτων με πολλά...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | Greek |
| Published: |
2015
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/10889/8331 |
| id |
nemertes-10889-8331 |
|---|---|
| record_format |
dspace |
| spelling |
nemertes-10889-83312022-09-06T05:14:12Z Επιτάχυνση της οικογένειας αλγορίθμων Spike μέσω τεχνικών επίλυσης γραμμικών συστημάτων με πολλά δεξιά μέλη Καλαντζής, Βασίλειος Γαλλόπουλος, Ευστράτιος Kalantzis, Vasileios Γαλλόπουλος, Ευστράτιος Ζαρολιάγκης, Χρήστος Μπουντουβής, Ανδρέας Αλγόριθμος Spike Επίλυση γραμμικών συστημάτων Προρυθμιστές Ταινιακά μητρώα Μέθοδοι αναδιάταξης Πολλά δεξιά μέλη Αραιά μητρώα Επαναληπτικές μέθοδοι Υπόχωρος Krylov Παράλληλοι υπολογισμοί Υπολογισμοί υψηλών επιδόσεων 519.6 Spike algorithm Solution of linear systems Preconditioners Banded matrices Reordering methods Multiple right-hand sides Sparse matrices Iterative methods Krylov subspace Parallel computing High performance computing Στη παρούσα διπλωματική εργασία ασχολούμαστε με την αποδοτική επίλυση ταινιακών και γενικών, αραιών γραμμικών συστημάτων σε παράλληλες αρχιτεκτονικές μέσω της οικογένειας αλγορίθμων Spike. Ζητούμενο είναι η βελτίωση (μείωση) του χρόνου επίλυσης μέσω τεχνικών επίλυσης γραμμικών συστημάτων με πολλά δεξιά μέλη. Πιο συγκεκριμένα, επικεντρωνόμαστε στην επίλυση της εξίσωσης μητρώου $AX=F$ (1) όπου $A\in \mathbb{R}^{n\times n}$ είναι το μητρώο συντελεστών και το οποίο είναι αραιό ή/και ταινιακό, $F\in \mathbb{R}^{n\times s}$ είναι ένα μητρώο με $s$ στήλες το οποίο ονομάζεται μητρώο δεξιών μελών και $X\in \mathbb{R}^{n\times s}$ είναι η λύση του συστήματος. Μια σημαντική μέθοδος για την παράλληλη επίλυση της παραπάνω εξίσωσης, είναι η μέθοδος Spike και οι παραλλαγές της. Η μέθοδος Spike βασίζεται στη τεχνική διαίρει και βασίλευε και αποτελείται από δυο φάσεις: α) επίλυση ανεξάρτητων υπο-προβλημάτων τοπικά σε κάθε επεξεργαστή, και β) επίλυση ενός πολύ μικρότερου προβλήματος το οποίο απαιτεί επικοινωνία μεταξύ των επεξεργαστών. Οι δύο φάσεις συνδυάζονται ώστε να παραχθεί η τελική λύση $X$. Η συνεισφορά της διπλωματικής εργασίας έγκειται στην επιτάχυνση της οικογένειας αλγορίθμων Spike για την επίλυση της εξίσωσης (1) μέσω της μελέτης, το σχεδιασμό και την υλοποίηση νέων, περισσότερο αποδοτικών αλγοριθμικών σχημάτων τα οποία βασίζονται σε τεχνικές επίλυσης γραμμικών συστημάτων με πολλά δεξιά μέλη. Αυτά τα νέα αλγοριθμικά σχήματα έχουν ως στόχο τη βελτίωση του χρόνου επίλυσης των γραμμικών συστημάτων καθώς και άλλα οφέλη όπως η αποδοτικότερη χρήση μνήμης. In this thesis we focus on the efficient solution of general banded and general sparse linear systems on parallel architectures by exploiting the Spike family of algorithms. The equation of interest can be written in matrix form as $ AX = F $ (1) where $ A \ in \ mathbb {R} ^ {n \ times n} $ is the coefficient matrix, which is also sparse and / or banded, $ F \ in \ mathbb {R} ^ {n \ times s} $ is a matrix with $ s $ columns called matrix of the right hand sides and $ X \ in \ mathbb {R} ^ {n \ times s} $ is the solution of the system. An important method for the parallel solution of the above equation, is the Spike method and its variants. The Spike method is based on the divide and conquer technique and consists of two phases: a) solution of local, independent sub-problems in each processor, and b) solution of a much smaller problem which requires communication among the processors. The two phases are combined to produce the final solution $ X $. The contribution of this thesis is the acceleration of the Spike method for the solution of the matrix equation in (1) by studying, designing and implementing new, more efficient algorithmic schemes which are based on techniques used for the effective solution of linear systems with multiple right hand sides. These new algorithmic schemes were designed to improve the solving time of the linear systems as well as to provide other benefits such as more efficient use of memory. 2015-02-05T16:18:50Z 2015-02-05T16:18:50Z 2014-07-30 2015-02-05 Thesis http://hdl.handle.net/10889/8331 gr 0 application/pdf |
| institution |
UPatras |
| collection |
Nemertes |
| language |
Greek |
| topic |
Αλγόριθμος Spike Επίλυση γραμμικών συστημάτων Προρυθμιστές Ταινιακά μητρώα Μέθοδοι αναδιάταξης Πολλά δεξιά μέλη Αραιά μητρώα Επαναληπτικές μέθοδοι Υπόχωρος Krylov Παράλληλοι υπολογισμοί Υπολογισμοί υψηλών επιδόσεων 519.6 Spike algorithm Solution of linear systems Preconditioners Banded matrices Reordering methods Multiple right-hand sides Sparse matrices Iterative methods Krylov subspace Parallel computing High performance computing |
| spellingShingle |
Αλγόριθμος Spike Επίλυση γραμμικών συστημάτων Προρυθμιστές Ταινιακά μητρώα Μέθοδοι αναδιάταξης Πολλά δεξιά μέλη Αραιά μητρώα Επαναληπτικές μέθοδοι Υπόχωρος Krylov Παράλληλοι υπολογισμοί Υπολογισμοί υψηλών επιδόσεων 519.6 Spike algorithm Solution of linear systems Preconditioners Banded matrices Reordering methods Multiple right-hand sides Sparse matrices Iterative methods Krylov subspace Parallel computing High performance computing Καλαντζής, Βασίλειος Επιτάχυνση της οικογένειας αλγορίθμων Spike μέσω τεχνικών επίλυσης γραμμικών συστημάτων με πολλά δεξιά μέλη |
| description |
Στη παρούσα διπλωματική εργασία ασχολούμαστε με την αποδοτική επίλυση ταινιακών και γενικών, αραιών γραμμικών συστημάτων σε παράλληλες αρχιτεκτονικές μέσω της οικογένειας αλγορίθμων Spike. Ζητούμενο είναι η
βελτίωση (μείωση) του χρόνου επίλυσης μέσω τεχνικών επίλυσης γραμμικών συστημάτων με πολλά δεξιά μέλη.
Πιο συγκεκριμένα, επικεντρωνόμαστε στην επίλυση της εξίσωσης μητρώου $AX=F$ (1) όπου $A\in \mathbb{R}^{n\times n}$ είναι το μητρώο συντελεστών και το οποίο είναι αραιό
ή/και ταινιακό, $F\in \mathbb{R}^{n\times s}$ είναι ένα μητρώο με $s$ στήλες το οποίο ονομάζεται μητρώο δεξιών μελών και $X\in \mathbb{R}^{n\times s}$
είναι η λύση του συστήματος. Μια σημαντική μέθοδος για την παράλληλη επίλυση της παραπάνω εξίσωσης, είναι η
μέθοδος Spike και οι παραλλαγές της. Η μέθοδος Spike βασίζεται στη τεχνική διαίρει και βασίλευε και αποτελείται από δυο
φάσεις: α) επίλυση ανεξάρτητων υπο-προβλημάτων τοπικά σε κάθε επεξεργαστή, και β) επίλυση ενός πολύ μικρότερου προβλήματος το οποίο απαιτεί επικοινωνία
μεταξύ των επεξεργαστών. Οι δύο φάσεις συνδυάζονται ώστε να παραχθεί η τελική λύση $X$.
Η συνεισφορά της διπλωματικής εργασίας έγκειται στην επιτάχυνση της οικογένειας αλγορίθμων Spike για την επίλυση της εξίσωσης (1) μέσω
της μελέτης, το σχεδιασμό και την υλοποίηση νέων, περισσότερο αποδοτικών αλγοριθμικών σχημάτων
τα οποία βασίζονται σε τεχνικές επίλυσης γραμμικών συστημάτων με πολλά δεξιά μέλη. Αυτά τα νέα αλγοριθμικά σχήματα έχουν ως στόχο τη βελτίωση του χρόνου
επίλυσης των γραμμικών συστημάτων καθώς και άλλα οφέλη όπως η αποδοτικότερη χρήση μνήμης. |
| author2 |
Γαλλόπουλος, Ευστράτιος |
| author_facet |
Γαλλόπουλος, Ευστράτιος Καλαντζής, Βασίλειος |
| format |
Thesis |
| author |
Καλαντζής, Βασίλειος |
| author_sort |
Καλαντζής, Βασίλειος |
| title |
Επιτάχυνση της οικογένειας αλγορίθμων Spike μέσω τεχνικών επίλυσης γραμμικών συστημάτων με πολλά δεξιά μέλη |
| title_short |
Επιτάχυνση της οικογένειας αλγορίθμων Spike μέσω τεχνικών επίλυσης γραμμικών συστημάτων με πολλά δεξιά μέλη |
| title_full |
Επιτάχυνση της οικογένειας αλγορίθμων Spike μέσω τεχνικών επίλυσης γραμμικών συστημάτων με πολλά δεξιά μέλη |
| title_fullStr |
Επιτάχυνση της οικογένειας αλγορίθμων Spike μέσω τεχνικών επίλυσης γραμμικών συστημάτων με πολλά δεξιά μέλη |
| title_full_unstemmed |
Επιτάχυνση της οικογένειας αλγορίθμων Spike μέσω τεχνικών επίλυσης γραμμικών συστημάτων με πολλά δεξιά μέλη |
| title_sort |
επιτάχυνση της οικογένειας αλγορίθμων spike μέσω τεχνικών επίλυσης γραμμικών συστημάτων με πολλά δεξιά μέλη |
| publishDate |
2015 |
| url |
http://hdl.handle.net/10889/8331 |
| work_keys_str_mv |
AT kalantzēsbasileios epitachynsētēsoikogeneiasalgorithmōnspikemesōtechnikōnepilysēsgrammikōnsystēmatōnmepolladexiamelē |
| _version_ |
1799945011357286400 |
