Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

SparseArrays are atomic objects, but they do have a FullForm which reveals information about them.

What is the meaning of the various elements in the full form of a SparseArray? Did the structure change between Mathematica versions, and is it documented anywhere?

share|improve this question
    
It seems to be the same as InputForm which is mentioned: Whenever a sparse array is evaluated, it is automatically converted to an optimized standard form But it doesn't have much detalis –  ssch Jan 19 '13 at 21:34
2  
I can't tell much about the changes from version to version, but the "API" I use in many of my answers,e.g. here gives some idea. I give more details on the meaning of these parts here. –  Leonid Shifrin Jan 19 '13 at 21:48
    
Based on ElisionsDump`HeldSparseArrayData it looks like SparseArray[data_,dims_,def_,{___,elems_}], where dims is the dimensions and elems is number of non-default elements. I'm not sure about def and data. –  Szabolcs Jan 19 '13 at 22:50
    
def is the "background", or default, value. data seems always to be Automatic, and I don't know what it represents. –  Oleksandr R. Jan 20 '13 at 6:12
2  
"SparseArray-s are considered to be atomic objects for pattern matching " - this is not quite true (see my answer), and this is actually quite important, because SparseArray-s are fully represented by their FullForm, in the sense that, if you combine a SparseArray expression from pieces (like it is done in my answer below), you get a valid SparseArray object. To my mind, this is an important property. It does not hold for some other atomic objects (e.g. Graph-s), which some of us consider rather unfortunate. –  Leonid Shifrin Mar 28 at 12:15
show 4 more comments

2 Answers

up vote 7 down vote accepted

I have described the details here and here. The second post describes the version number of the sparse array implementation, which is still at version 1. So no big changes since it's introduction and V9.

If you like to read about sparse arrays I can recommend this from Tim Davis.

share|improve this answer
add comment

Reposting my answer from here (its relevant part about SparseArray)

The anatomy of sparse arrays

We start with a generally useful API for construction and deconstruction of SparseArray objects:

ClearAll[spart, getIC, getJR, getSparseData, getDefaultElement, makeSparseArray];
HoldPattern[spart[SparseArray[s___], p_]] := {s}[[p]];
getIC[s_SparseArray] := spart[s, 4][[2, 1]];
getJR[s_SparseArray] := Flatten@spart[s, 4][[2, 2]];
getSparseData[s_SparseArray] := spart[s, 4][[3]];
getDefaultElement[s_SparseArray] := spart[s, 3];
makeSparseArray[dims : {_, _}, jc : {__Integer}, ir : {__Integer}, 
     data_List, defElem_: 0] :=
 SparseArray @@ {Automatic, dims, defElem, {1, {jc, List /@ ir}, data}};

Some brief comments are in order. Here is a sample sparse array:

In[15]:= 
ToHeldExpression@ToString@FullForm[
   sp  = SparseArray[{{0,0,1,0,2},{3,0,0,0,4},{0,5,0,6,7}}]
]

Out[15]= 
    Hold[
      SparseArray[
        Automatic,
        {3,5}, (* Dimensions *)
        0,     (* Default element *)
        {
          1,
          {{0,2,4,7},{{3},{5},{1},{5},{2},{4},{5}}}, (* {ic, jr} *)
          {1,2,3,4,5,6,7} (* sparseData*)
        }
      ]
    ]

(I used ToString - ToHeldExpression cycle to convert List[...] etc in the FullForm back to {...} for the ease of reading). Here are the meanings of the parts:

  • {3,5} are obviously dimensions.
  • Next is 0, the default element.
  • Next is a nested list, which we can denote as {1,{ic,jr}, sparseData}. Here:

    • ic gives a total number of nonzero (non-default) elements as we add rows - so it is first 0, then 2 after first row, the second adds 2 more, and the last adds 3 more.
    • The next list, jr, gives positions of non-zero elements in all rows, so they are 3 and 5 for the first row, 1 and 5 for the second, and 2, 4 and 5 for the last one.

    There is no confusion as to where which row starts and ends here, since this can be determined by the ic list.

    • Finally, we have the sparseData, which is a list of the non-zero elements as read row by row from left to right (the ordering is the same as for the jr list).

Supplement:

(The following interpretation is a guess based on Silvia's observation.)

Suppose we have an array $A$ with dimension $N_1 \times N_2 \times \cdots \times N_n$,($n>1$): $\{A_1,A_2,\dots , A_k, \dots , A_{N_1}\}$, with the unspecified value (i.e. the background) being $b$.

And inside any $A_k$, there are $C_k$ numbers other than $b$: $\{\xi_{k,1},\xi_{k,2},\dots,\xi_{k,C_k}\}$, which located at positions $\{\rm{pos}_{k,1},\rm{pos}_{k,2},\dots,\rm{pos}_{k,C_k}\}$. So every $\rm{pos}_{k,\_}$ is a one-dimensional list with length $n-1$. (Except for the case of $A$ whose dimension is $1$ itself.)

Let $C_0=0$. Than the SparseArray expression of $A$ would be:

SparseArray syntax

share|improve this answer
    
any idea what the Automatic does? –  george2079 Mar 28 at 12:51
    
My guess is that it is needed to differentiate the long form (to which the short form auto-evaluates), from the short form itself - but I am not sure. –  Leonid Shifrin Mar 28 at 13:03
    
By "nonzero" (ic) you mean "nondefault"? Or does SparseArray always use 0 internally to denote the default? –  István Zachar Mar 28 at 13:13
1  
@george2079 Ok, that's a good point, and I did not account for this. The thing is, within each row, there is a freedom oh where to put the new elements, because the only requirement is that we have a list of positions, and that the ic has been modified correctly, so that we know how to split the list between rows. Do, we could have {{3}, {5}, {1}, {1}, {5}, {2}, {4}, {5}}}, {1, 2, 8, 3, 4, 5, 6, 7} (which is what we have), or e.g. {{1}, {3}, {5}, {1}, {5}, {2}, {4}, {5}}}, {8, 1, 2,3, 4, 5, 6, 7}, and this would've been equally valid. –  Leonid Shifrin Mar 28 at 17:17
1  
@george2079 So, apparently, the current implementation adds the newly set element to the end for the part of the lists which correspond to a given row where the element has been added - which is one possible choice, but not the only one. You asked why not at the start - well, it does not have to. All that matters is that the two lists are consistent with each other, and that we do have a list of positions - it is enough to reconstruct the original list correctly. –  Leonid Shifrin Mar 28 at 17:20
show 6 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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