Parallel base sum computation

[eigmax]

When we evaluate some point x on a polynomial p(a_0, ..., a_d), we usually have such a function:

a_0 + x * ( a_1 + x * ( ...  x * a_d ... ))

I think we can convert it to the classical prefix sum problem, by which, given an input array a[0..n], we output b[0..n], where b[i] = sum_j (a[j]), j < i.

i.e.

out[0] = 0; for j from 1 to n do   out[j] = out[j-1] + f(in[j-1]); 

TBD

Reference: https://developer.nvidia.cn/gpugems/gpugems3/part-vi-gpu-computing/chapter-39-parallel-prefix-sum-scan-cuda