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>
- Taking sums across indices of a SparseArray efficiently