performance tuning - Adding three integer sparse matrices is very slow. Adding only two is fast

Bug introduced in 9.0.0 and fixed in 10.0.0

---

Adding more than two sparse matrices in one step in Mathematica 9 is very slow (in fact I couldn't even wait for it to finish).

Here's an example. Let's generate a large sparse matrix:

am = AdjacencyMatrix@RandomGraph[{25000, 50000}];

am + am; // Timing (* very fast *)

(am + am) + am; // Timing (* very fast *)


am + am + am; // Timing (* so slow I didn't wait for it to finish *)

Can anyone reproduce this? I used Mathematica 9.0.0 on OS X. Mathematica 8 does not have this problem.

Does anyone have any ideas what may be going wrong here?

Answer

I have reported this as a bug. Having said that, here is some more info:

Note that when you use:

am = AdjacencyMatrix@RandomGraph[{25000, 50000}];//N

you do not see the issue. So this is only an integer sparse array issue. What happened until V8 internally is that there is a loop for adding each sparse array as a binary operation. E.g. something like:

res = Plus[Plus[sp1,sp2],sp3]

In version 9 this has been changed to use var args. In essence what you do with using parentheses is to enforce the old behavior. The reason this was changed is that the var args form of the code is faster and uses less memory:

am = (AdjacencyMatrix@RandomGraph[{2500, 5000}]) // N;
MaxMemoryUsed[am + am; // Timing] (*very fast*)
MaxMemoryUsed[(am + am) + am; // Timing] (*very fast*)
MaxMemoryUsed[
 am + am + am; // Timing] (*so slow I didn't wait for it to finish*)

So for now you can either convert with N if that is possible, or use the parentheses.