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: [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


  • Prev by Date: Re: Re: ListCurvePathPlot
  • Next by Date: Re: Re: Simplifying and Rearranging Expressions
  • Previous by thread: Re: Taking sums across indices of a SparseArray efficiently
  • Next by thread: Re: Re: Taking sums across indices of a