寻找内存有效的外积和

Question

我有一个公式：

其中a和b是大小为n和m的1D数组。我希望避免在中间步骤中形成大小为n*m的任何数组，因为n和m都非常大，所需的内存将非常昂贵。你知道吗

一种解决方案是简单的python循环：

total = 0
for j in range(n):
    total += a[j] * b**j

我正在寻找一个没有python循环的原生numpy解决方案。但是要在没有python循环的情况下解决这个问题，我找不到一个numpy函数，它可以在不形成[0*b，b，b**2，b**3，…]的n×m数组作为输入的情况下工作。你知道吗

编辑：

正如hpaulj所指出的，多项式解可能是可行的。我发现这个：

from numpy.polynomial import polynomial
total = polynomial.polyval(b, a)

这在快速测试中给出了相同的值，根据polyval上的注释，它使用了Horner的方法，似乎是最优的。我的问题实际上是两个维度上的和，但我认为这个解决方案可以推广。你知道吗

编辑2：

波里瓦尔似乎引起了

RuntimeWarning: overflow encountered in multiply c0 = c[-i] + c0*x

数组大小小于偶数np.外部导致内存错误。当它工作时，它比python循环快得多。你知道吗

编辑3：

忽略编辑1和2。下面的代码使用python循环运行得更快（在我的机器上）。polyval至少看起来是内存有效的。你知道吗

import numpy as np
from numpy.polynomial import polynomial
a_size = 3
b_size = 6
a = np.random.rand(10**a_size)
b = np.exp(2j * np.pi * np.random.rand(10**b_size))
start = time.time()
c = polynomial.polyval(b, a)
middle = time.time()
print(middle - start)
c2, b_current = 0, b**0
for i in range(0, a.size):
    c2 += a[i] * b_current
    b_current *= b
end = time.time()
print(end-middle)