Task-based randomized singular value decomposition and multidimensional scaling - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport Année : 2022

Task-based randomized singular value decomposition and multidimensional scaling

Décomposition en valeurs singulières randomisée et positionnement multidimensionel à base de tâches

Samuel Thibault

Résumé

The multidimensional scaling (MDS) is an important and robust algorithm for representing individual cases of a dataset out of their respective dissimilarities. However, heuristics, possibly trading-off with robustness, are often preferred in practice due to the potentially prohibitive memory and computational costs of the MDS. The recent introduction of random projection techniques within the MDS allowed it to be become competitive on larger test cases. The goal of this manuscript is to propose a high-performance distributed-memory MDS based on random projection for processing data sets of even larger size (up to one million items). We propose a task-based design of the whole algorithm and we implement it within an efficient software stack including state-of-the-art numerical solvers, runtime systems and communication layers. The outcome is the ability to efficiently apply robust MDS to large data sets on modern supercomputers. We assess the resulting algorithm and software stack to the point cloud visualization for analyzing distances between sequencesin metabarcoding.
Le positionnement multidimensionnel (MDS) est un algorithme important et robuste pour représenter les cas individuels d’un ensemble de données en fonction de leurs dissimilarités respectives. Cependant, les heuristiques, qui peuvent être un compromis avec la robustesse, sont souvent préférées en pratique en raison de sa consommation mémoire et de ses coûts potentiellement prohibitifs. L’introduction récente de techniques de projection aléatoire dans le MDS lui a permis de devenir compétitif sur des cas test plus importants. L’objectif de ce manuscrit est de proposer un MDS haute performance basé sur la projection aléatoire pour le traitement d’ensembles de données de taille encore plus grande (jusqu’à un million d’éléments). Nous proposons une conception de l’algorithme et nous l’implémentons dans une pile logicielle efficace, comprenant des solveurs numériques de pointe ainsi des systèmes d’exécution et des couches de communication optimisés. L’aboutissement de ce travail résultat est la capacité d’appliquer efficacement le MDS robuste à de grands ensembles de données sur des super-ordinateurs modernes. Nous évaluons l’algorithme et la pile logicielle résultants à la visualisation de nuages de points pour l’analyse des distances entre séquences de metabarcoding.
Fichier principal
Vignette du fichier
RR-9482 (1).pdf (1.22 Mo) Télécharger le fichier
RR-9482.pdf (1.22 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03773985 , version 1 (09-09-2022)
hal-03773985 , version 2 (22-09-2022)

Licence

Paternité

Identifiants

  • HAL Id : hal-03773985 , version 2

Citer

Emmanuel Agullo, Olivier Coulaud, Alexandre Denis, Mathieu Faverge, Alain Franc, et al.. Task-based randomized singular value decomposition and multidimensional scaling. [Research Report] RR-9482, Inria Bordeaux - Sud Ouest; Inrae - BioGeCo. 2022, pp.37. ⟨hal-03773985v2⟩
385 Consultations
301 Téléchargements

Partager

Gmail Facebook X LinkedIn More