Re: Taking sums across indices of a SparseArray efficiently
- To: mathgroup at smc.vnet.net
- Subject: [mg96053] Re: Taking sums across indices of a SparseArray efficiently
- From: "D. Grady" <D.C.Grady at gmail.com>
- Date: Tue, 3 Feb 2009 06:32:52 -0500 (EST)
- References: <200901301042.FAA06408@smc.vnet.net> <gm0q2n$rle$1@smc.vnet.net>
On Jan 31, 12:11 am, Carl Woll <ca... at wolfram.com> wrote:
> 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
What if I want to sum across just the 3rd index of an n-dimensional
array? Can this still be made to work?
-Daniel