Collaborative Research: OAC Core: Robust, Scalable, and Practical Low-Rank Approximation

合作研究：OAC 核心：稳健、可扩展且实用的低阶近似

• 批准号: 2106920
• 负责人: Grey Ballard
• 金额: $ 22.5万
• 依托单位: Wake Forest University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2021
• 资助国家: 美国
• 起止时间: 2021-07-15 至 2024-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2106920&HistoricalAwards=false
• 关键词: Collaborative; Research; OAC; Core; Robust

Nearly all aspects of society are affected by data being produced at a faster rate in recent years. The data from experiments, observations, and simulations are not only in more classical science and engineering domains but also in numerous other areas such as businesses tracking more and more facets of consumer behavior, and social networking capturing vast amounts of information on the relationships between people and their actions and interactions. There is a strong need to distill a set of data into a smaller representation that separates useful information from noise and captures the most important trends, patterns, and underlying relationships.  Such a representation can be used for direct interpretation of hidden patterns or as a means of simplifying other data analytic tasks.  This project addresses these challenges by studying a concept from linear algebra called low rank approximation.  The project develops techniques that faithfully distill the meaningful information within a data set.  The algorithms are also designed to exploit high-performance computers so that analysts can get results more quickly and tackle larger problems.  The overall effort in the project is expected to close the gap between algorithms that can effectively handle very large-scale problems and the data analyst’s ability to convert raw input into meaningful representations and actionable insight.The matrix and tensor low rank approximations being studied in this project serve as foundational tools in numerous science and engineering applications. Imposing constraints on the low rank approximations enables the modeling of many key problems, and designing scalable algorithms enables new applications that reach far beyond classical science and engineering disciplines. In particular, mathematical models with nonnegative data values abound, and imposing nonnegative constraints allows for more accurate and interpretable models. Variants of these constraints can be designed to reflect additional characteristics of real-life data analytics problems. The primary goals of this project are (1) to develop robust techniques for evaluating computed low rank approximations for rank and model determination, (2) to develop scalable parallel algorithms for large and robust low rank approximations on today’s extreme-scale machines, and (3) to provide end users the practical tools required to compute and analyze solutions at scale. Typical data and application scientists use Python or Matlab to iteratively compute, visualize, and evaluate solutions, and they are limited to small data sets with feasible memory and computational requirements. While high-performance algorithms and implementations exist, end users would not leverage these tools if they cannot rely on the robustness and generalizability of the results. This project aims to close this gap, developing an end-to-end system with scalable solutions for all steps of the data analytics workflow.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.

近年来，社会的几乎所有方面都受到了数据产生速度的影响。来自实验、观察和模拟的数据不仅在更经典的科学和工程领域，而且在许多其他领域，如企业跟踪越来越多的消费者行为方面，社交网络捕获大量关于人与他们的行为和互动之间关系的信息。强烈需要将一组数据提取为较小的表示，将有用信息与噪声分离，并捕获最重要的趋势，模式，和潜在的关系。这种表示可以用于直接解释隐藏的模式或作为简化其他数据分析任务的一种手段。这个项目通过研究线性代数中称为低秩近似的概念来解决这些挑战。该项目开发了忠实地提取数据集中有意义信息的技术。算法也旨在利用高性能计算机，以便分析人员可以更快地获得结果并解决更大的问题。该项目的整体努力预计将缩小算法之间的差距，这些算法可以有效地处理非常大的数据集。规模问题以及数据分析师将原始输入转换为有意义的表示和可操作的洞察力的能力。该项目中正在研究的矩阵和张量低秩近似作为许多科学和工程应用的基础工具。对低秩近似施加约束使得许多关键问题能够建模，并且设计可扩展的算法使得新的应用远远超出经典科学和工程学科。特别是，具有非负数据值的数学模型比比皆是，并且施加非负约束允许更准确和可解释的模型。这些约束的变体可以被设计为反映现实生活中数据分析问题的其他特征。该项目的主要目标是（1）开发用于评估计算的低秩近似的秩和模型确定的鲁棒技术，（2）在当今的极端规模机器上开发用于大型和鲁棒低秩近似的可扩展并行算法，以及（3）为最终用户提供大规模计算和分析解决方案所需的实用工具。典型的数据和应用科学家使用Python或Matlab来迭代计算、可视化和评估解决方案，并且他们仅限于具有可行内存和计算要求的小数据集。虽然存在高性能的算法和实现，但如果最终用户不能依赖结果的健壮性和通用性，他们就不会利用这些工具。该项目旨在缩小这一差距，开发一个端到端系统，为数据分析工作流程的所有步骤提供可扩展的解决方案。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Parallel Memory-Independent Communication Bounds for SYRK

SYRK 的并行内存独立通信范围

• DOI: 10.1145/3558481.3591072
• 发表时间: 2023
• 期刊: Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures
• 作者: Al Daas, Hussam;Ballard, Grey;Grigori, Laura;Kumar, Suraj;Rouse, Kathryn
• 通讯作者: Rouse, Kathryn

Distributed-Memory Parallel JointNMF

• DOI: 10.1145/3577193.3593733
• 发表时间: 2023-06
• 期刊: Proceedings of the 37th International Conference on Supercomputing
• 作者: Srinivas Eswar;Benjamin Cobb;Koby Hayashi;R. Kannan;Grey Ballard;R. Vuduc;Haesun Park

Parallel Tensor Train Rounding using Gram SVD

使用 Gram SVD 进行并行张量训练舍入

• DOI: 10.1109/ipdps53621.2022.00095
• 发表时间: 2022
• 期刊: Proceedings of the 2022 IEEE International Parallel and Distributed Processing Symposium
• 作者: Al Daas, Hussam;Ballard, Grey;Manning, Lawton
• 通讯作者: Manning, Lawton

Brief Announcement: Tight Memory-Independent Parallel Matrix Multiplication Communication Lower Bounds

简短公告：严格的内存独立并行矩阵乘法通信下界

• DOI: 10.1145/3490148.3538552
• 发表时间: 2022
• 期刊: Proceedings of the 34th Annual ACM Symposium on Parallelism in Algorithms and Architectures
• 作者: Al Daas, Hussam;Ballard, Grey;Grigori, Laura;Kumar, Suraj;Rouse, Kathryn
• 通讯作者: Rouse, Kathryn

Visualizing Parallel Dynamic Programming using the Thread Safe Graphics Library

使用线程安全图形库可视化并行动态编程

• DOI: 10.1109/eduhpc54835.2021.00009
• 发表时间: 2021
• 期刊: 2021 IEEE/ACM Ninth Workshop on Education for High Performance Computing (EduHPC
• 作者: Ballard, Grey;Parsons, Sarah
• 通讯作者: Parsons, Sarah