Institutional Repository
Technical University of Crete
EN  |  EL



My Space

Efficient parallel algoriths for tensor decompositions and implementation in distributed environments

Kolomvakis Christos

Simple record

Extent65 pagesel
TitleΑποδοτικοί παράλληλοι αλγόριθμοι για επεξεργασία τανυστών και υλοποίηση σε κατανεμημένα περιβάλλονταel
TitleEfficient parallel algoriths for tensor decompositions and implementation in distributed environments en
CreatorKolomvakis Christosen
CreatorΚολομβακης Χρηστοςel
Contributor [Thesis Supervisor]Liavas Athanasiosen
Contributor [Thesis Supervisor]Λιαβας Αθανασιοςel
Contributor [Committee Member]Karystinos Georgiosen
Contributor [Committee Member]Καρυστινος Γεωργιοςel
Contributor [Committee Member]Samoladas Vasilisen
Contributor [Committee Member]Σαμολαδας Βασιληςel
PublisherΠολυτεχνείο Κρήτηςel
PublisherTechnical University of Creteen
Academic UnitTechnical University of Crete::School of Electrical and Computer Engineeringen
Academic UnitΠολυτεχνείο Κρήτης::Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστώνel
Content SummaryΟι τανυστές είναι μαθηματικές δομές οι οποίες έχουν γίνει τα τελευταία χρόνια δημοφιλείς στα πεδία της επεξεργασίας σήματος και της μηχανικής μάθησης. Αυτό είναι λόγω της ικανότητάς τους να μπορούν να μοντελοποιούν τις σχέσεις και τις εξαρτήσεις μεταξύ πολλών αντικειμένων. Για ένα πλήρες data set, όπου δεν υπάρχουν στοιχεία που δεν μας είναι διαθέσιμα, οι αποσυνθέσεις τανυστών μας δίνουν την δυνατότητα να κάνουμε μοντελοποίηση των δεδομένων, ενώ κάποιες συγκεκριμένες αποσυνθέσεις μας δίνουν την δυνατότητα να πετύχουμε συμπίεση των δεδομένων. Για ένα data set στο οποίο λείπουν στοιχεία, μπορούμε να χρησιμοποιήσουμε αποσυνθέσεις έτσι ώστε να συμπεράνουμε στοιχεία που λείπουν. Οι τανυστές ωστόσο πάσχουν από την “κατάρα της διαστατικότητας”. Ο αριθμός των στοιχείων ενός τανυστή αυξάνεται εκθετικά με την τάξη του, και ως αποτέλεσμα, υπάρχει η ανάγκη για την ανάπτυξη αποδοτικών αλγορίθμων που πραγματοποιούν τις αποσυνθέσεις. Σε αυτήν την εργασία, θα επικεντρωθούμε στην αποσύνθεση CP ή PARAFAC. Αρχικά αναφέρουμε κάποιες έννοιες από την γραμμική άλγεβρα, και στην συνέχεια αναφερόμαστε σε προβλήματα ελαχίστων τετραγώνων για πίνακες. Μετά από μία εισαγωγή στην άλγεβρα τανυστών, παρουσιάζουμε την αποσύνθεση PARAFAC. Το πρόβλημα που καλούμαστε να αντιμετωπίσουμε είναι η επιτάχυνση ενός πολλαπλασιασμού πινάκων κατά την διάρκεια του αλγορίθμου αποσύνθεσης. Το γινόμενο είναι γνωστό στην βιβλιογραφία ως matricized—tensor Khatri—Rao product (MTTKRP) και αποτελεί το πιο απαιτητικό υπολογιστικά στάδιο του αλγορίθμου. Προς αυτό τον σκοπό, χρησιμοποιούμε μια δομή η οποία λέγεται dimension tree. Το δέντρο αποθηκεύει ποσότητες οι οποίες μπορούν να επαναχρησιμοποιηθούν στον αλγόριθμο αποσύνθεσης, με σκοπό την επιτάχυνση του υπολογισμού του MTTKRP. Τέλος, περιγράφουμε μια παράλληλη υλοποίηση σε κατανεμημένο περιβάλλον αυτού του αλγορίθμου, και παρουσιάζουμε αποτελέσματα για διάφορους τανυστές, και για ένα εύρος επεξεργαστών.el
Content SummaryTensors 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 ItemDiploma Worken
Date of Item2019-10-04-
Date of Publication2019-
SubjectΑποσυνθέσεις τανυστώνel
SubjectTensor decompositionsen
SubjectDistributed computingen
SubjectΠρογραμματισμός σε κατανεμημένα περιβάλλονταel
Bibliographic CitationΧρήστος Κολομβάκης, "Αποδοτικοί παράλληλοι αλγόριθμοι για επεξεργασία τανυστών και υλοποίηση σε κατανεμημένα περιβάλλοντα", Διπλωματική Εργασία, Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, Πολυτεχνείο Κρήτης, Χανιά, Ελλάς, 2019el
Bibliographic CitationChristos 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, 2019en

Available Files