2017/07/14 by Edgar Solomonik, Solomonik, Edgar, James Demmel +3 · 1 citation
Mathematics · Computer Science · #Tensor decomposition and applications #Parallel Computing and Optimization Techniques
paper · pdf · doi:10.48550/arxiv.1707.04618
We introduce a new theoretical framework for deriving lower bounds on data\nmovement in bilinear algorithms. Bilinear algorithms are a general\nrepresentation of fast algorithms for bilinear functions, which include\ncomputation of matrix multiplication, convolution, and symmetric tensor\ncontractions. A bilinear algorithm is described by three matrices. Our\ncommunication lower bounds are based on quantifying the minimal matrix ranks of\nmatching subsets of columns of these matrices. This infrastructure yields new\ncommunication lower bounds for symmetric tensor contraction algorithms, which\nprovide qualitative new insights. Tensor symmetry (invariance under permutation\nof modes) is common to many applications of tensor computations (e.g., tensor\nrepresentation of hypergraphs, analysis of high order moments in data, as well\nas tensors modelling interactions of electrons in computational chemistry).\nTensor symmetry enables reduction in representation size as well as arithmetic\ncost of contractions by factors that scale with the number of equivalent\npermutations. However, we derive lower bounds showing that these arithmetic\ncost and memory reductions can necessitate increases in data movement by\nfactors that scale with the size of the tensors.\n