An a posteriori certification algorithm for Newton homotopies
An a posteriori certification algorithm for Newton homotopies
复制标题
牛顿同伦的后验证明算法
DOI：
10.1145/2608628.2608651
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Alan C. Liddell
中科院分区：
文献类型：
--
作者：
J. Hauenstein;Ian Haywood;Alan C. Liddell
牛顿同伦是只涉及改变常数项的同伦。例如，当执行单向循环、移动机器人的末端执行器时，以及简单地试图计算平方方程组的解时，它们自然会出现。以前的认证路径跟踪技术侧重于使用先验认证的跟踪方案，这意味着构造步长使得结果自动满足某些条件。这些方案使用的悲观步长可能比启发式跟踪方法使用的步长小得多。本文设计了一种后验认证方案，它使用启发式跟踪方案的结果作为输入，以产生路径确实被正确跟踪的证书，例如，没有发生路径跳跃。通过使用后验方法，可以独立地验证每个步骤，从而可以并行地执行路径验证。给出的例子证明了这种后验认证方法的有效性。
A Newton homotopy is a homotopy that involves changing only the constant terms. They arise naturally, for example, when performing monodromy loops, moving end effectors of robots, and simply when trying to compute a solution to a square system of equations. Previous certified path tracking techniques have focused on using an a priori certified tracking scheme which means that the stepsize is constructed so that the result automatically satisfies some conditions. These schemes use pessimistic stepsizes that can be much smaller than those used by heuristic tracking methods. This article designs an a posteriori certification scheme that uses the result of a heuristic tracking scheme as input to produce a certificate that the path was indeed tracked correctly, e.g., no path jumpings occurred. By using an a posteriori approach, each step can be certified independently and thus certification of the path can be performed in parallel. Examples are presented demonstrating the efficiency of this a posteriori certification approach.