Ανάπτυξη Αλγορίθμου Επίλυσης Διοφαντικών Εξισώσεων Πινάκων (Master thesis)
Τσελεγκαρίδης, Σωκράτης
The current thesis focused on Control Systems, and in particular through a survey, demonstrates the usefulness of algebra and its functionality with Diophantine Equations in the analysis, synthesis and design for a wide range of different systems, such as: linear, non-linear, time varying, continuous time, discrete time, multivariable.
Additional, some methods of resolving Diophantine Equations of Matrices are analyzed for multivariable systems. Also, indicated the unnecessary use of processing resources for the zeros elements. At this point, an attempt is made with polynomials matrices to gain time from the execution of the calculation product, which ultimately leads to the Zero Elements (Z.E.) method and to the development of a corresponding algorithm where finally only the necessary (non zero) elements are used to reach the result A.B = C.
Furthermore, for the product of any two matrices A.B, the Z.E. O(n3-nz) method is compared with Strassen algorithm O(n2.807) and Williams O(n2.373), where n is the dimension of square matrix and z the number of zero elements in matrix A, and it is shown that the number of zeros in some cases, such as diagonal matrices, renders the Z.E. method more efficient than the others.
Finally, an Extended Zero Elements (E.Z.E.) method is expanded from the Zero Element method, where the extra gain of complexity is examined when zero elements is present not only in one, but in both matrices.
| Institution and School/Department of submitter: | Σχολή Τεχνολογικών Εφαρμογών / Τμήμα Μηχανικών Πληροφορικής |
| Keywords: | Συστήματα Αυτομάτου Ελέγχου;Διοφαντικές εξισώσεις πολυωνυμικών πινάκων;Πολλαπλασιασμός πινάκων;Smith μορφή;Διαγώνιος πίνακας;Control Systems;Diophantine equations;Matrices multiplication;Smith form;Diagonal matrix |
| Description: | Μεταπτυχιακή εργασία=Σχολή Τεχνολογικών Εφαρμογών=Τμήμα Ηλεκτρονικών Μηχανικών, 2019 (α/α10961) |
| URI: | http://195.251.240.227/jspui/handle/123456789/14456 |
| Item type: | masterThesis |
| General Description / Additional Comments: | Μεταπτυχιακή εργασία |
| Item language: | el |
| Item access scheme: | account |
| Institution and School/Department of submitter: | Σχολή Τεχνολογικών Εφαρμογών / Τμήμα Μηχανικών Πληροφορικής |
| Publication date: | 2019-04-18 |
| Bibliographic citation: | Τσελεγκαρίδης, Σ. (2019). Ανάπτυξη Αλγορίθμου Επίλυσης Διοφαντικών Εξισώσεων Πινάκων (Μεταπτυχιακή εργασία). Αλεξάνδρειο ΤΕΙ Θεσσαλονίκης |
| Abstract: | Η παρούσα διπλωματική εργασία ασχολείται με τα Συστήματα Αυτομάτου Ελέγχου, και συγκεκριμένα μέσω μιας επισκόπησης καταδεικνύεται η χρησιμότητα της άλγεβρας, η λειτουργικότητα και η ευκολία που προσφέρει με τις Διοφαντικές Εξισώσεις στην ανάλυση, σύνθεση και σχεδιασμό ενός μεγάλου φάσματος ετερόκλητων συστημάτων, όπως: γραμμικά / μη γραμμικά, χρονομεταβλητά / χρονοαμετάβλημα, συνεχούς χρόνου / διακριτού χρόνου, και μίας ή πολλών μεταβλητών.
Ακόμη, για τα πολυμεταβλητά συστήματα αναλύονται μερικές μέθοδοι επίλυσης Διοφαντικών Εξισώσεων Πινάκων και επισημαίνεται η άσκοπη χρησιμοποίηση επεξεργαστικών πόρων για τα μηδενικά στοιχεία που περιέχουν. Σε αυτόν τον άξονα γίνεται μία προσπάθεια μέσω πολυωνυμικών πινάκων να κερδηθεί χρόνος από την εκτέλεση του υπολογισμού γινομένου, κάτι που οδηγεί τελικά στην μέθοδο Μηδενικών Στοιχείων (Zero Elements), και την ανάπτυξη αντίστοιχου αλγορίθμου όπου από το σύνολο των επιμέρους πολλαπλασιασμών αφαιρούνται τα μηδενικά στοιχεία και έτσι υπολογίζονται μόνο οι απαραίτητοι όροι για να προκύψει το αποτέλεσμα Α.Β = C.
Επιπλέον, για γινόμενο δύο οποιονδήποτε πινάκων Α.Β γίνεται σύγκριση της μεθόδου Μηδενικών Στοιχείων Ο(n3–n.z) με τον αλγόριθμο Strassen O(n2.807) και της μεθόδου Williams O(n2.373), όπου n η διάσταση τετράγωνου πίνακα και z το πλήθος των μηδενικών στοιχείων του πίνακα Α, και αποδεικνύεται ότι το πλήθος των μηδενικών στοιχείων σε κάποιες περιπτώσεις, όπως οι διαγώνιοι πίνακες, κάνει την μέθοδο Μηδενικών Στοιχείων αποδοτικότερη έναντι των υπόλοιπων.
Τέλος, γίνεται επέκταση από την μέθοδο Μηδενικών Στοιχείων στην μέθοδο Εκτεταμένων Μηδενικών Στοιχείων (Extended Zero Elements – E.Z.E.) όπου εξετάζεται το επιπλέον κέρδος πολυπλοκότητας όταν υπάρχουν μηδενικά στοιχεία όχι μόνο στον έναν αλλά και στους δύο προς πολλαπλασιασμό πίνακες. The current thesis focused on Control Systems, and in particular through a survey, demonstrates the usefulness of algebra and its functionality with Diophantine Equations in the analysis, synthesis and design for a wide range of different systems, such as: linear, non-linear, time varying, continuous time, discrete time, multivariable. Additional, some methods of resolving Diophantine Equations of Matrices are analyzed for multivariable systems. Also, indicated the unnecessary use of processing resources for the zeros elements. At this point, an attempt is made with polynomials matrices to gain time from the execution of the calculation product, which ultimately leads to the Zero Elements (Z.E.) method and to the development of a corresponding algorithm where finally only the necessary (non zero) elements are used to reach the result A.B = C. Furthermore, for the product of any two matrices A.B, the Z.E. O(n3-nz) method is compared with Strassen algorithm O(n2.807) and Williams O(n2.373), where n is the dimension of square matrix and z the number of zero elements in matrix A, and it is shown that the number of zeros in some cases, such as diagonal matrices, renders the Z.E. method more efficient than the others. Finally, an Extended Zero Elements (E.Z.E.) method is expanded from the Zero Element method, where the extra gain of complexity is examined when zero elements is present not only in one, but in both matrices. |
| Advisor name: | Τζέκης, Παναγιώτης |
| Examining committee: | Τζέκης, Παναγιώτης |
| Publishing department/division: | Τμήμα Μηχανικών Πληροφορικής |
| Publishing institution: | teithe |
| Number of pages: | 71 |
| Appears in Collections: | Πτυχιακές Εργασίες |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Tselegkaridis.pdf | Μεταπτυχιακή εργασία | 2.05 MB | Adobe PDF | View/Open |
Please use this identifier to cite or link to this item:
This item is a favorite for 0 people.
http://195.251.240.227/jspui/handle/123456789/14456
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
