What are SparseArray Properties? How and when should they be used?

Question

A strange undocumented form of SparseArray is increasingly used in answers on this site:

SparseArray[(* data *)]["NonzeroPositions"]

What is this, and why would anyone want to use this? Are there any other commands like it?

Answer 1

Introduction

This post is long overdue as I have been repeatedly asked to explain code of mine containing these things. As I see increased use of this construct by others perhaps it is past due also.

SparseArray objects can behave as functions accepting certain arguments to return internal data or efficiently return data in certain forms. These are known as Properties or Methods. They are not the only objects to have these; see for example How to splice together several instances of InterpolatingFunction? for Methods of InterpolatingFunction.

As undocumented functionality these Properties are more likely to be incompatibly changed than documented functions and they could be removed entirely in future versions. However they appear to have been stable (and extended) since the introduction of SparseArray itself so I feel this is still unlikely.

SparseArray is highly optimized therefore converting a tensor to a SparseArray and then using one of these Properties is often competitively fast, in many cases bettering seemingly more direct methods. Before Pick was optimized for packed arrays in version 8 SparseArray was often the fasted method available outside of compilation therefore as a long-time version 7 user I made (and make) frequent use of these, most often "AdjacencyLists" or "NonzeroPositions". Many examples can be found with these searches: AdjacencyLists, NonzeroPositions.

Documentation

The primary Properties themselves may be listed by using "Properties" or (I believe) exhaustively with "Methods"; in Mathematica 7:

SparseArray[{1}]["Methods"]

{"AdjacencyLists",   "Background",    "MethodInformation", "Methods", 
 "NonzeroPositions", "NonzeroValues", "PatternArray",      "Properties"}

And in Mathematica 10.1:

SparseArray[{1}]["Methods"]

{"AdjacencyLists", "Background",        "ColumnIndices", "Density",
 "MatrixColumns",  "MethodInformation", "Methods",       "NonzeroPositions",
 "NonzeroValues",  "PatternArray",      "Properties",    "RowPointers"}

There is limited internal documentation for these Properties in the form of hidden usage messages. As shown below the non-string form may be used but in my opinion it is safer to use Strings.

sa = SparseArray[{1}];
sa["MethodInformation"@#] & ~Scan~ sa["Methods"]

SparseArray[data]@AdjacencyLists gives the adjacency lists.

SparseArray[data]@Background gives the background value.

SparseArray[data]@ColumnIndices gives the column indices from the compressed sparse row data

SparseArray[data]@Density fraction of all elements that are nonzero.

SparseArray[data]@MatrixColumns gives the column indices for each row of a matrix

SparseArray[data]@MethodInformation[method] gives information about a particular method.

SparseArray[data]@Methods[pat] gives the list of methods matching the string pattern pat.

SparseArray[data]@NonzeroPositions gives the positions at which the nonzero (different from background) elements occur.

SparseArray[data]@NonzeroValues gives the values which occur at the nonzero positions.

SparseArray[data]@PatternArray gives the structural pattern template SparseArray.

SparseArray[data]@Properties gives the list of possible properties.

SparseArray[data]@RowPointers gives the row pointers array from the compressed sparse row data

Now in my own words:

NonzeroPositions

This Property returns the position of every non-background element in the sparse array. The default background element is zero:

a = {{1, 0, 2}, {0, 0, 1}, {2, 0, 1}};

sa0 = SparseArray[a];
sa0["NonzeroPositions"]

{{1, 1}, {1, 3}, {2, 3}, {3, 1}, {3, 3}}

A different background may be specified:

sa1 = SparseArray[a, Automatic, 1];
sa1["NonzeroPositions"]

{{1, 2}, {1, 3}, {2, 1}, {2, 2}, {3, 1}, {3, 2}}

Background

This is simply the background element of the array, zero when unspecified or as specified during the construction the SparseArray;

sa0["Background"]
sa1["Background"]

0

1

NonzeroValues

These are the non-background values corresponding to the positions returned by "NonzeroPositions" returned as a flat list:

sa0["NonzeroValues"]
sa1["NonzeroValues"]

{1, 2, 1, 2, 1}

{0, 2, 0, 0, 2, 0}

a ~Extract~ sa0["NonzeroPositions"]
a ~Extract~ sa1["NonzeroPositions"]

{1, 2, 1, 2, 1}

{0, 2, 0, 0, 2, 0}

AdjacencyLists

This is like "NonzeroPositions" given for every row in the array, except that single indexes are given as raw integers rater than in a list.

sa0["AdjacencyLists"]

{{1, 3}, {3}, {1, 3}}

Unlike "NonzeroPositions" the List depth of the returned expression varies with tensor rank:

SparseArray[{1, 0, 2, 3, 0}]["AdjacencyLists"]

Array[Plus, {2, 3, 4}] ~Mod~ 3;
SparseArray[%]["AdjacencyLists"]

{1, 3, 4}

{{{1, 2}, {1, 3}, {2, 1}, {2, 2}, {2, 4}, {3, 1}, {3, 3}, {3, 4}},
 {{1, 1}, {1, 2}, {1, 4}, {2, 1}, {2, 3}, {2, 4}, {3, 2}, {3, 3}}}

PatternArray

This returns a modified SparseArray object that represents an expression in which only the background elements remain and all others are replaced with _ (Blank[]). Normal may be used to convert it to a standard List tensor.

sa0["PatternArray"] // Normal

sa1["PatternArray"] // Normal

{{_, 0, _}, {0, 0, _}, {_, 0, _}}

{{1, _, _}, {_, _, 1}, {_, _, 1}}

Density

The fraction of all non-background elements in the sparse array as a Real number:

Count[a, Except[0], {2}] / Length@Flatten@a // N

sa0["Density"]

0.555556

0.555556

Count[a, Except[1], {2}] / Length@Flatten@a // N

sa1["Density"]

0.666667

0.666667

MatrixColumns

This appears to be identical to AdjacencyLists for a two dimensional sparse array and inapplicable otherwise, returning unevaluated. Not listed in the shorter "Properties" list this Method is perhaps unfinished or deprecated.

ColumnIndices and RowPointers

These newer Properties allow one to extract two internal structures of a SparseArray object without resorting to destructuring methods. Observe the alignment:

sa1 // InputForm

sa1 /@ {"RowPointers", "ColumnIndices"}

{{0, 2, 4, 6}, {{2}, {3}, {1}, {2}, {1}, {2}}}

SparseArray[Automatic, {3, 3}, 1, 
 {1, {{0, 2, 4, 6}, {{2}, {3}, {1}, {2}, {1}, {2}}},
   {0, 2, 0, 0, 2, 0}}]

These internal structures are fairly complex and are the subject of another Q&A:

• How to interpret the FullForm of a SparseArray?

Leonid Shifrin summarizes them as:

• (RowPointers) gives a total number of nonzero (non-default) elements as we add rows

• (ColumnIndices) gives positions of non-zero elements in all rows

kguler makes use of both in answer to Faster way to extract partial data from AdjacencyMatrix.

Application

• As briefly noted in the introduction SparseArray may be chosen for performance benefits.

• In some cases is one of the most clean ways to write a particular operation.

• When a SparseArray is returned by a System function it can be far superior to work with its Properties than to convert it to a Normal array and (re)compute them externally.

(This section will be extended with multiple examples when I have sufficient time to do them rigorously.)

---

Related:

• How to interpret the FullForm of a SparseArray?
• SparseArray row operations
• Leonid's SparseArray destructuring tools

Answer 2

In addition, there is TreatRepeatedEntries which allows for additive assembly as used in How to speed up this SparseArray construction in an answer provided Henrik Schumacher.

The core code, please refer to the Q&A of the above link for the full context.

 MySparseArray[R_Rule, dims_?VectorQ, fun_: Total, background_: 0] :=
 With[{spopt = SystemOptions["SparseArrayOptions"]},
  Internal`WithLocalSettings[
   SetSystemOptions[
    "SparseArrayOptions" -> {"TreatRepeatedEntries" -> fun}],
   SparseArray[R, dims, background],
   SetSystemOptions[spopt]]
  ]