Early Termination in Parametric Linear System Solving and Rational Function Vector Recovery with Error Correction
Early Termination in Parametric Linear System Solving and Rational Function Vector Recovery with Error Correction
复制标题
参数线性系统求解的提前终止和带误差修正的有理函数向量恢复
DOI：
10.1145/3087604.3087645
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Cleveland Waddell
中科院分区：
文献类型：
--
作者：
E. Kaltofen;Clément Pernet;A. Storjohann;Cleveland Waddell
考虑求解黑框线性系统，A（U）X = B（U），其中条目在u上是u上的多项式，而A（u）是完整的，x = 1/g（U） ）f（u），g始终是最不常见的一元分母，可以通过在K中的不同点评估系统。即使在[Boyer和Kaltofen，Proc。 SNC 2014]问题解决了通过将代数芦苇代码的Welch/Berlekamp解码的算法，他们的算法需要绑定的学位，以及对于解决方案的分解器的度数。算法大高估了实际的学位。基于斯坦利·卡巴伊（Stanley Cabay）的工作需要恢复解决方案。到达。 Cabay计数少于我们的两个计数。理性函数的向量，1/g（u）f（u），从其评估中，如果理性函数向量是对完整等级线性系统的解决方案如果我们允许在Poles（G的根）进行评估，我们可能会从更少的评估中恢复它。如果除了指出评估点是一个极点外，黑匣子还提供了有关在评估点上解决方案数值的信息。
Consider solving a black box linear system, A(u) x = b(u), where the entries are polynomials in u over a field K, and A(u) is full rank. The solution, x = 1/g(u) f(u), where g is always the least common monic denominator, can be found by evaluating the system at distinct points ξl in K. The solution can be recovered even if some evaluations are erroneous. In [Boyer and Kaltofen, Proc. SNC 2014] the problem is solved with an algorithm that generalizes Welch/Berlekamp decoding of an algebraic Reed-Solomon code. Their algorithm requires the sum of a degree bound for the numerators plus a degree bound for the denominator of the solution. It is possible that the degree bounds input to their algorithm grossly overestimate the actual degrees. We describe an algorithm that given the same inputs uses possibly fewer evaluations to compute the solution. We introduce a second count for the number of evaluations required to recover the solution based on work by Stanley Cabay. The Cabay count includes bounds for the highest degree polynomial in the coefficient matrix and right side vector, but does not require solution degree bounds. Instead our algorithm iterates until the Cabay termination criterion is reached. At this point our algorithm returns the solution. Assuming we have the actual degrees for all necessary input parameters, we give the criterion that determines when the Cabay count is fewer than the generalized Welch/Berlekamp count. Incorporating our two counts we develop a combined early termination algorithm. We then specialize the algorithm in [Boyer and Kaltofen, Proc. SNC 2014] for parametric linear system solving to the recovery of a vector of rational functions, 1/g(u) f(u), from its evaluations. Thus, if the rational function vector is the solution to a full rank linear system our early termination strategy applies and we may recover it from fewer evaluations than generalized Welch/Berlekamp decoding. If we allow evaluations at poles (roots of g) there are examples where the Cabay count is not sufficient to recover the rational function vector from just its evaluations. This problem is solved if in addition to indicating that an evaluation point is a pole, the black box gives information about the numerators of the solution at the evaluation point.