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。在代数计算复杂性中的基本问题中，它需要重新研究多项式乘法和最大的常见分歧。学生和博士后学者，以便他们在设计用于数学的算法和计算机程序方面发展了高级技能。将鼓励学生和博士后通过在国际会议上介绍海报和演讲来采取高级研究沟通技巧，尤其是当他们的背景来自该学科中的代表性不足的群体时。实现低成本认证目标的方法是为稀疏矩阵的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
期刊：
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 有理函数插值