What are pattern sparse arrays and how do I use them?

Question

I found a few references to something called a "pattern sparse array" that does not contain any values, only positions. What is this data structure? How and when do I use it?

---

From the documentation of MSparseArray_getExplicitValues:

For a pattern sparse array where only positions are stored and there are no values, the result will point to a null (0) MTensor.

Some graph objects also contain a sparse array like this. The FullForm of e.g. SeedRandom[42]; RandomGraph[{5, 6}] contains

SparseArray[Automatic, {5, 5}, 0, {1, {{0, 1, 4, 7, 9, 12}, {{2}, {1}, {3}, {5}, {2}, {4}, {5}, {3}, {5}, {2}, {3}, {4}}}, Pattern}]

The ArrayRules of this array are

{{1, 2} -> _, {2, 1} -> _, {2, 3} -> _, {2, 5} -> _, {3, 2} -> _, {3, 
   4} -> _, {3, 5} -> _, {4, 3} -> _, {4, 5} -> _, {5, 2} -> _, {5, 
   3} -> _, {5, 4} -> _, {_, _} -> 0}

Finally, a regular sparse array has a method called PatternArray, which appears to create the equivalent sparse array with no values.

In[33]:= SparseArray[{0, 0, 1, 2, 0, 0, 3}] // InputForm
Out[33]//InputForm=
SparseArray[Automatic, {7}, 0, {1, {{0, 3}, {{3}, {4}, {7}}}, {1, 2, 3}}]

In[34]:= SparseArray[{0, 0, 1, 2, 0, 0, 3}]["PatternArray"] // InputForm
Out[34]//InputForm=
SparseArray[Automatic, {7}, 0, {1, {{0, 3}, {{3}, {4}, {7}}}, Pattern}]

Answer 1

Pattern sparse arrays are used, for example, in NDSolve to specify the structure of a Jacobian. This can save significant time while integrating a differential equation. In other words pattern sparse arrays are useful if one knows something about the structure of a sparse array but not (yet) about the values. There are some examples in the FEM Programming tutorial.

To extract a sparse array pattern one can use:

sa = SparseArray[{{1, 1} -> 1, {1, 2} -> 1,{2, 2} -> 2, {3, 3} -> 3, {1, 3} -> 4}];
spa = sa["PatternArray"];
spa["NonzeroValues"]
Pattern

And that's the reason for the documentation note you found. Since a sparse array can be a pattern array one needs to check that the value tensor actually has something in it.

Some algorithms like

SparseArray`ApproximateMinimumDegree[spa]
{3, 2, 1}

SparseArray`MinimumBandwidthOrdering[spa]
{{1, 1}, {{2, 1, 3}, {2, 1, 3}}}

can use a sparse pattern array. Or

FindShortestTour[AdjacencyGraph[Transpose[spa].spa]]
{3, {1, 3, 2, 1}}

In these cases the value of the sparse array is not relevant. So if you have a sparse array just use that if you need to construct a new one or have an operation that constructs a new one (like Dot) you can save the memory of the values and the time to compute the values if all you care about is the structure of the matrix