Hi

What is the best way to apply prefix sum operation to Eigen types?

Use the .sum() member function, for instance

Code: Select all

VectorXd vec = VectorXd::Random(5);
std::cout << "Sum of coefficients is " << vec.sum() << std::endl;


If you really want to use sum as a prefix operator and write "sum(vec)" then you have to define the sum() function yourself.

I think wingsit meant:

VectorXf vec = VectorXf::Random(100);
for(int j=1; j<vec.size(); ++j)
vec(j) += vec(j-1);

and for that there is no built-in function is Eigen yet.

ggael wrote:I think wingsit meant:

VectorXf vec = VectorXf::Random(100);
for(int j=1; j<vec.size(); ++j)
vec(j) += vec(j-1);

and for that there is no built-in function is Eigen yet.

yes that is what I am asking but meant to have more generic operation then just sum. Any plan to extend on that direction?

Is it almost optimal to write a loop similar to above?

yes we could imagine a generic implementation with a meta unroller for small fixed sizes. The simplest would be an in-place API and implementation. This would be a good exercise to anyone who would like to start knowing more about Eigen's internal.

Regarding optimizations there exist a parallel algorithm to compute a prefix sum. Very useful on GPU to process scattered data. The parallel version is quite complex though.

edit: I forgot to mention that the generic algo could also handle rowwise/colwise operation.

Also, do you have use cases for similar algo but with a different operation than sum?

ggael wrote:yes we could imagine a generic implementation with a meta unroller for small fixed sizes. The simplest would be an in-place API and implementation. This would be a good exercise to anyone who would like to start knowing more about Eigen's internal.

Regarding optimizations there exist a parallel algorithm to compute a prefix sum. Very useful on GPU to process scattered data. The parallel version is quite complex though.

edit: I forgot to mention that the generic algo could also handle rowwise/colwise operation.

Also, do you have use cases for similar algo but with a different operation than sum?

I looked at the GPU algorithm at some point but it might be overkill on few cores. I want to apply prefix sum operation for time series calcuation

For arma model in time series, we have to compute new estimate based on historical observation and historical estimation

so it it does something like

a[]
b[]

for loop:
a[i] = f(a[indices before i], b[indices before i])

where in arma case, f is just a linear combination of the historical a and b, but can be slightly nonlinear (squares) for variance model.

Just want to see how to write optimal code in Eigen environment.

reference for Autoregressive moving average model
http://en.wikipedia.org/wiki/Autoregres ... rage_model
Thanks for the good respond thus far.

I guess you may also consider using std::accumulate with a custom functor or lambda (e.g., to perform ARMA multiplication/addition) with iterators obtained through "data" member function.

mattd wrote:I guess you may also consider using std::accumulate with a custom functor or lambda (e.g., to perform ARMA multiplication/addition) with iterators obtained through "data" member function.

I think this is more of a std::partial_sum algorithm.