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

符号计算的一个特点是输出是准确的。数字纠错译码从其中某些条目不正确的输入产生准确的输出，并将所需的冗余度降至最低。符号多项式插值算法利用了稀疏性。卡尔托芬建议创建一种算法，可以根据某些值不正确的情况对稀疏的单变量和多变量多项式以及有理函数进行内插。目标是将定位和纠正这些错误评估所需的过抽样量降至最低。混合符号-数值计算接受输入中的近似标量条目，这可能是不精确的，因为它们来自浮点计算或物理测量。稀疏多元多项式内插已适用于此类数据，目的是为观测到的测量数据构建稀疏模型，Kaltofen建议创建我们的插补算法的符号-数字混合版本，以纠正离群值误差。此外，Kaltofen建议为复杂的非线性问题构造易于验证的证书，例如实数多元多项式是无界的或对称实数矩阵是正定的证书。这两个问题对于全局非线性优化都很重要。最后，Kaltofen建议将Berlekamp/Massey算法的矩阵推广和Shojiro Sakata的多维推广应用于具有多项式系数的递归，例如阶乘序列和二项系数。他还将研究如何纠正线性生成阵列中的错误。Kaltofen提出的研究将符号-数值计算与数字纠错解码相结合，目的是消除稀疏模型综合中的离群值，这构成了一种全新的数据集错误清理方法。证明计算的最小值是全局最小值的证书允许在优化方法中使用未经证实的算法启发式，特别是使用不分析稳定性的浮点算法的算法，并极大地拓宽了可以放置在可发布软件中的范围：程序不会给出错误的输出。最后，递归是符号计算算法中的基本工具。Kaltofen正在免费提供为这些算法开发的软件。

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.