Combining Uneliminated Algebraic Formulations With Sparse Linear Solvers to Increase the Speed and Accuracy of Homotopy Path Tracking for Kinematic Synthesis
Combining Uneliminated Algebraic Formulations With Sparse Linear Solvers to Increase the Speed and Accuracy of Homotopy Path Tracking for Kinematic Synthesis
复制标题
将未消除代数公式与稀疏线性求解器相结合，提高运动学综合同伦路径跟踪的速度和精度
DOI：
10.1115/1.4055241
复制
发表时间：
2022
影响因子：
3.1
通讯作者：
Plecnik, Mark
中科院分区：
文献类型：
--
作者：
Glabe, Jeffrey;Plecnik, Mark
运动学综合的方法要求找到多项式系统的解集。参数同伦连续用于解决这些系统，需要反复求解线性方程组。对于运动学综合，相关的线性系统变得病态，导致由于路径跟踪失败而发现的解决方案的数量显着减少。这种不可避免的病态要求精确的函数和矩阵求值。传统上，消除变量以减少问题的维度。然而，这大大增加了计算所得函数和矩阵的计算成本，并引入了数值不稳定性。我们建议避免消除变量，以减少所需的计算，增加线性系统的维数，但导致矩阵是相当稀疏的。然后，我们用稀疏求解器来解决这些系统，以节省内存并提高速度。我们发现，这种组合比传统方法的速度提高了250倍，同时保持了相同的精度。
The method of kinematic synthesis requires finding the solution set of a system of polynomials. Parameter homotopy continuation is used to solve these systems and requires repeatedly solving systems of linear equations. For kinematic synthesis, the associated linear systems become ill-conditioned, resulting in a marked decrease in the number of solutions found due to path tracking failures. This unavoidable ill-conditioning places a premium on accurate function and matrix evaluations. Traditionally, variables are eliminated to reduce the dimension of the problem. However, this greatly increases the computational cost of evaluating the resulting functions and matrices and introduces numerical instability. We propose avoiding the elimination of variables to reduce required computations, increasing the dimension of the linear systems, but resulting in matrices that are quite sparse. We then solve these systems with sparse solvers to save memory and increase speed. We found that this combination resulted in a speedup of up to 250 × over traditional methods while maintaining the same accuracy.