11
$\begingroup$

Suppose I have two large packed arrays a and b, that respectively contain the position of the elements of a square matrix (i.e. a has the explicit form {{1,2},{2,3},{3,4},...}) and the value for each matrix element (i.e. b has the explicit form {0.2938,0.091,-0.4984,...}).

Now, is there a way to build a sparse array from a and b without having unpacking in the internal process of creating the sparse array ?

Refining the question + example below: The usual SparseArray[a->b] command seems have some unpacking in the process although a and b are unaffected. Really, what I'm concerned about is : suppose you have memA=ByteCount[a] and memB=ByteCount[b].

In the process of constructing c=SparseArray[a->b] I do not want my kernel to suck up all my memory by unpacking a or b (or doing some other unpacking in the internal code), i.e. the kernel memory required during the process should not exceed something like memA+memB, which seems like a very natural requirement to me... In eldo's answer below, it seems there is no unpacking since the arrays considered are too small. Considering larger arrays will lead to the above mentioned problem.

Is there a simple solution (or not so simple) to this issue ?

*Specific example:

On["Packing"] 

a=Table[{i, i + 1}, {i, 1, 10000000}]; (* Position of the elements *)
b=Table[RandomReal[], {i, 1, 10000000}]; (* Value of the elements *)
c=SparseArray[{a -> b}]; (* Generating the sparse array *)
ByteCount[a]
ByteCount[b]
ByteCount[c]

80000168

80000168

160000952

Plus you get the following messages :

FromPackedArray::punpack: Unpacking array with dimensions {10000000,2} in call to Rule. >> FromPackedArray::punpack: Unpacking array with dimensions {10000000} in call to Rule. >> FromPackedArray::punpack1: Unpacking array with dimensions {10000000}.>>

So it seems there is some unpacking in the internal process. In this specific examples the kernel memory during the process goes up by 1 GB, although the final results takes only 160 MB...

$Version

8.0 for Mac OS X x86 (64-bit) (October 5, 2011)

$\endgroup$
9
  • $\begingroup$ Answered here: link $\endgroup$
    – eldo
    Jun 27, 2014 at 22:46
  • $\begingroup$ I looked at that answer, but I didn't understand how this could be applied to my problem. I guess what I'm asking here is : is there a simple command such as SparseArray[A->B] to generate the sparse array from A and B ? $\endgroup$ Jun 27, 2014 at 22:48
  • $\begingroup$ It looks like there is some internal unpacking going on, for large enough lists. It is possible to construct the pieces of the SparseArray without unpacking, but it looks like they are still unpacked internally. $\endgroup$ Jun 27, 2014 at 23:26
  • $\begingroup$ Your comment at On["Packing"] is incorrect. It just switches on unpacking warnings. It does not AFAIK influence packing itself. $\endgroup$ Jun 28, 2014 at 7:13
  • $\begingroup$ Right. I made the update. $\endgroup$ Jun 28, 2014 at 13:04

2 Answers 2

3
$\begingroup$

In version 10.1 under Windows I find that a subtle syntax difference is critical to this issue.

The form SparseArray[{a -> b}] causes unpacking while SparseArray[a -> b] does not. Further this affects the output of SparseArray itself, not only its memory consumption during creation.

On["Packing"]

a = {#, # + 1}\[Transpose] & @ Range @ 1*^6;
b = RandomReal[1, 1*^6];
c = SparseArray[a -> b];

Developer`PackedArrayQ /@ {a,b}

MaxMemoryUsed[]
ByteCount[c]
{True, True}

85279216

24000792

In a fresh session the exact same code as above adding only the brackets around a -> b

On["Packing"]

a = {#, # + 1}\[Transpose] & @ Range @ 1*^6;
b = RandomReal[1, 1*^6];
c = SparseArray[{a -> b}];    (* <-------- CRITICAL SYNTAX DIFFERENCE *)

Developer`PackedArrayQ /@ {a,b}

MaxMemoryUsed[]
ByteCount[c]

Developer`FromPackedArray::punpack: Unpacking array with dimensions {1000000,2} in call to Rule. >>

Developer`FromPackedArray::punpack: Unpacking array with dimensions {1000000} in call to Rule. >>

{True, True}

286566696

40000728

The two objects are functionally equivalent despite the size difference:

c1 = SparseArray[a -> b];
c2 = SparseArray[{a -> b}];

ByteCount /@ {c1, c2}

c1 === c2
{24000792, 40000728}

True

I surmise that specific optimizations exist in SparseArray for exactly your application, however the syntax is brittle and the optimization is not triggered for {a -> b}.

$\endgroup$
1
$\begingroup$
Needs["Developer`"];

a = {{1, 2}, {3, 4}, {99, 2}} // ToPackedArray;

b = {1.1, 1.2, 1.3} // ToPackedArray;

c = SparseArray[a -> b];

PackedArrayQ /@ {a, b, c}

{True, True, False}

Hence, a and b were NOT unpacked.

UPDATE

Needs["Developer`"];

a = Table[{i, i + 1}, {i, 1, 10000000}];
b = Table[RandomReal[], {i, 1, 10000000}];
c = SparseArray[{a -> b}];

ByteCount /@ {a, b, c}

{160000152, 80000144, 400000728}

PackedArrayQ /@ {a, b, c}

{True, True, False}

No Warnings.

$Version

"9.0 for Microsoft Windows (64-bit) (January 25, 2013)"

$\endgroup$
9
  • 4
    $\begingroup$ There is unpacking if you try this on larger arrays, of e.g. 100 elements. But to see it, you have to enable On["Packing"] before running the code. $\endgroup$ Jun 27, 2014 at 23:18
  • $\begingroup$ Exactly ! Is there a way to avoid this ? In the example given by eldo, the arrays are indeed too small to have the unpacking. $\endgroup$ Jun 28, 2014 at 1:08
  • $\begingroup$ @VanillaSpinIce Not that I know of (which doesn't mean there isn't). It seems that the unpacking is done in the internal code, which constructs the sparse array. I wrote some code which constructs the sparse array from pieces at lower level, but the unpacking was still there - thus I did not post it. $\endgroup$ Jun 28, 2014 at 2:00
  • $\begingroup$ @ Leonid Shifrin Ah, I see. It seems that being able to do such a thing would be such a big plus for using Mathematica for large sparse matrix diagonalization... meaning that you can increase the size of the matrix you are looking at by a factor of 4 or 8. I think this would be of great interest for many physicists that are interest in exact diagonalization of quantum systems. $\endgroup$ Jun 28, 2014 at 2:12
  • 1
    $\begingroup$ "Unpacking" here refers to temporary unpacking. In other words, the internal representation of a, b is not changed permanently. PackedArrayQ[a] will always give True. However, during the process of creating the SparseArray, an unpacked version of a,b is created in memory temporarily. These can take up a lot of memory, and the unpacking process can be very slow (in general, I don't know how big an issue it is in the specific case of creating a SparseArray). Before evaluating this test code, make sure you do On["Packing"] which will turn on warnings about unpacking events. $\endgroup$
    – Szabolcs
    Jun 28, 2014 at 14:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.