AF: Small: Symbolic Computation with Certificates, Sparsity and Error Correction
AF:小:带有证书、稀疏性和纠错的符号计算
基本信息
- 批准号:1717100
- 负责人:
- 金额:$ 49.64万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Standard Grant
- 财政年份:2017
- 资助国家:美国
- 起止时间:2017-09-01 至 2022-08-31
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
This project continues the PI's productive work in certifying the results of symbolic computations and in polynomial computations. It aims for results in three areas: 1. Low-cost certification of the output of large-scale symbolic computations performed on high power servers, possibly in the computing cloud. The focus is on problems in high-dimensional linear algebra and non-linear optimization. Quickly checkable proofs can also expose bugs/faults in time- and space-consuming server computations. 2. Medical image processing needs robust interpolation from values sampled at points; The project will reconstruct functions as sparse sums of a few exponentials or orthogonal polynomials, using algorithms that account for noise and outliers (that is, catastrophic errors) while minimizing the number of sample points. 3. In fundamental problems in algebraic computational complexity, it takes a fresh look at polynomial multiplication and greatest common divisors.The PI continues to train undergraduate and Master students, and supervise Ph.D. students and a postdoctoral scholar, so that they develop advanced skills in designing algorithms and computer programs for doing mathematics. The students and postdoc will be encouraged to adopt advanced research communication skills by presenting posters and talks at international meetings, especially when their background is from under-represented groups in the discipline.The method to achieve the goal of low-cost certification is to develop certificates for the Frobenius form of sparse matrices and for the solvability of polynomial equations over the real numbers that are independent of the algorithms that produce the output. The approach is based on interactive proof protocols and crytographic hardness assumptions, but the project aims to reduce the use of cryptography in its protocols, so that the verifier can increase probability of correctness arbitrarily, even after the computation. The PI has used algebraic error correcting decoding to locate evaluation errors in sparse interpolation and dense rational vector recovery, the latter with early termination. The current focus is on sparseness in a Chebyshev basis, where list-decoders are missing, and on multivariate sparse interpolation using a generalization of Prony's Algorithm combined with Sakata's generalization of the Berlekamp/Massey Algorithm. Finally, the project studies the algebraic complexity of multiplying polynomials without the use of constants, computing the Sylvester resultant without divisions, and representing polynomials as the characteristic polynomial of matrices.
该项目延续了PI的生产力,以证明符号计算的结果和多项式计算的结果。 它的目的是在三个领域的结果:1。对高功率服务器(可能在计算云中)执行的大规模符号计算输出的低成本认证。 重点是高维线性代数和非线性优化的问题。 快速检查的证明还可以在时间和空间的服务器计算中揭示错误/故障。 2。医疗图像处理需要从点在点采样的值来鲁棒插值;该项目将使用一些算法来重建几个指数或正交多项式的稀疏总和,这些算法可以说明噪声和异常值(即灾难性错误),同时最小化样品点的数量。 3。在代数计算复杂性中的基本问题中,它需要重新研究多项式乘法和最大的常见分歧。学生和博士后学者,以便他们在设计用于数学的算法和计算机程序方面发展了高级技能。 将鼓励学生和博士后通过在国际会议上介绍海报和演讲来采取高级研究沟通技巧,尤其是当他们的背景来自该学科中的代表性不足的群体时。实现低成本认证目标的方法是为稀疏矩阵的Frobenius形式开发证书,而稀疏矩阵和多项式平等的溶解度超过了altg,而这些算法是独立的,而这些数字是独立于该算法的。 该方法基于交互式证明协议和冷冻硬度假设,但是该项目旨在减少加密在其协议中的使用,以便验证者即使在计算后也可以任意提高正确性的可能性。 PI已使用校正解码的代数误差来定位稀疏插值和密集的有理矢量恢复中的评估误差,后者具有早期终止。 当前的重点是在chebyshev的基础上稀疏,其中列表描述器缺少,以及使用Prony算法的概括以及Sakata对Berlekamp/Massey算法的概括的多元稀疏插值。 最后,该项目研究了不使用常数的多项式多项式的代数复杂性,计算sylvester的产生而无需划分,并将多项式表示为矩阵的特征多项式。
项目成果
期刊论文数量(11)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
Elimination-based certificates for triangular equivalence and rank profiles
- DOI:10.1016/j.jsc.2019.07.013
- 发表时间:2019-09
- 期刊:
- 影响因子:0
- 作者:J. Dumas;E. Kaltofen;David Lucas;Clément Pernet
- 通讯作者:J. Dumas;E. Kaltofen;David Lucas;Clément Pernet
Hermite Interpolation With Error Correction: Fields of Zero or Large Characteristic and Large Error Rate
带纠错的 Hermite 插值:零或大特征和大错误率的字段
- DOI:10.1145/3452143.3465525
- 发表时间:2021
- 期刊:
- 影响因子:0
- 作者:Kaltofen, Erich L.;Pernet, Clément;Yang, Zhi-Hong
- 通讯作者:Yang, Zhi-Hong
Sparse Polynomial Hermite Interpolation
- DOI:10.1145/3476446.3535501
- 发表时间:2022-07
- 期刊:
- 影响因子:0
- 作者:E. Kaltofen
- 通讯作者:E. Kaltofen
Hermite Rational Function Interpolation with Error Correction
带误差修正的 Hermite 有理函数插值
- DOI:10.1007/978-3-030-60026-6_19
- 发表时间:2020
- 期刊:
- 影响因子:0
- 作者:Kaltofen, Erich L.;Pernet, Clement;Yang, Zhi-Hong
- 通讯作者:Yang, Zhi-Hong
Computing Higher Polynomial Discriminants
- DOI:10.1145/3452143.3465543
- 发表时间:2021-07
- 期刊:
- 影响因子:0
- 作者:E. Kaltofen
- 通讯作者:E. Kaltofen
{{
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 }}
Erich Kaltofen其他文献
Deterministic distinct-degree factorization of polynomials over finite fields
有限域上多项式的确定性异次因式分解
- DOI:
- 发表时间:
2004 - 期刊:
- 影响因子:0.7
- 作者:
Shuhong Gao;Erich Kaltofen;Alan G. B. Lauder - 通讯作者:
Alan G. B. Lauder
What is Hybrid Symbolic-Numeric Computation?
- DOI:
10.1109/synasc.2011.65 - 发表时间:
2011-09 - 期刊:
- 影响因子:0
- 作者:
Erich Kaltofen - 通讯作者:
Erich Kaltofen
Parallel Computation of Polynomial Greatest Common Divisors
多项式最大公约数的并行计算
- DOI:
- 发表时间:
2022 - 期刊:
- 影响因子:0
- 作者:
Erich Kaltofen - 通讯作者:
Erich Kaltofen
Factorization of Polynomials
- DOI:
10.1007/978-3-7091-7551-4_8 - 发表时间:
1983 - 期刊:
- 影响因子:0
- 作者:
Erich Kaltofen - 通讯作者:
Erich Kaltofen
Erich Kaltofen的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Erich Kaltofen', 18)}}的其他基金
AF: Small: Symbolic computation with sparsity, error checking and error correction
AF:小:具有稀疏性、错误检查和纠错的符号计算
- 批准号:
1421128 - 财政年份:2014
- 资助金额:
$ 49.64万 - 项目类别:
Standard Grant
AF: Small: Efficient Exact/Certified Symbolic Computation By Hybrid Symbolic-Numeric and Parallel Methods
AF:小型:通过混合符号数字和并行方法进行高效精确/认证符号计算
- 批准号:
1115772 - 财政年份:2011
- 资助金额:
$ 49.64万 - 项目类别:
Standard Grant
Model Discovery and Verification With Symbolic, Hybrid Symbolic-Numeric and Parallel Computation
使用符号、混合符号数值和并行计算进行模型发现和验证
- 批准号:
0830347 - 财政年份:2008
- 资助金额:
$ 49.64万 - 项目类别:
Standard Grant
Workshop on Advanced Cyber-Enabled Discovery & Innovation (CDI) Through Symbolic and Numeric Computation
高级网络驱动发现研讨会
- 批准号:
0751501 - 财政年份:2007
- 资助金额:
$ 49.64万 - 项目类别:
Standard Grant
Challenges in Linear and Polynomil Algebra in Symbolic Computation Algorithms
符号计算算法中线性代数和多项式代数的挑战
- 批准号:
0514585 - 财政年份:2005
- 资助金额:
$ 49.64万 - 项目类别:
Continuing Grant
Fast Bit Complexity in Symbolic Computation Algorithms
符号计算算法中的快速位复杂性
- 批准号:
0305314 - 财政年份:2003
- 资助金额:
$ 49.64万 - 项目类别:
Continuing Grant
ITR/ACS: Collaborative Research LinBox: A Generic Library for Seminumeric Black Box Linear Algebra
ITR/ACS:协作研究 LinBox:半数值黑盒线性代数通用库
- 批准号:
0113121 - 财政年份:2001
- 资助金额:
$ 49.64万 - 项目类别:
Standard Grant
Optimization, Randomization, and Generalization in Symbolic Computation
符号计算中的优化、随机化和泛化
- 批准号:
9988177 - 财政年份:2000
- 资助金额:
$ 49.64万 - 项目类别:
Standard Grant
Multi-Use "Plug-And-Play" Software Packages for Black Box and Inexact Symbolic Objects
用于黑匣子和不精确符号对象的多用途“即插即用”软件包
- 批准号:
9712267 - 财政年份:1997
- 资助金额:
$ 49.64万 - 项目类别:
Standard Grant
Efficient Computer Algorithms for Symbolic Mathematics
符号数学的高效计算机算法
- 批准号:
9696203 - 财政年份:1996
- 资助金额:
$ 49.64万 - 项目类别:
Continuing Grant
相似国自然基金
靶向Treg-FOXP3小分子抑制剂的筛选及其在肺癌免疫治疗中的作用和机制研究
- 批准号:32370966
- 批准年份:2023
- 资助金额:50 万元
- 项目类别:面上项目
化学小分子激活YAP诱导染色质可塑性促进心脏祖细胞重编程的表观遗传机制研究
- 批准号:82304478
- 批准年份:2023
- 资助金额:30 万元
- 项目类别:青年科学基金项目
靶向小胶质细胞的仿生甘草酸纳米颗粒构建及作用机制研究:脓毒症相关性脑病的治疗新策略
- 批准号:82302422
- 批准年份:2023
- 资助金额:30 万元
- 项目类别:青年科学基金项目
HMGB1/TLR4/Cathepsin B途径介导的小胶质细胞焦亡在新生大鼠缺氧缺血脑病中的作用与机制
- 批准号:82371712
- 批准年份:2023
- 资助金额:49 万元
- 项目类别:面上项目
小分子无半胱氨酸蛋白调控生防真菌杀虫活性的作用与机理
- 批准号:32372613
- 批准年份:2023
- 资助金额:50 万元
- 项目类别:面上项目
相似海外基金
AF: Small: Numeric-Symbolic Techniques for Geometric Problems in Algebra and Analysis
AF:小:代数和分析中几何问题的数值符号技术
- 批准号:
1423228 - 财政年份:2014
- 资助金额:
$ 49.64万 - 项目类别:
Standard Grant
AF: Small: Symbolic computation with sparsity, error checking and error correction
AF:小:具有稀疏性、错误检查和纠错的符号计算
- 批准号:
1421128 - 财政年份:2014
- 资助金额:
$ 49.64万 - 项目类别:
Standard Grant
AF: Small: Relaxation Techniques in Symbolic-Numeric Computation
AF:小:符号数值计算中的松弛技术
- 批准号:
1217557 - 财政年份:2012
- 资助金额:
$ 49.64万 - 项目类别:
Standard Grant
AF: Small: Efficient Exact/Certified Symbolic Computation By Hybrid Symbolic-Numeric and Parallel Methods
AF:小型:通过混合符号数字和并行方法进行高效精确/认证符号计算
- 批准号:
1115772 - 财政年份:2011
- 资助金额:
$ 49.64万 - 项目类别:
Standard Grant
AF: Small: Symbolic Computation and Difference and Differential Equations
AF:小:符号计算以及差分和微分方程
- 批准号:
1017217 - 财政年份:2010
- 资助金额:
$ 49.64万 - 项目类别:
Standard Grant