AF: Small: Algorithms for Matrix Multiplication, Polynomial Factorization and Generalized Fourier Transform
AF:小:矩阵乘法、多项式分解和广义傅立叶变换算法
基本信息
- 批准号:1423544
- 负责人:
- 金额:$ 50万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Standard Grant
- 财政年份:2014
- 资助国家:美国
- 起止时间:2014-07-01 至 2017-06-30
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
This project addresses three prominent algorithmic problems: matrix multiplication, polynomial factorization, and the generalized discrete Fourier transform (DFT). In the first two, the challenge is to obtain fast algorithms for basic manipulations of matrices and polynomials, and in the third, the challenge is to obtain fast algorithms for transforming data in certain mathematically meaningful ways. Matrix multiplication is a central open problem in theoretical computer science, both because of its intrinsic mathematical appeal, and because improved algorithms for this important problem would have immediate consequences for a broad variety of related problems. Univariate polynomial factorization occupies a similar central position among the basic operations on polynomials, and the generalized DFT is one of the most interesting and useful linear maps, with structure that should admit a fast algorithm. All three problems are fundamental and longstanding open problems, and they have a diversity of applications in computer science, and beyond.The project's goal is to achieve "nearly-linear" time algorithms for all three problems. These problems possess rich structure that is susceptible to a sophisticated mathematical treatment; for example, one technique is to embed matrix multiplication into algebraic structures arising from groups and coherent configurations. This project develops these ideas, and at the same time aims to make further progress by injecting some more "computer science"-style ideas -- recursion, approximation, reductions, relaxations, and a mixture of Boolean computation with algebraic operations. Because all three focus areas of this project revolve around difficult and longstanding open problems, the project will take concrete steps towards (1) building up understanding and (2) developing useful machinery, both aimed at an eventual resolution of these central algorithmic problems.
该项目解决了三个突出的算法问题:矩阵乘法,多项式分解和广义离散傅立叶变换(DFT)。在前两个方面,挑战是获得矩阵和多项式基本操作的快速算法,而在第三个方面,挑战是获得以某些数学上有意义的方式转换数据的快速算法。矩阵乘法是理论计算机科学中的一个核心开放问题,这既是因为它内在的数学吸引力,也是因为改进了这个重要问题的算法将对各种相关问题产生直接影响。单变量多项式分解在多项式的基本运算中占有类似的中心地位,广义DFT是最有趣和最有用的线性映射之一,其结构应该允许快速算法。这三个问题都是基本的、长期存在的开放性问题,它们在计算机科学和其他领域有多种应用。该项目的目标是为这三个问题实现“近乎线性”的时间算法。这些问题具有丰富的结构,易于进行复杂的数学处理;例如,一种技术是将矩阵乘法嵌入到由群和相干构型产生的代数结构中。这个项目发展了这些想法,同时旨在通过注入更多的“计算机科学”风格的想法——递归、近似、约简、松弛,以及布尔计算与代数运算的混合来取得进一步的进展。由于该项目的所有三个重点领域都围绕着困难和长期开放的问题,因此该项目将采取具体步骤(1)建立理解和(2)开发有用的机器,两者都旨在最终解决这些核心算法问题。
项目成果
期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
数据更新时间:{{ journalArticles.updateTime }}
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
Christopher Umans其他文献
Pseudorandomness for Approximate Counting and Sampling
近似计数和采样的伪随机性
- DOI:
- 发表时间:
2006 - 期刊:
- 影响因子:0
- 作者:
Ronen Shaltiel;Christopher Umans - 通讯作者:
Christopher Umans
Special Issue “Conference on Computational Complexity 2013” Guest editor’s foreword
- DOI:
10.1007/s00037-014-0088-x - 发表时间:
2014-05-08 - 期刊:
- 影响因子:1.000
- 作者:
Christopher Umans - 通讯作者:
Christopher Umans
Christopher Umans的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Christopher Umans', 18)}}的其他基金
AF: Small: Group Theory and Representation Theory in Matrix Multiplication and Generalized DFTs
AF:小:矩阵乘法和广义 DFT 中的群论和表示论
- 批准号:
1815607 - 财政年份:2018
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
AF: Small: Algebraic Methods for Core Problems in Algorithms and Complexity
AF:小:算法和复杂性核心问题的代数方法
- 批准号:
1116111 - 财政年份:2011
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
New Applications of Error-Correcting Codes in Complexity and Algorithms
纠错码在复杂性和算法方面的新应用
- 批准号:
0830787 - 财政年份:2008
- 资助金额:
$ 50万 - 项目类别:
Continuing Grant
CAREER: Research in Complexity Theory with Applications
职业:复杂性理论及其应用研究
- 批准号:
0346991 - 财政年份:2004
- 资助金额:
$ 50万 - 项目类别:
Continuing Grant
相似国自然基金
昼夜节律性small RNA在血斑形成时间推断中的法医学应用研究
- 批准号:
- 批准年份:2024
- 资助金额:0.0 万元
- 项目类别:省市级项目
tRNA-derived small RNA上调YBX1/CCL5通路参与硼替佐米诱导慢性疼痛的机制研究
- 批准号:n/a
- 批准年份:2022
- 资助金额:10.0 万元
- 项目类别:省市级项目
Small RNA调控I-F型CRISPR-Cas适应性免疫性的应答及分子机制
- 批准号:32000033
- 批准年份:2020
- 资助金额:24.0 万元
- 项目类别:青年科学基金项目
Small RNAs调控解淀粉芽胞杆菌FZB42生防功能的机制研究
- 批准号:31972324
- 批准年份:2019
- 资助金额:58.0 万元
- 项目类别:面上项目
变异链球菌small RNAs连接LuxS密度感应与生物膜形成的机制研究
- 批准号:81900988
- 批准年份:2019
- 资助金额:21.0 万元
- 项目类别:青年科学基金项目
肠道细菌关键small RNAs在克罗恩病发生发展中的功能和作用机制
- 批准号:31870821
- 批准年份:2018
- 资助金额:56.0 万元
- 项目类别:面上项目
基于small RNA 测序技术解析鸽分泌鸽乳的分子机制
- 批准号:31802058
- 批准年份:2018
- 资助金额:26.0 万元
- 项目类别:青年科学基金项目
Small RNA介导的DNA甲基化调控的水稻草矮病毒致病机制
- 批准号:31772128
- 批准年份:2017
- 资助金额:60.0 万元
- 项目类别:面上项目
基于small RNA-seq的针灸治疗桥本甲状腺炎的免疫调控机制研究
- 批准号:81704176
- 批准年份:2017
- 资助金额:20.0 万元
- 项目类别:青年科学基金项目
水稻OsSGS3与OsHEN1调控small RNAs合成及其对抗病性的调节
- 批准号:91640114
- 批准年份:2016
- 资助金额:85.0 万元
- 项目类别:重大研究计划
相似海外基金
Collaborative Research: AF: Small: Structural Graph Algorithms via General Frameworks
合作研究:AF:小型:通过通用框架的结构图算法
- 批准号:
2347322 - 财政年份:2024
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
AF: Small: Communication-Aware Algorithms for Dynamic Allocation of Heterogeneous Resources
AF:小型:用于异构资源动态分配的通信感知算法
- 批准号:
2335187 - 财政年份:2024
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: Structural Graph Algorithms via General Frameworks
合作研究:AF:小型:通过通用框架的结构图算法
- 批准号:
2347321 - 财政年份:2024
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
AF: Small: New Challenges and Approaches in Clustering Algorithms
AF:小:聚类算法的新挑战和方法
- 批准号:
2311397 - 财政年份:2023
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
AF: Small: RUI: Toward High-Performance Block Krylov Subspace Algorithms for Solving Large-Scale Linear Systems
AF:小:RUI:用于求解大规模线性系统的高性能块 Krylov 子空间算法
- 批准号:
2327619 - 财政年份:2023
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
SHF: AF: Small: Algorithms and a Code Generator for Faster Stencil Computations
SHF:AF:Small:用于更快模板计算的算法和代码生成器
- 批准号:
2318633 - 财政年份:2023
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
NSF-BSF: AF: Small: Algorithms for Graph-Based Codes
NSF-BSF:AF:小型:基于图形的代码算法
- 批准号:
2133154 - 财政年份:2022
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
AF: Small: Towards New Relaxations for Online Algorithms
AF:小:在线算法的新放松
- 批准号:
2224718 - 财政年份:2022
- 资助金额:
$ 50万 - 项目类别:
Standard Grant