2022/07/21 by Hussam Al Daas, Daas, Hussam Al, Grey Ballard +7 · 1 citation
Computer Science · Mathematics · Physics and Astronomy · #Computational Physics and Python Applications #Distributed #FOS: Computer and information sciences #Parallel #Solar and Space Plasma Dynamics #Tensor decomposition and applications #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2207.10437
openalex publication_date 2022/07/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.