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
- References:
- Taking sums across indices of a SparseArray efficiently
- From: "D. Grady" <D.C.Grady@gmail.com>
- Taking sums across indices of a SparseArray efficiently