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

AF: Small: Symbolic Computation with Certificates, Sparsity and Error Correction

AF：小：带有证书、稀疏性和纠错的符号计算

基本信息

批准号：
1717100
负责人：
Erich Kaltofen
金额：
$ 49.64万
依托单位：
North Carolina State University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2017
资助国家：
美国
起止时间：
2017-09-01 至 2022-08-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1717100&HistoricalAwards=false
关键词：
AF Small Symbolic Computation Certificates

项目摘要

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. 在代数计算复杂性的基本问题上，重新审视多项式乘法和最大公约数。 PI继续培养本科生和硕士生，并指导博士生。学生和博士后学者，以便他们发展设计数学算法和计算机程序的高级技能。将鼓励学生和博士后通过在国际会议上展示海报和演讲来采用先进的研究沟通技巧，特别是当他们的背景来自该学科中代表性不足的群体时。实现低成本认证目标的方法是为稀疏矩阵的 Frobenius 形式以及独立于产生输出的算法的实数多项式方程的可解性开发证书。该方法基于交互式证明协议和密码学硬度假设，但该项目的目标是减少协议中密码学的使用，以便验证者可以任意增加正确性的概率，即使在计算之后也是如此。 PI使用代数纠错解码来定位稀疏插值和稠密有理向量恢复中的评估错误，后者提前终止。当前的重点是切比雪夫基础上的稀疏性（其中缺少列表解码器），以及使用 Prony 算法的泛化与 Sakata 的 Berlekamp/Massey 算法的泛化相结合的多元稀疏插值。最后，该项目研究了不使用常数的多项式相乘、不除法计算西尔维斯特结果以及将多项式表示为矩阵的特征多项式的代数复杂性。

项目成果

期刊论文数量（11）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Elimination-based certificates for triangular equivalence and rank profiles

DOI：
10.1016/j.jsc.2019.07.013
发表时间：
2019-09
期刊：
ArXiv
影响因子：
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
期刊：
ISSAC '21: Proceedings of the 2021 on International Symposium on Symbolic and Algebraic Computation
影响因子：
0
作者：
Kaltofen, Erich L.;Pernet, Clément;Yang, Zhi-Hong
通讯作者：
Yang, Zhi-Hong

Sparse Polynomial Hermite Interpolation

DOI：
10.1145/3476446.3535501
发表时间：
2022-07
期刊：
Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation
影响因子：
0
作者：
E. Kaltofen
通讯作者：
E. Kaltofen

Computing Higher Polynomial Discriminants

DOI：
10.1145/3452143.3465543
发表时间：
2021-07
期刊：
Proceedings of the 2021 on International Symposium on Symbolic and Algebraic Computation
影响因子：
0
作者：
E. Kaltofen
通讯作者：
E. Kaltofen

Hermite Rational Function Interpolation with Error Correction

带误差修正的 Hermite 有理函数插值