Communication Lower Bounds for Matricized Tensor Times Khatri-Rao\n Product

2017/08/24 by Grey Ballard, Ballard, Grey, Nicholas Knight +3 · 1 citation
Computer Science · Mathematics · #Distributed #FOS: Computer and information sciences #Interconnection Networks and Systems #Parallel #Parallel Computing and Optimization Techniques #Tensor decomposition and applications #and Cluster Computing (cs.DC)

paper · pdf · doi:10.48550/arxiv.1708.07401

openalex publication_date 2017/08/24 · openalex created_date 2022/09/26 · openalex updated_date 2026/07/28

Abstract

The matricized-tensor times Khatri-Rao product computation is the typical\nbottleneck in algorithms for computing a CP decomposition of a tensor. In order\nto develop high performance sequential and parallel algorithms, we establish\ncommunication lower bounds that identify how much data movement is required for\nthis computation in the case of dense tensors. We also present sequential and\nparallel algorithms that attain the lower bounds and are therefore\ncommunication optimal. In particular, we show that the structure of the\ncomputation allows for less communication than the straightforward approach of\ncasting the computation as a matrix multiplication operation.\n

Cited by

• Minimizing Communication for Parallel Symmetric Tensor Times Same Vector Computation

Related

• Communication Lower Bounds and Optimal Algorithms for Multiple Tensor-Times-Matrix Computation
• Minimizing Communication for Parallel Symmetric Tensor Times Same Vector Computation
• Shared Memory Parallelization of MTTKRP for Dense Tensors
• Parallel Nonnegative CP Decomposition of Dense Tensors
• On Fast Computation of Gradients for CANDECOMP/PARAFAC Algorithms