CAREER: Scalable Algorithmic Primitives for Data Science

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

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.