MathGroup Archive 2009

[Date Index] [Thread Index] [Author Index]

Search the Archive

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


  • Prev by Date: Re: Synchronous zooming of 3D graphics
  • Next by Date: Re: Can I Mapthis code?
  • Previous by thread: Taking sums across indices of a SparseArray efficiently
  • Next by thread: Re: Taking sums across indices of a SparseArray efficiently