CAREER: Scalable Algorithmic Primitives for Data Science

该项目旨在改进计算中一些最基本的算法：求解线性方程组，图上的优化，以及维护动态变化的网络。解决这些问题的工具是高级编程语言（如MATLAB和Julia）的组成部分，并且在机器学习、统计学和数据科学课程中经常作为基本编程结构教授。针对这些问题的改进算法可以提供更快、更健壮和更易于使用的算法原语，这反过来又可以在数据挖掘、图像处理、科学计算和网络科学等领域对更大、更多样化的数据集进行计算。建议的工作将积极涉及研究生，他们的成果将被纳入研究生和本科水平的课程。该项目还将支持PI长期参与算法问题解决外展活动，重点是使这些活动更容易被代表性不足的群体获得，并使研究生的参与制度化。这个项目提出的研究问题，线性系统求解和图上的优化，是算法设计中研究得最充分的一些问题。以前在这些主题上的工作导致了许多广泛使用的算法和数据结构。这个项目的主要方法是通过图拉普拉斯矩阵结合数值和组合算法原语的进展，被称为设计图算法的“拉普拉斯范式”。PI和合作者最近和正在进行的工作导致了当前涉及图拉普拉斯算子的许多关键问题的最佳算法，更重要的是，大大拓宽了所解决问题的范围。这些结果的一个潜在主题是，最强大的工具与中间算法状态一起工作，这个项目的重点是使用数据结构的思想对这种现象进行更深入的研究，数据结构也构建和重用中间算法状态。这些研究方向将导致新的算法结构，为静态和动态数据的计算提供改进的工具，并使基于图和矩阵计算的新应用成为可能。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

This project aims to improve some of the most fundamental algorithms in computing: solving systems of linear equations, optimization on graphs, and maintaining dynamically changing networks. Tools for solving these problems are integral components of high-level programming languages such as MATLAB and Julia, and are frequently taught as basic programming constructs in courses on machine learning, statistics, and data science. Improved algorithms for these problems can provide faster, more robust, and easier-to-use algorithmic primitives, which would in turn enable computing on larger and more diverse data sets in areas such as data mining, image processing, scientific computing, and network science. The proposed works will actively involve graduate students, and their results will be incorporated into courses at both graduate and undergraduate levels. The project will also support the PI's long-time involvement with algorithmic problem-solving outreach activities, with a focus on making these activities more accessible to underrepresented groups, and institutionalizing the involvement of graduate students. The problems that this project proposes to study, linear system solvers and optimization on graphs, are some of the most well-studied problems in algorithm design. Previous work on these topics led to many widely-used algorithms and data structures. The main approach of this project is motivated by progress on combining numerical and combinatorial algorithmic primitives through the graph Laplacian matrix, known as the `Laplacian paradigm' for designing graph algorithms. Recent and ongoing work by the PI and collaborators led to the current best algorithms for many key problems involving graph Laplacians, and more importantly, significantly broadened the scope of problems addressed. An underlying theme in these results is that the most powerful tools work with intermediate algorithmic states, and the focus of this project is a more in-depth study of this phenomenon using ideas from data structures, which also construct and reuse intermediate algorithmic states. These directions of investigation will lead to new algorithmic constructs, give improved tools for computing on static and dynamic data, and enable new applications based on computations on graphs and matrices.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.