# Evaluating sums of subsets

Let $X=\{x_1,...,x_N\}$ be a set of real numbers. We consider $M$ sums over its subsets, e.g. $N=9$, $M=3$

\begin{align*} s_1&=x_1+x_2+x_3+x_9,\\ s_2&=x_1+x_2+x_4+x_9,\\ s_3&=x_1+x_2+x_5+x_9 \end{align*}

There are repeating subsums, e.g. $x_1+x_2+x_9$. If subsums are extracted and summed up separately, one needs 5 additions, while direct computation requires 9 additions.

In applied problem $N\sim10^6$, $M\sim10^9$ and many subsums are repeating. We expect significant speedup of the computation if the repeating subsums are recognized and extracted. Each sum has about $K\sim10^3$ terms. The structure of the sums is fixed once and forever, so we can do some preprocessing based on the structure of the sums to find the best evaluation order.

More details as requested by gnasher729: the real data in $X$ are permanently coming from a telescope. The summing is performed in a processing program, which tries to find signals matching a certain signature (localized in the sky, periodic in time, having certain drift in frequency bands). We hope to find a method for accelerating the program, not going deeper into processing specifics, but analyzing its summation pattern.

Is there any algorithm for doing this?

Thanks comment by D.W., the task can be formulated as optimization of vectorial addition chain. In the example above the chain can be converted from a form $$((-8,-7),(-6,1),(0,2)\downarrow,(-8,-7),(-5,4),(0,5)\downarrow,(-8,-7),(-4,7),(0,8)\downarrow)$$ to a form $$((-8,-7),(0,1),(-6,2)\downarrow,(-5,2)\downarrow,(-4,2)\downarrow).$$ Here downarrows show the places where the sums $s_1,s_2,s_3$ can be saved. Non-positive numbers $(-8...0)$ denote the variables $(x_1...x_9)$, positive numbers enumerate intermediate sums. The second sequence is shorter and may be even optimal. For the application purpose it is enough to obtain the output sequence much shorter than the input one.

The equivalent question then: is there an algorithm for compression of vectorial addition chains?

• This is related to the vectorial addition chain problem for $N$-dimensional vectors. Here there are $M$ target vectors instead of just one, and each target vector is sparse and has entries that are zero or one. It's possible you might be able to use some of the techniques for that problem to solve your situation. – D.W. Feb 8 '17 at 3:52
• Just saying: You have about 10^12 indices here. Unless you can generate these indices somehow, I'd like to know what kind of hardware you've got to handle this. If you can generate the indices, please tell us how they are generated. – gnasher729 Feb 8 '17 at 22:39
• Maybe I didn't make that clear enough. You have a billion sums, adding array elements given by 1000 indices, that's a trillion indices. Unless these indices are created in some systematic way, there's no way you can handle a trillion indices. I can tell you how to easily save half the additions - but it's pointless if you have a trillion indices, using multiple terabytes of virtual memory. So what is the system behind the billion sums? – gnasher729 Feb 9 '17 at 22:28
• The processing program reserves 4Mb of memory for storing $x_i$. Then it selects combinations and sums them up. Together it makes $10^{12}$ additions and requires some hours on one CPU or faster if we run it in parallel on several CPUs. Selection of combinations is performed by algorithms XYZ, where X is designed for a search of periodical sequences (pulsars), Y detects phase shift linearly increasing with the frequency (dispersion on interstellar medium), Z averages the result in a moving window in the sky... – Igor Feb 10 '17 at 9:50
• The question was about the possibility to accelerate significantly the processing, knowing only summation pattern, not the details of XYZ. Summation pattern can be streamed out from the program during its execution and saved to a disk, requiring 4Tb space. If it is absolutely necessary to store the whole summation matrix in memory, we can downscale the problem by considering shorter datasets or/and using some block diagonal structures we can recognize in the matrix. – Igor Feb 10 '17 at 9:50