  We introduce a new theoretical framework for deriving lower bounds on data
movement in bilinear algorithms. Bilinear algorithms are a general
representation of fast algorithms for bilinear functions, which include
computation of matrix multiplication, convolution, and symmetric tensor
contractions. A bilinear algorithm is described by three matrices. Our
communication lower bounds are based on quantifying the minimal matrix ranks of
matching subsets of columns of these matrices. This infrastructure yields new
communication lower bounds for symmetric tensor contraction algorithms, which
provide qualitative new insights. Tensor symmetry (invariance under permutation
of modes) is common to many applications of tensor computations (e.g., tensor
representation of hypergraphs, analysis of high order moments in data, as well
as tensors modelling interactions of electrons in computational chemistry).
Tensor symmetry enables reduction in representation size as well as arithmetic
cost of contractions by factors that scale with the number of equivalent
permutations. However, we derive lower bounds showing that these arithmetic
cost and memory reductions can necessitate increases in data movement by
factors that scale with the size of the tensors.
