High Performance Graph Algorithms and Data Structures

大规模数据的计算与线性系统求解器、凸优化以及存储动态变化网络的系统等工具密切相关。这些工具集成在许多高级编程语言中，如MATLAB、Python和Julia，这些语言又被广泛用于机器学习、统计和科学计算。这项研究计划的长期目标是开发新一代算法原语，适用于比我们目前处理的输入大几个数量级的输入。具体地说，我们希望开发出在静态和动态环境下处理图形和稀疏矩阵的高效和理论上站得住脚的算法。它建立在基本图问题算法的最新突破的基础上，即图结构线性系统的近线性时间解算器，网络流的更快算法，以及更高连接值的动态维护。短期(5年)目标是：*调查和分类结构化稀疏线性系统，特别是与图形相关的系统，目标是改进和改进操纵它们的数值基元。*开发近乎线性的时间算法，以解决范围广泛的图形优化问题，以获得高精度。*更好地理解数据结构，以便在动态变化的图上维护优化问题的解决方案。拟议的工作围绕着两个最广泛使用的数值基元：迭代和消元。将它们推广到更大类的计算问题将导致大量新的算法原语适用于大规模图和稀疏矩阵。这些原语是当今许多大规模计算的沉默主力，包括为现代互联网提供动力的搜索引擎。对它们的改进已经并将继续导致加速药物设计、更好的社交网络分析、更准确地向用户推荐产品等。这项研究计划包括对本科生和研究生的指导，开发连接数值算法和组合算法的课程，以及组织算法问题解决推广活动。参与的学生将获得算法的最新发展知识，发展独立研究技能，并通过参与外展活动获得监督/组织经验。这类技能在工业界和学术界都备受追捧：例如，社交媒体公司脸书计划在旧金山湾区招聘35000名员工，基于网络的快递公司亚马逊在过去一年中扩张了约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.