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>

```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