The movement of data (communication) between levels of a memory hierarchy, or
between parallel processors on a network, can greatly dominate the cost of
computation, so algorithms that minimize communication are of interest.
Motivated by this, attainable lower bounds for the amount of communication
required by algorithms were established by several groups for a variety of
algorithms, including matrix computations. Prior work of
Ballard-Demmel-Holtz-Schwartz relied on a geometric inequality of Loomis and
Whitney for this purpose. In this paper the general theory of discrete
multilinear Holder-Brascamp-Lieb (HBL) inequalities is used to establish
communication lower bounds for a much wider class of algorithms. In some cases,
algorithms are presented which attain these lower bounds.
Several contributions are made to the theory of HBL inequalities proper. The
optimal constant in such an inequality for torsion-free Abelian groups is shown
to equal one whenever it is finite. Bennett-Carbery-Christ-Tao had
characterized the tuples of exponents for which such an inequality is valid as
the convex polyhedron defined by a certain finite list of inequalities. The
problem of constructing an algorithm to decide whether a given inequality is on
this list, is shown to be equivalent to Hilbert's Tenth Problem over the
rationals, which remains open. Nonetheless, an algorithm which computes the
polyhedron itself is constructed.