Sparse Vectors

Sparse vectors are represented by the SparseVector<T> class. Some special sparse vectors, like the rows and columns of a sparse matrix, are represented by internal types.

Constructing sparse vectors

The SparseVector<T> class has no public constructors. Instead, use an overload of the CreateSparse method to construct a new sparse vector. This method has four overloads. The first overload takes one argument: the length of the vector. The second overload takes an additional argument: a Double value between 0 and 1 that specifies the proportion of nonzero values that is expected. The third overload is similar to the second, but takes as its second argument an integer that specifies the capacity. All three overloads need the element type to be specified as a generic type argument.

The example below constructs three sparse vectors, each with one million elements. The second and third vectors have an initial capacity of 100 nonzero values:

var v1 = Vector.CreateSparse<double>(1000000);
var v2 = Vector.CreateSparse<double>(1000000, 1e-4);
var v3 = Vector.CreateSparse<double>(1000000, 100);

The fourth and final overload takes three arguments. The first is once again the length. The second argument is an integer array containing the indexes of the nonzero elements of the vector. The third argument is a Double array containing the corresponding values. The lengths of the arrays must be equal, and all indexes must be within the proper range. If the same index occurs multiple times, then the corresponding element equals the sum of the all the values with that index.

The next example constructs a new sparse vector of length one million, with non-zeros at index 10k for k in the range 0 to 5:

int[] indexes = { 1, 10, 100, 1000, 10000 };
double[] values = { 1.0, 10.0, 100.0, 1000.0, 10000.0 };
var v4 = Vector.CreateSparse(1000000, indexes, values);

Accessing Elements

Elements of sparse vectors can be accessed in the same way as for any other vector. If an element is set to a nonzero value, the element is automatically added to the list of nonzero elements. If the vector was at full capacity, then the capacity is automatically extended.

It is possible to iterate over the nonzero elements of a sparse vector efficiently. The NonzeroElements property returns a sequence of IndexValuePair<T> values that can be used to iterate over the nonzero elements. The IndexValuePair<T> structure has two read-only fields: Index and Value that contain the index and the value of each successive nonzero.

The code below uses the NonzeroElements property to list the nonzero elements of the vector v4:

foreach (var pair in v4.NonzeroElements)
    Console.WriteLine("Element {0} = {1}", pair.Index, pair.Value);

Other properties and methods

All properties and methods of vectors are also available for sparse vectors. Nearly all of these methods have optimized sparse implementations. This includes norms, most arithmetic operations including addition, subtraction, scaling and matrix products. For example:

var norm = v4.Norm();
var sum = v4.Sum();

Note that some operations on sparse vectors result in a dense vector, causing memory to be allocated for all elements. For example, the result of adding a scalar to a sparse vector is dense.