High Performance Graph Algorithms and Data Structures

大规模数据的计算与线性系统求解器、凸优化和存储动态变化网络的系统等工具密切相关。这些工具集成在许多高级编程语言中，如MATLAB、Python和Julia，这些语言又广泛用于机器学习、统计学和科学计算。这项研究计划的长期目标是开发新一代算法原语，适用于比我们目前处理的输入大几个数量级的输入。具体来说，我们希望在静态和动态设置中开发高效且理论上有充分基础的算法来处理图和稀疏矩阵。它建立在基本图问题算法的最新突破之上，即图结构线性系统的几乎近线性时间解算器，网络流的更快算法，以及更高连通性值的动态维护。短期（5年）的目标是：研究和分类结构化的稀疏线性系统，特别是与图相关的系统，目标是精炼和改进用于操作它们的数值原语。*开发几乎线性的时间算法，以高精度解决大范围的图优化问题。*更好地理解数据结构，以便在动态变化的图上维护优化问题的解决方案。所提出的工作围绕着两个最广泛使用的数值原语：迭代和消去。将它们推广到更广泛的计算问题中，将产生大量适合大规模图和稀疏矩阵的新算法原语。这些原语是当今许多大规模计算的无声主力，包括为现代互联网提供动力的搜索引擎。它们的改进已经并将继续导致加速药物设计，更好的社交网络分析，更准确地向用户推荐产品等等。本研究计划包括对本科生和研究生的监督，开发连接数值和组合算法的课程，以及组织算法问题解决的推广活动。参与的学生将获得算法最新发展的知识，培养独立研究技能，并通过参与外展活动获得监督/组织经验。这些技能在工业界和学术界都很受欢迎：例如，社交媒体公司Facebook计划在其湾区工厂雇佣3.5万名员工，网络快递公司亚马逊在过去一年中扩大了约50%，计算机研究协会报告称，2006年至2017年期间，计算机科学项目的规模平均增长了两倍，主要研究型大学在2021-2022周期内雇佣了70多名理论计算机科学学院。

Computation on large scale data is closely connected with tools such as linear system solvers, convex optimization, and systems for storing dynamically changing networks. These tools are integrated in many high-level programming languages such as MATLAB, Python, and Julia, which are in turn widely used in machine learning, statistics, and scientific computing. The long term goal of this research program is to develop a new generation of algorithmic primitives suitable for inputs several order of magnitudes larger than what we currently process. Specifically, we hope to develop highly efficient and theoretically well-founded algorithms for processing graphs and sparse matrices in both static and dynamic settings. It builds upon recent breakthroughs in algorithms for fundamental graph problems, namely almost nearly-linear time solvers for graph structured linear systems, faster algorithms for network flows, and dynamic maintenance of higher connectivity values. The shorter term (5 year) objectives are: * Investigate and classify structured sparse linear systems, especially ones related to graphs, with the goal of refining and improving numerical primitives for manipulating them. * Develop almost linear time algorithms for solving wide ranges of graph optimization problems to high accuracy. * Better understand data structures for maintaining solutions of optimization problems on dynamically changing graphs. The proposed work revolves around two of the most widely used numerical primitives: iteration and elimination. Generalizing them to wide classes of computational problems will lead to a host of new algorithmic primitives suitable for the large-scale graph and sparse matrices. Such primitives are the silent workhorse of much of large-scale computation today, including the search engines that power the modern internet. Improvements on them have led to, and will continue to lead to, accelerated drug design, better social network analytics, more accurate recommendation of products to users, and more. This research program includes the supervision of both undergraduate and graduate students, the development of courses that connect numerical and combinatorial algorithms, as well as the organization of algorithmic problem solving outreach activities. Students involved will gain knowledge in the latest development of algorithms, develop independent research skills, and gain supervision/organization experiences through involvements in outreach activities. Such skills are highly sought after in both industry and academia: for example, the social media company Facebook has plans of hiring 35000 employees in its Bay Area facility, the web-based delivery company Amazon expanded by about 50% over the past year, the Computer Research Association reported that the size of CS programs tripled on average between 2006 and 2017, and major research universities hired over 70 faculties in theoretical computer science during the 2021-2022 cycle.