Institutional Repository
Technical University of Crete
Technical University of Crete
EN
|
EL
| URI | http://purl.tuc.gr/dl/dias/3867AFDB-00B1-4B4A-9A71-A2965C218584 | - |
| Identifier | https://doi.org/10.26233/heallink.tuc.83406 | - |
| Language | en | - |
| Extent | 65 pages | el |
| Title | Αποδοτικοί παράλληλοι αλγόριθμοι για επεξεργασία τανυστών και υλοποίηση σε κατανεμημένα περιβάλλοντα | el |
| Title | Efficient parallel algoriths for tensor decompositions and implementation in distributed environments | en |
| Creator | Kolomvakis Christos | en |
| Creator | Κολομβακης Χρηστος | el |
| Contributor [Thesis Supervisor] | Liavas Athanasios | en |
| Contributor [Thesis Supervisor] | Λιαβας Αθανασιος | el |
| Contributor [Committee Member] | Karystinos Georgios | en |
| Contributor [Committee Member] | Καρυστινος Γεωργιος | el |
| Contributor [Committee Member] | Samoladas Vasilis | en |
| Contributor [Committee Member] | Σαμολαδας Βασιλης | el |
| Publisher | Πολυτεχνείο Κρήτης | el |
| Publisher | Technical University of Crete | en |
| Academic Unit | Technical University of Crete::School of Electrical and Computer Engineering | en |
| Academic Unit | Πολυτεχνείο Κρήτης::Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών | el |
| Content Summary | Οι τανυστές είναι μαθηματικές δομές οι οποίες έχουν γίνει τα τελευταία χρόνια δημοφιλείς στα πεδία της επεξεργασίας σήματος και της μηχανικής μάθησης. Αυτό είναι λόγω της ικανότητάς τους να μπορούν να μοντελοποιούν τις σχέσεις και τις εξαρτήσεις μεταξύ πολλών αντικειμένων. Για ένα πλήρες data set, όπου δεν υπάρχουν στοιχεία που δεν μας είναι διαθέσιμα, οι αποσυνθέσεις τανυστών μας δίνουν την δυνατότητα να κάνουμε μοντελοποίηση των δεδομένων, ενώ κάποιες συγκεκριμένες αποσυνθέσεις μας δίνουν την δυνατότητα να πετύχουμε συμπίεση των δεδομένων. Για ένα data set στο οποίο λείπουν στοιχεία, μπορούμε να χρησιμοποιήσουμε αποσυνθέσεις έτσι ώστε να συμπεράνουμε στοιχεία που λείπουν. Οι τανυστές ωστόσο πάσχουν από την “κατάρα της διαστατικότητας”. Ο αριθμός των στοιχείων ενός τανυστή αυξάνεται εκθετικά με την τάξη του, και ως αποτέλεσμα, υπάρχει η ανάγκη για την ανάπτυξη αποδοτικών αλγορίθμων που πραγματοποιούν τις αποσυνθέσεις. Σε αυτήν την εργασία, θα επικεντρωθούμε στην αποσύνθεση CP ή PARAFAC. Αρχικά αναφέρουμε κάποιες έννοιες από την γραμμική άλγεβρα, και στην συνέχεια αναφερόμαστε σε προβλήματα ελαχίστων τετραγώνων για πίνακες. Μετά από μία εισαγωγή στην άλγεβρα τανυστών, παρουσιάζουμε την αποσύνθεση PARAFAC. Το πρόβλημα που καλούμαστε να αντιμετωπίσουμε είναι η επιτάχυνση ενός πολλαπλασιασμού πινάκων κατά την διάρκεια του αλγορίθμου αποσύνθεσης. Το γινόμενο είναι γνωστό στην βιβλιογραφία ως matricized—tensor Khatri—Rao product (MTTKRP) και αποτελεί το πιο απαιτητικό υπολογιστικά στάδιο του αλγορίθμου. Προς αυτό τον σκοπό, χρησιμοποιούμε μια δομή η οποία λέγεται dimension tree. Το δέντρο αποθηκεύει ποσότητες οι οποίες μπορούν να επαναχρησιμοποιηθούν στον αλγόριθμο αποσύνθεσης, με σκοπό την επιτάχυνση του υπολογισμού του MTTKRP. Τέλος, περιγράφουμε μια παράλληλη υλοποίηση σε κατανεμημένο περιβάλλον αυτού του αλγορίθμου, και παρουσιάζουμε αποτελέσματα για διάφορους τανυστές, και για ένα εύρος επεξεργαστών. | el |
| Content Summary | Tensors are mathematical objects that have recently become popular in the fields of machine learning and signal processing. This is due to their ability to describe multi-way relations and dependencies. For a complete data set, where we have no missing entries, tensor decompositions can help us model the data set, while others give us the potential to perform compression. For a data set with missing entries, we can use decompositions to infer missing values. Tensors however, suffer from the curse of dimensionality. The number of elements increases exponentially with respect to the order of a tensor. As a result, it is necessary to develop fast and scalable algorithms to perform these decompositions. In this thesis, we focus on the CP decomposition, or PARAFAC decomposition. We begin this work by introducing some definitions from linear algebra, followed by matrix least squares problems. These chapters are succeded by an introduction to tensor algebra, and a presentation of the PARAFAC decomposition. The problem we deal with in this thesis is the speeding of a matrix multiplication during the decomposition algorithm. This product is known in the bibliography as the matricized--tensor Khatri-Rao product (MTTKRP) and constitutes the computational bottleneck of the algorithm. To this end, we use a data structure called a dimension tree. The tree stores intermediate results that can be reused in the decomposition algorithm, in order to speed up the MTTKRP. Finally, we describe a parallel implementation in a distributed environment of this algorithm, and present results for various tensors and a range of processors. | en |
| Type of Item | Διπλωματική Εργασία | el |
| Type of Item | Diploma Work | en |
| License | http://creativecommons.org/licenses/by/4.0/ | en |
| Date of Item | 2019-10-04 | - |
| Date of Publication | 2019 | - |
| Subject | Αποσυνθέσεις τανυστών | el |
| Subject | Optimization | en |
| Subject | Tensor decompositions | en |
| Subject | Βελτιστοποίηση | el |
| Subject | Distributed computing | en |
| Subject | Προγραμματισμός σε κατανεμημένα περιβάλλοντα | el |
| Bibliographic Citation | Χρήστος Κολομβάκης, "Αποδοτικοί παράλληλοι αλγόριθμοι για επεξεργασία τανυστών και υλοποίηση σε κατανεμημένα περιβάλλοντα", Διπλωματική Εργασία, Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, Πολυτεχνείο Κρήτης, Χανιά, Ελλάς, 2019 | el |
| Bibliographic Citation | Christos Kolomvakis, "Efficient parallel algoriths for tensor decompositions and implementation in distributed environments ", Diploma Work, School of Electrical and Computer Engineering, Technical University of Crete, Chania, Greece, 2019 | en |
Copyright © DIAS 2013
