权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

AF: Small: Geometry and Complexity Theory

AF：小：几何和复杂性理论

基本信息

批准号：
1814254
负责人：
Joseph Landsberg
金额：
$ 48.25万
依托单位：
Texas A&M University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2018
资助国家：
美国
起止时间：
2018-06-01 至 2022-05-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1814254&HistoricalAwards=false
关键词：
AF Small Geometry Complexity Theory

项目摘要

Linear algebra, which includes computing the solutions to a system of linear equations, is at the heart of all scientific computation. The core computation of linear algebra is matrix multiplication. In 1968 V. Strassen discovered that the widely used and assumed best algorithm for matrix multiplication is not optimal. Since then there has been intense research in both developing better algorithms and determining the limits of how much the current algorithms can be improved. There are three parts to the project. The first two are: practical construction of algorithms for matrix multiplication, and determining the above-mentioned limits. The third addresses a fundamental question of L. Valiant which is an algebraic analog of the famous P versus NP problem. Valiant asked if a polynomial that can be written down efficiently also must admit an efficient algorithm to compute it. All three parts will be approached using theoretical mathematics not traditionally utilized in the study of these questions (representation theory and algebraic geometry). The practical construction of algorithms in this project could potentially have impact across all scientific computation. The novel use of modern mathematical techniques previously not used in theoretical computer science will enrich both fields, opening new questions in mathematics and providing new techniques to computer science.The exponent of matrix multiplication, denoted omega, is the fundamental constant that governs the complexity of basic operations in linear algebra. It is currently known that omega is somewhere between 2 and 2.38. Independent of the exponent, practical matrix multiplication (of matrices of size that actually arise in practice) is only around 2.79. For example, matrices of size 1000x1000 may be effectively multiplied by performing (1000)^{2.79} arithmetic operations. If algorithms to achieve an omega of 2.38 were known, the same matrix operation can be performed using 220 million fewer arithmetic operations. By exploiting representation theory, this project will develop practical algorithms with the goal of lowering this practical exponent. It will also address the exponent by analyzing the feasibility of Strassen's asymptotic rank conjecture and its variants, which are proposed paths towards proving upper bounds on the exponent. The project will also address two aspects of Valiant's conjecture on permanent versus determinant. First, commutative algebra will be used to improve the current lower bound for the conjecture, which has not advanced since 2005. The investigator and a co-author have proven that Valiant's conjecture is true under the restricted model of equivariance. The second aspect will investigate loosening this restriction to weaker hypotheses under which the conjecture is still provable.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.

线性代数，包括计算线性方程组的解，是所有科学计算的核心。线性代数的核心计算是矩阵乘法。1968年，V.斯特拉森发现，广泛使用的和假定的最佳矩阵乘法算法并不是最佳的。从那时起，在开发更好的算法和确定当前算法可以改进多少的限制方面进行了大量的研究。该项目有三个部分。前两个是：矩阵乘法算法的实际构造，以及确定上述限制。第三个是关于L的一个基本问题。Valiant是著名的P对NP问题的代数模拟。Valiant问，如果一个多项式，可以有效地写下来，也必须承认一个有效的算法来计算它。所有这三个部分将接近使用理论数学传统上不利用研究这些问题（表示论和代数几何）。该项目中算法的实际构建可能会对所有科学计算产生影响。新的现代数学技术的使用以前没有在理论计算机科学中使用，将丰富这两个领域，在数学中开辟新的问题，并提供新的技术，以计算机科学。矩阵乘法的指数，表示为欧米茄，是基本常数，决定了线性代数中基本运算的复杂性。目前已知ω在2和2.38之间。与指数无关，实际的矩阵乘法（实际出现的矩阵大小）仅为2.79左右。例如，大小为1000 x1000的矩阵可以通过执行（1000）^{2.79}算术运算来有效地相乘。如果已知实现Ω为2.38的算法，则可以使用少2.2亿次算术运算来执行相同的矩阵运算。通过利用表示理论，本项目将开发实用算法，目标是降低这一实用指数。它还将通过分析斯特拉森的渐近秩猜想及其变体的可行性来解决指数，这些猜想及其变体是证明指数上界的建议路径。该项目还将解决两个方面的Valiant的猜想对永久与行列式。首先，交换代数将被用来改善目前的下界的猜想，这已经没有先进的自2005年以来。研究者和合著者证明了Valiant猜想在等方差限制模型下是正确的。第二个方面将研究放宽这一限制，以较弱的假设下，猜想仍然是可证明的。这个奖项反映了NSF的法定使命，并已被认为是值得的支持，通过评估使用基金会的智力价值和更广泛的影响审查标准。

项目成果

期刊论文数量（7）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Towards a geometric approach to Strassen’s asymptotic rank conjecture

走向斯特拉森渐近秩猜想的几何方法

DOI：
10.1007/s13348-020-00280-8
发表时间：
2021
期刊：
Collectanea mathematica
影响因子：
1.1
作者：
Conner, Austin;Gesmundo, Fulvio;Landsberg, Joseph M.;Ventura, Emanuele;Wang, Yao
通讯作者：
Wang, Yao

Multilinear Compressive Sensing and an Application to Convolutional Linear Networks

多线性压缩感知及其在卷积线性网络中的应用