AF: Small: Symbolic computation with sparsity, error checking and error correction

AF：小：具有稀疏性、错误检查和纠错的符号计算

• 批准号: 1421128
• 负责人: Erich Kaltofen
• 金额: $ 46.99万
• 依托单位: North Carolina State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-09-01 至 2018-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1421128&HistoricalAwards=false
• 关键词: AF; Small; Symbolic; computation; sparsity

A hallmark of symbolic computation is that the outputs are exact. Digital error correcting decoding produces exact outputs from inputs in which some entries are incorrect, and minimizes the required redundancy. Symbolic polynomial interpolation algorithms take advantage of sparsity. Kaltofen proposes to create algorithms that can interpolate sparse uni- and multivariate polynomials and rational functions from evaluations where some of the values are incorrect. A goal is to minimize the amount of oversampling that is necessary to locate and correct those faulty evaluations. Hybrid symbolic-numeric computation accepts approximate scalar entries in the inputs, which can be imprecise because they come from a floating point computation or a physical measurement. Sparse multivariate polynomial interpolation has been adapted to such data, for purpose of constructing sparse models for the observed measurements, and Kaltofen proposes to create hybrid symbolic-numeric versions of our interpolation algorithms that can correct outlier errors. In addition, Kaltofen proposes to construct easily verifiable certificates for complex non-linear problems, such as certificates that a real multivariate polynomial is unbounded or that a symmetric real matrix is positive definite. Both problems are important for global non-linear optimization. Lastly, Kaltofen proposes to apply the matrix generalization of the Berlekamp/Massey algorithm and the multidimensional generalization by Shojiro Sakata to recurrences with polynomial coefficients, such as the sequence of the factorials and the binomial coefficients. He will also study how to correct errors in the linear generated arrays.Kaltofen's proposed research combines hybrid symbolic-numeric computation with digital error-correcting decoding for purpose of removing outliers in sparse model synthesis, which constitutes a brand-new approach for ``cleaning-up'' errors in data sets. Certificates that prove that computed minima are global minima permit the use of unproven algorithmic heuristics in the optimization methods, especially algorithms with floating point arithmetic whose stability is not analyzed, and greatly broaden what can be placed in publishable software: the programs do not give a false output. Lastly, recurrences are fundamental tools in symbolic computation algorithms. Kaltofen is making the developed software for the algorithms freely available.

符号计算的一个特点是输出是精确的。数字纠错解码从某些条目不正确的输入中产生精确的输出，并最大限度地减少所需的冗余。 符号多项式插值算法利用稀疏性。 Kaltofen提出创建算法，可以从某些值不正确的评估中插值稀疏的单变量和多变量多项式以及有理函数。 目标是最小化定位和纠正这些错误评估所需的过采样量。 混合符号-数字计算接受输入中的近似标量项，这可能是不精确的，因为它们来自浮点计算或物理测量。 稀疏多变量多项式插值已适应于这样的数据，为所观察到的测量值构建稀疏模型的目的，Kaltofen提出创建混合符号-数值版本的插值算法，可以纠正离群值误差。此外，Kaltofen提出为复杂的非线性问题构建易于验证的证书，例如证明真实的多元多项式是无界的或对称的真实的矩阵是正定的。 这两个问题对于全局非线性优化都很重要。 最后，Kaltofen提出将Berlekamp/Massey算法的矩阵推广和Shojiro Sakata的多维推广应用于多项式系数的递归，例如因子和二项式系数的序列。 Kaltofen的研究将符号-数值混合计算与数字纠错解码相结合，以去除稀疏模型合成中的异常值，这构成了一种全新的数据集“清理”错误的方法。证明计算的最小值是全局最小值的证书允许在优化方法中使用未经证明的算法逻辑，特别是具有浮点运算的算法，其稳定性未被分析，并且大大拓宽了可以放置在可编程软件中的内容：程序不会给出错误输出。 最后，递归是符号计算算法中的基本工具。 Kaltofen正在免费提供为算法开发的软件。

项目成果

Sparse Polynomial Interpolation With Arbitrary Orthogonal Polynomial Bases

任意正交多项式基的稀疏多项式插值

• DOI: 10.1145/3208976.3208999
• 发表时间: 2018
• 期刊: Proc. 2018 ACM International Symposium on Symbolic and Algebraic Computation
• 作者: Imamoglu, Erdal;Kaltofen, Erich L.;Yang, Zhengfeng
• 通讯作者: Yang, Zhengfeng