How to interpret the FullForm of a SparseArray?

Question

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?

---

Update: In recent versions of Mathematica the LibraryLink documentation has a useful description of the internal SparseArray structure.

Answer 1

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.

Answer 2

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: