Hermite Rational Function Interpolation with Error Correction
Hermite Rational Function Interpolation with Error Correction
复制标题
带误差修正的 Hermite 有理函数插值
DOI：
10.1007/978-3-030-60026-6_19
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Yang, Zhi-Hong
中科院分区：
文献类型：
--
作者：
Kaltofen, Erich L.;Pernet, Clement;Yang, Zhi-Hong
本文将多重代数纠错码中的带纠错的Hermite插值方法推广到域上有理函数的Hermite插值，由函数和函数的导数值给出了一种插值算法，该算法能在不同的参数上定位和纠正错误，其中至少有一个值或导数值是错误的.输入的此类数的上限E。我们的算法充分过采样的有理函数，以保证一个唯一的插值。我们对，，distinct进行采样，其中是有理函数f/g的j阶导数，其中 n = ∑ 我 = 1 n ( ℓ 我 + 1 ) ≥ D F + D G + 1 + 2 e + 2 ∑ K = 1 e ℓ K ;是的上界和的上界，它们是我们算法的输入。自变量可以是极点，它的真假由一个函数值来表示。我们的结果仍然有效的fieldsof特征。该算法具有与经典Hermite插值算法相同的渐近运算复杂度，对于多项式，即，，和均匀导数轮廓，该算法专门用于基于1986年Welch-Berlekamp算法的单变量多重码译码器。
We generalize Hermite interpolation with error correction, which is the methodology for multiplicity algebraic error correction codes, to Hermite interpolation of a rational function over a fieldfrom function and function derivative values.We present an interpolation algorithm that can locate and correcterrors at distinct argumentswhere at least one of the values or values of a derivative is incorrect. The upper boundEfor the number of suchis input. Our algorithm sufficiently oversamples the rational function to guarantee a unique interpolant. We samplefor,,distinct, whereis thej-th derivative of the rational functionf/g,,,, and where N = ∑ i = 1 n ( ℓ i + 1 ) ≥ D f + D g + 1 + 2 E + 2 ∑ k = 1 E ℓ k ;is an upper bound forandan upper bound for, which are input to our algorithm. The argumentscan be poles, which is truly or falsely indicated by a function valuewith the corresponding. Our results remain valid for fieldsof characteristic. Our algorithm has the same asymptotic arithmetic complexity as that for classical Hermite interpolation, namely.For polynomials, that is,, and a uniform derivative profile, our algorithm specializes to the univariate multiplicity code decoder that is based on the 1986 Welch-Berlekamp algorithm.
登录
查看更多内容
从带有噪声和异常值错误的值中恢复稀疏多元函数
DOI：
10.1145/2465506.2465524
发表时间：
2013
期刊：
J. Symb. Comput.
影响因子：
--
作者：
E. Kaltofen;Zhengfeng Yang
通讯作者：
Zhengfeng Yang
DOI：
10.1145/2608628.2608637
发表时间：
2014
期刊：
J. Symb. Comput.
影响因子：
--
作者：
E. Kaltofen;Zhengfeng Yang
通讯作者：
Zhengfeng Yang
GCD 的快速计算
DOI：
10.1145/800125.804045
发表时间：
1973
期刊：
Proceedings of the fifth annual ACM symposium on Theory of computing
影响因子：
--
作者：
R. Moenck
通讯作者：
R. Moenck
参数线性系统求解的提前终止和带误差修正的有理函数向量恢复
DOI：
10.1145/3087604.3087645
发表时间：
2017
期刊：
Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation
影响因子：
--
作者：
E. Kaltofen;Clément Pernet;A. Storjohann;Cleveland Waddell
通讯作者：
Cleveland Waddell
关于多重码的一些说明
DOI：
10.1090/conm/625/12497
发表时间：
2015
期刊：
ArXiv
影响因子：
--
作者：
Swastik Kopparty
通讯作者：
Swastik Kopparty