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. Strassen发现，用于基质乘法的广泛使用和假定的最佳算法不是最佳的。从那时起，人们一直在开发更好的算法和确定可以改善当前算法的限制方面进行了激烈的研究。该项目有三个部分。前两个是：用于矩阵乘法算法的实用结构，并确定上述限制。第三个问题是L. Valiant的基本问题，该问题是著名P与NP问题的代数类似物。英勇询问是否可以有效地写下的多项式还必须接受有效的算法来计算它。所有这三个部分将使用传统上不使用这些问题（表示理论和代数几何形状）的理论数学来处理。该项目中算法的实际结构可能会在所有科学计算中产生影响。以前在理论计算机科学中未使用的现代数学技术的新颖使用将丰富这两个领域，在数学上开放新问题并为计算机科学提供新技术。矩阵乘法的指数，表示欧米茄（Omega），是控制基本操作的基本常数。目前众所周知，欧米茄在2到2.38之间。独立于指数，实用的矩阵乘法（实际上在实践中出现的大小的矩阵）仅在2.79左右。例如，大小1000x1000的矩阵可以通过执行（1000）^{2.79}算术操作有效地乘以。如果已知以达到2.38的欧米茄算法，则可以使用少量的算术操作进行相同的矩阵操作。通过利用代表理论，该项目将开发实用算法，以降低该实用指数。它还将通过分析Strassen的渐近等级猜想及其变体的可行性来解决指数，这是提出了证明指数上限的途径。该项目还将解决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

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