CAREER: Communication-Avoiding Tensor Decomposition Algorithms

Wake Forest University, Winston Salem NC

Investigators

Abstract

Advances in sensors and measurement technologies, extreme-scale scientific simulations, and digital communications all contribute to a data avalanche that is overwhelming analysts. Standard data-analytic techniques often require information to be organized into two-dimensional tables, where, for example, rows correspond to subjects and columns correspond to features. However, many of today's data sets involve multi-way relationships and are more naturally represented in higher-dimensional tables called tensors. For example, movies are naturally 3D tensors, communication information tracked between senders and receivers across time and across multiple modalities can be represented by a 4D tensor, and scientific simulations tracking multiple variables in three physical dimensions and across time are 5D tensors. Tensor decompositions are the most common method of unsupervised exploration and analysis of multidimensional data. These decompositions can be used to discover hidden patterns in data, find anomalies in behavior, remove noise from measurements, or compress prohibitively large data sets. The aim of this project is to develop efficient algorithms for computing these decompositions, allowing for analysis of multidimensional datasets that would otherwise take too much time or memory. The education plan includes the development of a textbook and course aimed to introduce undergraduate and graduate students to tensor decompositions and multidimensional data analysis. Computing tensor decompositions on data of today’s magnitude in reasonable time requires algorithms to be efficient, not only in the number of arithmetic operations they perform, but also in the amount of data they communicate through the memory hierarchy and among processors. This project aims to develop communication-efficient algorithms for computing tensor decompositions that will scale well to data sets of arbitrary size and dimension; these algorithms will enable efficient and accurate analysis of huge datasets that require distribution across multiple processors’ memories. The first thrust of the project will be to prove communication lower bounds for the key kernels used by algorithms for computing the most common decompositions, and use those bounds to drive algorithmic improvements. The second thrust of the project will be to use randomization to trade off deterministic accuracy for reduced data movement and computational complexity. The third thrust is to adapt the developed algorithms to variants of these decompositions. The algorithms produced by the proposed project will contribute to both high-level productivity-oriented software packages and highly efficient, parallel implementations written in low-level languages. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.