CAREER: Fine-Grained Complexity and Algorithms for Structured Linear Equations and Linear Programs

职业：结构化线性方程和线性程序的细粒度复杂性和算法

• 批准号: 2238682
• 负责人: Peng Zhang
• 金额: $ 49.93万
• 依托单位: Rutgers University New Brunswick
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-02-01 至 2028-01-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2238682&HistoricalAwards=false
• 关键词: CAREER; Fine; Grained; Complexity; Algorithms

Abstract:Linear equations and linear programs are ubiquitous in computational mathematics, engineering, machine learning, and data science, and they are powerful primitives for developing various algorithmic paradigms. Unfortunately, the currently best-known algorithms for solving general linear equations and linear programs run in super-quadratic time, which can be prohibitively slow for modern large-scale datasets. In practice, however, many linear equations and programs exhibit additional structures that enable significantly faster solvers. This project aims (1) to identify and classify structures that can accelerate solving linear equations and linear programs and those that can not and (2) to understand how fast we can solve general linear equations and linear programs. Another major part of this project is to provide multi-disciplinary education and research training for graduate, undergraduate, and high school students and to broaden the participation of women and underrepresented students in STEM fields. This project aims to study fine-grained complexity and algorithms for structured linear equations and structured linear programs and focuses on three major goals. The first goal is to establish ``equivalent`` classes for structured linear equations and linear programs so that if we can solve one problem fast, we can immediately solve all the problems in the same equivalence class equally fast. The second goal is to develop efficient solvers for structured linear equations and linear programs that arise commonly from practice. Examples include generalized Laplacians with additional geometric structures, dense instances such as kernel matrices, and random instances. Finally, the third goal is to better understand the time complexity of general linear equations and linear programs. For example, can we solve general linear equations and linear programs faster than matrix multiplication? What are the runtime lower bounds under the Strong Exponential Time Hypothesis?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）了解我们可以多快解决一般线性方程和线性规划。该项目的另一个主要部分是为研究生、本科生和高中生提供多学科教育和研究培训，并扩大妇女和代表性不足的学生在STEM领域的参与。本计画主要研究结构化线性方程式与结构化线性程式之细粒度复杂度与演算法，并著重于三个主要目标。第一个目标是为结构化线性方程和线性规划建立“等价”类，这样如果我们能快速解决一个问题，我们就能立即同样快速地解决同一等价类中的所有问题。第二个目标是为结构化线性方程组和线性规划开发有效的求解器，这些线性方程组和线性规划通常来自实践。例子包括具有额外几何结构的广义拉普拉斯算子、稠密实例（如核矩阵）和随机实例。最后，第三个目标是更好地理解一般线性方程和线性规划的时间复杂度。例如，我们能比矩阵乘法更快地求解一般线性方程组和线性规划吗？强指数时间假设下的运行时间下限是什么？该奖项反映了NSF的法定使命，并被认为是值得通过使用基金会的知识价值和更广泛的影响审查标准进行评估的支持。

项目成果

Efficient 1-Laplacian Solvers for Well-Shaped Simplicial Complexes: Beyond Betti Numbers and Collapsing Sequences

用于形状良好的单纯复形的高效 1-拉普拉斯求解器：超越贝蒂数和折叠序列

• DOI: 10.4230/lipics.esa.2023.41
• 发表时间: 2023
• 期刊: Leibniz International Proceedings in Informatics (LIPIcs
• 作者: Ding, Ming;Zhang, Peng
• 通讯作者: Zhang, Peng