Exact solutions to linear systems of equations using output sensitive lifting
Exact solutions to linear systems of equations using output sensitive lifting
复制标题
使用输出敏感提升的线性方程组的精确解
DOI：
10.1145/1940475.1940513
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
D. Steffy
中科院分区：
文献类型：
--
作者：
D. Steffy
人们已经发展了许多方法来符号化地求解有理数上的线性方程组。一种常见的方法是使用p进提升或迭代细化来构建模块化或近似解，然后应用有理数重构。在应用合理重构之前，可以计算出这些算法必须执行的迭代次数的上限。在实践中，这样的界限可以是保守的。输出敏感提升是在算法中间步骤进行合理重构并验证正确性的技术，允许在求解规模较小时提前终止的可能性。在本文中，我们展示了如何使用适当的输出敏感提升策略来改进几种算法。我们证明了这种方法在计算上是有效的，并引入了一种迭代细化方法的变体，该方法将热启动纳入到合理的重建过程中。
Many methods have been developed to symbolically solve systems of linear equations over the rational numbers. A common approach is to use p-adic lifting or iterative refinement to build a modular or approximate solution, then apply rational number reconstruction. An upper bound can be computed on the number of iterations these algorithms must perform before applying rational reconstruction. In practice such bounds can be conservative. Output sensitive lifting is the technique of performing rational reconstruction at intermediate steps of the algorithm and verifying correctness which allows the possibility of early termination when the solution size is small. In this paper we show how using an appropriate output sensitive lifting strategy can improve several algorithms. We show this procedure to be computationally effective and introduce a variant of the iterative-refinement method that incorporates warm starts into the rational reconstruction procedure.