Re: Taking sums across indices of a SparseArray efficiently

*To*: mathgroup at smc.vnet.net*Subject*: [mg95969] Re: [mg95926] Taking sums across indices of a SparseArray efficiently*From*: DrMajorBob <btreat1 at austin.rr.com>*Date*: Sat, 31 Jan 2009 01:12:59 -0500 (EST)*References*: <200901301042.FAA06408@smc.vnet.net>*Reply-to*: drmajorbob at longhorns.com

There may be a much easier way, but here goes... Here's a large 4-dimensional sparse array: s = SparseArray[ Table[{Mod[i, 7, 1], Mod[i^2, 11, 1], Prime@i, PrimePi@i} -> i, {i, 2, 1000}]]; Dimensions@s {7, 11, 7919, 168} A helper function applied to its rules gives a set of rules for a 2-dimensional matrix: Clear[rule12] rule12[x_List -> v_] := Take[x, 2] -> v u = Sort[rule12 /@ ArrayRules@s]; Length@u 1000 The matrix u has repeats, however, so it can't immediately be turned into a sparse array. Another helper array (reinitialize it for each new problem), applied to this one: Clear[sum12] sum12[{i_, j_} -> v_] := sum12[{i, j}] += v sum12[__] = 0; sum12 /@ u; That DEFINES the sum12 function for entries of the following 2-dimensional matrix: twodim=SparseArray@Array[sum12@{##}&,{7,7}] SparseArray[<28>,{7,7}] or Normal@twodim {{12583, 0, 13585, 13585, 12584, 0, 0}, {13156, 0, 13156, 12155, 13156, 0, 0}, {12727, 0, 12727, 12727, 13728, 0, 0}, {13299, 0, 13299, 13299, 12298, 0, 0}, {12870, 0, 12870, 13871, 12870, 0, 0}, {13442, 0, 12441, 12441, 13442, 0, 0}, {13013, 0, 13013, 13013, 13013, 0, 0}} Some of the entries are zero, but "twodim" has no wasted rules: ArrayRules@twodim {{1, 1} -> 12583, {1, 3} -> 13585, {1, 4} -> 13585, {1, 5} -> 12584, {2, 1} -> 13156, {2, 3} -> 13156, {2, 4} -> 12155, {2, 5} -> 13156, {3, 1} -> 12727, {3, 3} -> 12727, {3, 4} -> 12727, {3, 5} -> 13728, {4, 1} -> 13299, {4, 3} -> 13299, {4, 4} -> 13299, {4, 5} -> 12298, {5, 1} -> 12870, {5, 3} -> 12870, {5, 4} -> 13871, {5, 5} -> 12870, {6, 1} -> 13442, {6, 3} -> 12441, {6, 4} -> 12441, {6, 5} -> 13442, {7, 1} -> 13013, {7, 3} -> 13013, {7, 4} -> 13013, {7, 5} -> 13013, {_, _} -> 0} Bobby On Fri, 30 Jan 2009 04:42:22 -0600, D. Grady <D.C.Grady at gmail.com> 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 > -- DrMajorBob at longhorns.com

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