Accès direct au contenu


logo du site ENS

Logo du site Ens Lyon

30 ans de l'ENS de Lyon

Accueil  >  ENS de Lyon > Recherche > Soutenances de thèses > Thèses en sc. exactes et exp.


High Performance Parallel Algorithms for Tensor Decompositions - Algorithmes Parallèles pour les Decompositions

Soutenance de thèse
Soutenance de thèse de M. Oguz KAYA du LIP sous la direction de M. Yves ROBERT
15 septembre 2017

Lieu(x) :

Site Monod - 46 allée d'Italie
Amphi B - Site Monod - ENS de Lyon
Tensor factorization has been increasingly used to analyze high-dimensional low- rank data of massive scale in numerous application domains, including recommender systems, graph analytics, health-care data analysis, signal processing, chemometrics, and many others. In these applications, efficient computation of tensor decompositions is crucial to be able to handle such datasets of high volume.

The main focus of this thesis is on efficient decomposition of high dimensional sparse tensors, with hundreds of mil- lions to billions of nonzero entries, which arise in many emerging big data applications. We achieve this through three major approaches.
In the first approach, we provide distributed memory parallel algorithms with effi- cient point-to-point communication scheme for reducing the communication cost. These algorithms are agnostic to the partitioning of tensor elements and low rank decompo- sition matrices, which allow us to investigate effective partitioning strategies for mi- nimizing communication cost while establishing computational load balance. We use hypergraph-based techniques to analyze computational and communication require- ments in these algorithms, and employ hypergraph partitioning tools to find suitable partitions that provide much better scalability.

Second, we investigate effective shared memory parallelizations of these algorithms. Here, we carefully determine unit computational tasks and their dependencies, and express them using a proper data structure that exposes the parallelism underneath.
Third, we introduce a tree-based computational scheme that carries out expensive operations (involving the multiplication of the tensor with a set of vectors or ma- trices, found at the core of these algorithms) faster by factoring out and storing com- mon partial results and effectively re-using them. With this computational scheme, we asymptotically reduce the number of tensor-vector and -matrix multiplications for high dimensional tensors, and thereby render computing tensor decompositions significantly cheaper both for sequential and parallel algorithms.

Finally, we diversify this main course of research with two extensions on similar themes. The first extension involves applying the tree-based computational framework to computing dense tensor decompositions, with an in-depth analysis of computational complexity and methods to find optimal tree structures minimizing the computational cost. The second work focuses on adapting effective communication and partitioning
3schemes of our parallel sparse tensor decomposition algorithms to the widely used non- negative matrix factorization problem, through which we obtain significantly better parallel scalability over the state of the art implementations.
We point out that all theoretical results in the thesis are nicely corroborated by parallel experiments on both shared-memory and distributed-memory platforms. With these fast algorithms as well as their tuned implementations for modern HPC archi- tectures, we render tensor and matrix decomposition algorithms amenable to use for analyzing massive scale datasets.

Retour au haut de la page

Pôle Recherche
Mise à jour le 6 septembre 2017
Ens de Lyon
15 parvis René Descartes - BP 7000 69342 Lyon Cedex 07 - FRANCE
Tél. : Site René Descartes (siège) : +33 (0) 4 37 37 60 00 / Site Jacques Monod : +33 (0) 4 72 72 80 00