MathGroup Archive 2009

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

Search the Archive

Taking sums across indices of a SparseArray efficiently

  • To: mathgroup at smc.vnet.net
  • Subject: [mg95926] Taking sums across indices of a SparseArray efficiently
  • From: "D. Grady" <D.C.Grady at gmail.com>
  • Date: Fri, 30 Jan 2009 05:42:22 -0500 (EST)

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


  • Prev by Date: integration
  • Next by Date: Re: parasite points with Mesh
  • Previous by thread: Re: integration
  • Next by thread: Re: Taking sums across indices of a SparseArray efficiently