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

DOI10.1137/22M1510443arXiv2207.10437WikidataQ128541178 ScholiaQ128541178MaRDI QIDQ6154935FDOQ6154935

Authors: Hussam al Daas, Grey Ballard, Laura Grigori 

Publication date: 16 February 2024

Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Abstract: 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 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.

Full work available at URL: https://arxiv.org/abs/2207.10437

zbMATH Keywords

parallel algorithmstensor computationscommunication lower boundsHBL-inequalitiesmulti-TTM

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parallel algorithms in computer science (68W10) Distributed algorithms (68W15)

Cites Work

• TuckerMPI: a parallel C++/MPI software package for large-scale data compression via the Tucker tensor decomposition
• Tensor Decompositions and Applications
• A Multilinear Singular Value Decomposition
• An inequality related to the isoperimetric inequality
• Finite bounds for Hölder-Brascamp-Lieb multilinear inequalities
• Accelerating alternating least squares for tensor decomposition by pairwise perturbation
• Communication lower bounds for distributed-memory matrix multiplication
• Communication lower bounds and optimal algorithms for numerical linear algebra
• Randomized Algorithms for Low-Rank Tensor Decompositions in the Tucker Format
• Low-rank Tucker approximation of a tensor from streaming data
• Communication lower bounds of bilinear algorithms for symmetric tensor contractions

This page was built for publication: Communication Lower Bounds and Optimal Algorithms for Multiple Tensor-Times-Matrix Computation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6154935)