Multi-dimensional arrays, or tensors, are fundamental objects in computational science for their ability to store multi-dimensional data and to encode bilinear forms. We will consider algorithms and applications of the CP and Tucker tensor decompositions, focusing our efforts on optimizing subroutines required to compute tensor decompositions.

A significant computational bottleneck when computing a CP decomposition is the matricized tensor times Khatri-Rao product (MTTKRP) subroutine. We will prove lower bounds for the communication complexity of MTTKRP, and provide communication-optimal algorithms. In addition, we will consider other tensor computations like partial MTTKRP and multiple tensor times vector (Multi-TTV) computations that are used to compute MTTKRP by performing some of the products in previous steps, the distributing the remaining products over the aggregations of previous partial products. We will also consider variations that compute all MTTKRP computations at once. For Tucker decompositions, a significant bottleneck may occur in the multiple tensor times matrix (Multi-TTM) computation required to generate a core tensor from a set of factor matrices and recover the full tensor from the decomposition. Again we will prove lower bounds on the communication complexity of this computation. Where the bounds are particularly interesting, we will provide communication-optimal algorithms either from existing literature or developed for this work.

Finally, we will search for alternative algorithms for matrix multiplication, so called fast algorithms, that break the assumptions of our communication lower bounds. Specifically, we will compare discrete and continuous search strategies for finding fast matrix multiplication algorithms. These fast algorithms may be used to reduce both the communication and computational complexity of matrix multiplication which underlies many tensor computations including Multi-TTM. Ultimately, due to the ability of CP-decompositions to encode bilinear forms, this search is in fact a search for an exact CP-decomposition of the tensor that encodes matrix multiplication of a given dimension.