CAREER: Communication-Avoiding Tensor Decomposition Algorithms

传感器和测量技术的进步，极端规模的科学模拟和数字通信都促成了数据雪崩，使分析师不知所措。标准的数据分析技术通常要求将信息组织成二维表格，例如，行对应于主题，列对应于特征。然而，今天的许多数据集涉及多路关系，并且更自然地在称为张量的高维表中表示。例如，电影是天然的3D张量，发送者和接收者之间跨越时间和多模态的通信信息可以用4D张量表示，在三个物理维度和时间上跟踪多个变量的科学模拟是5D张量。张量分解是对多维数据进行无监督探索和分析的最常用方法。这些分解可用于发现数据中的隐藏模式，发现行为中的异常，从测量中去除噪声，或压缩过大的数据集。这个项目的目的是开发有效的算法来计算这些分解，允许对多维数据集进行分析，否则会占用太多的时间或内存。教育计划包括编写教材和课程，旨在向本科生和研究生介绍张量分解和多维数据分析。在合理的时间内对当今规模的数据进行张量分解需要算法的效率，这不仅体现在它们执行的算术运算的数量上，还体现在它们通过内存层次结构和处理器之间通信的数据量上。该项目旨在开发用于计算张量分解的通信高效算法，该算法将很好地扩展到任意大小和维度的数据集；这些算法将能够高效、准确地分析需要分布在多个处理器内存中的庞大数据集。该项目的第一个重点将是证明用于计算最常见分解的算法所使用的关键内核的通信下限，并使用这些边界来驱动算法改进。该项目的第二个重点将是使用随机化来权衡确定性的准确性，以减少数据移动和计算复杂性。第三个重点是使已开发的算法适应这些分解的变体。拟议项目产生的算法将有助于高水平的面向生产力的软件包和用低级语言编写的高效并行实现。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.