python - 用于计算“多项式系数”的 numpy/scipy 函数

Question

是否有任何 python 函数（可能来自 numpy 或 scipy）计算、where和x**r展开中的系数？(1+x+x**2+x**3+...+x**(k-1))**nk>=1n>=00<=r<=n(k-1)

这有时称为多项式系数 (PC)（例如，请参见此处）。

如果没有，你能想出一种有效的计算方法吗？（我对天真/贪婪的方式不感兴趣）。

Answer 1

您实际上是在进行n[1, 1, 1, ..., 1, 1, 1] 的折叠卷积。
因此，您是否考虑过在充分零填充的数组上使用 FFT，将其元素提升到幂n并使用逆 FFT 来恢复

(1+x+x**2+x**3+...+x**(k-1))**n

然后只是阅读你感兴趣的那些？

更新：

由于 FFT 是循环的，因此您需要一个不小于

(1+x+x**2+x**3+...+x**(k-1))**n

或者，换句话说，(k-1)*n+1这样结果就不会在末端环绕（或者至少在它们这样做时它们只会向受影响的元素添加零）。通常它的长度也应该是 2 的幂，因为这是 FFT 算法所要求的（不需要它的实现将用零填充您的输入，直到它这样做）。

在类 C 的伪代码中：

unsigned int m = 1;
while(m<(k-1)*n+1) m *= 2;

complex c[m];
for(unsigned int i=0;i!=k;++i) c[i] = complex(1.0, 0.0);
for(unsigned int i=k;i!=m;++i) c[i] = complex(0.0, 0.0);

c = fft(c);
for(unsigned int i=0;i!=m;++i) c[i] = pow(c[i], double(n));
c = inv_fft(c);

最后，r复数数组的第 ' 个元素的c实部等于 的系数，x**r虚部为零。
现在，由于这一切都是在浮点中完成的，您应该知道这些元素将累积舍入误差。您可以通过将它们四舍五入到最接近的整数来部分纠正此问题，但请注意，如果足够大k，n这些误差将超过 0.5，因此这可能会产生一些相对较小的误差。

在网络上的快速搜索显示，numpy 具有 FFT 及其逆的实现，当输入数据为真实时numpy.fft.rfft，numpy.fft.irfft您可以分别使用它们。