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