20
$\begingroup$

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}]
$\endgroup$
  • $\begingroup$ NDSolve`StructuralIncidenceArray -- I don't have M access right now, but can you create a Graph from a pattern sparse array? $\endgroup$ – Michael E2 Sep 29 '15 at 17:10
  • $\begingroup$ @MichaelE2 Yes, that is possible: AdjacencyGraph@SparseArray[{{1, 1}, {2, 3}} -> _, {3, 3}]. $\endgroup$ – Szabolcs Sep 29 '15 at 17:13
  • 1
    $\begingroup$ My initial guess is that it is one of the principal applications (and that it is the application in the NDSolve link). $\endgroup$ – Michael E2 Sep 29 '15 at 17:18
  • $\begingroup$ There is also an example use of "PatternArray" in the "Brusselator PDE" example of the LibraryLink tutorial Numerical Examples. $\endgroup$ – Michael E2 Sep 30 '15 at 10:36
15
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Is it a bug that this hangs? SparseArray[{}, {10, 10}]["PatternArray"]? $\endgroup$ – Szabolcs Dec 18 '15 at 8:16
  • $\begingroup$ @Szabolcs, filed. Thanks. $\endgroup$ – user21 Dec 18 '15 at 17:25
  • 1
    $\begingroup$ @Szabolcs, fixed in current sources. $\endgroup$ – user21 Dec 21 '15 at 18:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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