# How to sum up large number of elements in a table quickly?

I have been using Mathematica for some time now but I have a feeling that I am not using it as efficiently as it could be.

I have the following problem which I am unable to figure out and it would be great if someone could point me in the right direction:

I have a function which is of the following form:

f[x_]:= Total[A1/(A2+x),Infinity];


where A1 and A2 are very large arrays (2500x2500 real numbers) (Sorry for the way I wrote the function but I haven't figured out how to insert code into the question (not very good at this type of typesetting))

The problem is when I want to create another list (large list) of values of f[x]. It seems that Total is what slows things down here and I was wondering if there is a way to replace Total with something faster.

Any clues?

-
Are A1 and A2 different each time you call f or are they constant? –  wxffles Oct 11 '12 at 21:26
Mine is very fast, I can run about 10000 x values per second. What hardware are you using? –  s0rce Oct 11 '12 at 21:50
@user72409 actually, what are the exact sizes of A1 and A2? You said 2D Array, we've been using single arrays in answers... –  tkott Oct 11 '12 at 21:59
A1 and A2 are 2500x2500 (but this is an example, it could be more but let's go with this because I know that it takes about 10 mins on my machine). But as I said before, these remain constant. This was the whole idea. I wanted to precalculate them in order to gain speed, and I did but the final Table[f[x],{x,1,2500}], this takes 10 mins to calculate. –  lucian Oct 11 '12 at 22:06
6,000,000 >> 2000 –  wxffles Oct 11 '12 at 22:09

Have you tried Table instead of ParallelTable?

Anyway, here's an ugly way to get f a bit faster:

a1 = RandomReal[{0.1, 10}, 10000];
a2 = RandomReal[{0.1, 10}, 10000];


Original definition:

f[x_] := Total[a1/(a2 + x), Infinity]


slightly faster:

fc = Compile[
{{x, _Real}, {a1, _Real, 1}, {a2, _Real, 1}},
Module[{t = 0.},
Do[t = t + a1[[i]]/(a2[[i]] + x), {i, 1, Length[a1]}];
t
],
CompilationTarget -> "C"
];

Table[f[N@x], {x, 1, 2000}]; // Timing
Table[fc[N@x, a1, a2], {x, 1, 2000}]; // Timing
(*
{0.370212, Null}
{0.164774, Null}
*)


One possibility as to why ParallelTable is slower: it unpacks. Try:

SetSystemOptions[
"PackedArrayOptions" -> "UnpackMessage" -> True];

a1 = RandomReal[{0.1, 10}, 10000];
a2 = RandomReal[{0.1, 10}, 10000];

ParallelTable[f[x], {x, 1, 2000}]; // AbsoluteTiming
Table[f[x], {x, 1, 2000}]; // AbsoluteTiming


There is also added overhead when using ParallelTable. As tkott mentions in a comment, it would be helpful to know what a1 and a2 actually are (their dimensions).

-
you forgot the Total part :) –  tkott Oct 11 '12 at 21:53
I am afraid that I do not understand how you made f faster. Can you explain a bit more please? –  lucian Oct 11 '12 at 22:10
@user72409 sorry I botched the pasting and did not actually paste the faster version. In any case I don't know if this will remain faster for such large arrays (and it needs modification to work with 2D arrays anyway; perhaps you could mention this in your question!) –  acl Oct 11 '12 at 22:14
@acl Thank you fo the extensive post. I have never used Compile successfully but I will try and give it another go. –  lucian Oct 11 '12 at 22:27
@acl I tried running my problem using Table instead of ParallelTable but the latter is considerably faster. I get 649 seconds vs a lot more for the case of Table (I actually stopped it after it passed the 10 minute mark) –  lucian Oct 11 '12 at 22:31

I suspect that your arrays a1 and a2 are not packed, which would case a considerable slow-down.

Observe:

f[x_] := Total[a1/(a2 + x), -1]

n = Ceiling @ Sqrt @ 2000;

a1 = RandomReal[{-99, 99}, {n, n}];
a2 = RandomReal[{-99, 99}, {n, n}];

DeveloperPackedArrayQ /@ {a1, a2}


{True, True}

Table[f[i], {i, 1, 50000}] // AbsoluteTiming // First


1.0296018

{a1, a2} = DeveloperFromPackedArray /@ {a1, a2};

Table[f[i], {i, 1, 50000}] // AbsoluteTiming // First


66.1285161

-
ClearAll[f];
f[x_, a1_, a2_] := Total[a1/(a2 + x), Infinity];
{a1, a2} = RandomReal[{0, 1}, {2, 2000}];
Timing[f[#, a1, a2] & /@ RandomReal[{0, 1}, 2000]][[1]]


Takes under one second in my machine

-
Odd, I tried f[x_] = Total[a1/(a2 + x), Infinity] followed by Timing[f[#] & /@ RandomReal[{0, 1}, 2000]][[1]] and it is about 4 seconds on my machine vs 0.25 for your solution. I would have thought that precomputing the Total would have been faster. Any ideas? –  tkott Oct 11 '12 at 21:56
@tkott loss of packing –  Mr.Wizard Oct 11 '12 at 22:06
@tkott evaluate SetSystemOptions[PackedArrayOptions->UnpackMessage->True] and you'll see :) –  acl Oct 11 '12 at 22:07
@acl or shorter: On["Packing"] –  Mr.Wizard Oct 11 '12 at 22:11
@Mr.Wizard, @ acl ahh, thanks –  tkott Oct 12 '12 at 13:42