# High-performance parallel algorithms for the Tucker decomposition of higher order sparse tensors

2 ROMA - Optimisation des ressources : modèles, algorithmes et ordonnancement
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : We investigate an efficient parallelization of a class of algorithms for the well-known Tucker decomposition of general $N$-dimensional sparse tensors. The targeted algorithms are iterative and use the alternating least squares method. At each iteration, for each dimension of an $N$-dimensional input tensor, the following operations are performed: (i) the tensor is multiplied with $(N - 1)$ matrices (TTM step); (ii) the product is then converted to a matrix; and (iii) a few leading left singular vectors of the resulting matrix are computed (SVD step) to update one of the matrices for the next TTM step. We propose an efficient parallelization of these algorithms for current supercomputers comprised of compute nodes, where each node is a multi-core system. We reformulate the computation of $N$ successive TTM-steps to increase the reuse of intermediate computation, which is of interest on its own. We discuss a set of preprocessing steps which takes all computational decisions out of the main iteration of the algorithm and provide an intuitive row-wise shared-memory parallelism for the TTM and SVD steps. We consider a coarse and a fine grain computational scheme, investigate their data dependencies, and identify efficient communication schemes. We demonstrate how the computation of singular vectors in the SVD step can be carried out efficiently following the TTM step. Finally, we develop a hybrid MPI-OpenMP based implementation of the overall algorithm and report speedup results on up to 2048 cores.
Type de document :
Rapport
[Research Report] RR-8801, Inria - Research Centre Grenoble – Rhône-Alpes. 2015
Domaine :

Littérature citée [32 références]

https://hal.inria.fr/hal-01219316
Contributeur : Equipe Roma <>
Soumis le : jeudi 22 octobre 2015 - 14:22:27
Dernière modification le : vendredi 20 avril 2018 - 15:44:27
Document(s) archivé(s) le : vendredi 5 mai 2017 - 12:52:39

### Fichier

RR-8801.pdf
Fichiers produits par l'(les) auteur(s)

### Identifiants

• HAL Id : hal-01219316, version 1

### Citation

Oguz Kaya, Bora Uçar. High-performance parallel algorithms for the Tucker decomposition of higher order sparse tensors. [Research Report] RR-8801, Inria - Research Centre Grenoble – Rhône-Alpes. 2015. 〈hal-01219316〉

### Métriques

Consultations de la notice

## 495

Téléchargements de fichiers
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.7454373836517334, "perplexity": 3588.9066171893705}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2019-13/segments/1552912201521.60/warc/CC-MAIN-20190318172016-20190318194016-00312.warc.gz"}