论文标题
多项式操作的快速入境算法：分裂，评估，插值
Fast In-place Algorithms for Polynomial Operations: Division, Evaluation, Interpolation
论文作者
论文摘要
我们考虑了单变量多项式的几个重要操作的节省空间版本，即功率序列反转和分裂，剩余，多点评估和插值。现在古典的结果表明，可以在（几乎）与快速多项式乘法相同的渐近时间（几乎）解决此类问题。但是，这些降低即使应用于快速多项式乘法的地面变体，也会产生至少需要线性量的额外空间才能进行中间结果。我们展示了上述多项式计算的新的原位算法，这些算法仅需要持续的额外空间，并达到与现场的渐近运行时间相同的渐近运行时间。我们还提供了精确的复杂性分析，以使所有常数都被显式化，并通过基础乘法算法的空间使用进行参数化。
We consider space-saving versions of several important operations on univariate polynomials, namely power series inversion and division, division with remainder, multi-point evaluation, and interpolation. Now-classical results show that such problems can be solved in (nearly) the same asymptotic time as fast polynomial multiplication. However, these reductions, even when applied to an in-place variant of fast polynomial multiplication, yield algorithms which require at least a linear amount of extra space for intermediate results. We demonstrate new in-place algorithms for the aforementioned polynomial computations which require only constant extra space and achieve the same asymptotic running time as their out-of-place counterparts. We also provide a precise complexity analysis so that all constants are made explicit, parameterized by the space usage of the underlying multiplication algorithms.
