Re: Taking sums across indices of a SparseArray efficiently

*To*: mathgroup at smc.vnet.net*Subject*: [mg95961] Re: [mg95926] Taking sums across indices of a SparseArray efficiently*From*: Carl Woll <carlw at wolfram.com>*Date*: Sat, 31 Jan 2009 01:11:31 -0500 (EST)*References*: <200901301042.FAA06408@smc.vnet.net>

D. Grady wrote: >Suppose we've got a four-dimensional array: > >t = Array[Subscript[w, ##] &, {3, 3, 3, 3}] > >If we want to take the sum across one index of this array (which will >reduce its dimension), we can use the Total function: > >Dimensions@Total[t, {2}] >{3, 3, 3} > >In the problem I'm working on, I've got an array and I need to sum >across the first two dimensions. Using this toy array, I can see that >Total[t,{1,2}] gives me exactly the object that I want. The problem >is that I'm working with a four-dimensional sparse array, and Total >will apparently always try to convert its first argument to a normal >array. This fails because the array is too big to fit in memory: > >In[26]:= WAF = Total[W, {1, 2}]; // Timing > >During evaluation of In[26]:= SparseArray::ntb: Cannot convert the >sparse array SparseArray[Automatic,{489,489,489,489},0,{<<1>>}] to an >ordinary array because the 57178852641 elements required exceeds the >current size limit. >> > >Out[26]= SystemException[SparseArrayNormalLimit,Normal[SparseArray >[<1400152>,{489,489,489,489}]]] > >I can roll my own function to do this computation just by sorting >through the ArrayRules: > >Timing[ > WAF = > SparseArray@( > (#[[1, 1, 3 ;; 4]] -> Total[#[[All, 2]]] &) /@ > (SplitBy[#, Drop[First@#, 2] &] &)@ > (SortBy[#, Drop[First@#, 2] &] &)@ > Most@ > ArrayRules@ > W)] > >{22.1335,SparseArray[<21122>,{489,489}]} > >The point is that actually doing the computation isn't particularly >memory or time intensive, but I can't find a simple way to do this >directly using built-in functions like Total. Does anyone know if >there is a way? If there isn't, why not? Thanks a lot! > >-Daniel > > > Another workaround is to use Dot. Here is a toy array: In[31]:= toy = SparseArray[{i_, j_, k_, l_} -> i + j - k + l, {4, 4, 4, 4}] Out[31]= SparseArray[<252>,{4,4,4,4}] In[32]:= Total[toy, {1, 2}] Out[32]= {{80, 96, 112, 128}, {64, 80, 96, 112}, {48, 64, 80, 96}, {32, 48, 64, 80}} In[33]:= SparseArray[_ -> 1, 4].(SparseArray[_ -> 1, 4].toy) Out[33]= SparseArray[<16>,{4,4}] In[34]:= % // Normal Out[34]= {{80, 96, 112, 128}, {64, 80, 96, 112}, {48, 64, 80, 96}, {32, 48, 64, 80}} Carl Woll Wolfram Research

**References**:**Taking sums across indices of a SparseArray efficiently***From:*"D. Grady" <D.C.Grady@gmail.com>