python - 计算 "polynomial coefficient"的 numpy/scipy 函数

Question

是否有计算 x**r 系数的 python 函数(可能来自 numpy 或 scipy)在扩展(1+x+x**2+x**3+...+x**(k-1))**n , 其中k>=1 , n>=0和 0<=r<=n(k-1) ？

这有时称为多项式系数 (PC)(例如，参见 here)。

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

Answer 1

您实际上是在对 [1, 1, 1, ..., 1, 1, 1] 进行 n 次卷积。
因此，您是否考虑过对足够零填充的数组使用 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);

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

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