Communication Lower Bounds and Optimal Algorithms for Multiple Tensor-Times-Matrix Computation - Université de Paris - Faculté des Sciences Accéder directement au contenu
Article Dans Une Revue SIAM Journal on Matrix Analysis and Applications Année : 2024

Communication Lower Bounds and Optimal Algorithms for Multiple Tensor-Times-Matrix Computation

Résumé

Multiple Tensor-Times-Matrix (Multi-TTM) is a key computation in algorithms for computing and operating with the Tucker tensor decomposition, which is frequently used in multidimensional data analysis. We establish communication lower bounds that determine how much data movement is required (under mild conditions) to perform the Multi-TTM computation in parallel. The crux of the proof relies on analytically solving a constrained, nonlinear optimization problem. We also present a parallel algorithm to perform this computation that organizes the processors into a logical grid with twice as many modes as the input tensor. We show that with correct choices of grid dimensions, the communication cost of the algorithm attains the lower bounds and is therefore communication optimal. Finally, we show that our algorithm can significantly reduce communication compared to the straightforward approach of expressing the computation as a sequence of tensor-times-matrix operations when the input and output tensors vary greatly in size.
Fichier principal
Vignette du fichier
multi-TTM.pdf (627.61 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03950359 , version 1 (21-01-2023)

Licence

Paternité

Identifiants

Citer

Hussam Al Daas, Grey Ballard, Laura Grigori, Suraj Kumar, Kathryn Rouse. Communication Lower Bounds and Optimal Algorithms for Multiple Tensor-Times-Matrix Computation. SIAM Journal on Matrix Analysis and Applications, 2024, 45 (1), pp.450-477. ⟨10.1137/22M1510443⟩. ⟨hal-03950359⟩
81 Consultations
36 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More