Sparse Vectors

The SparseVectorT 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);

Dim v1 = Vector.CreateSparse(Of Double)(1000000)
Dim v2 = Vector.CreateSparse(Of Double)(1000000, 0.0001)
Dim v3 = Vector.CreateSparse(Of Double)(1000000, 100)

let v1 = Vector.CreateSparse<float>(1000000)
let v2 = Vector.CreateSparse<float>(1000000, 1e-4)
let v3 = Vector.CreateSparse<float>(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 10^k 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);

Dim indexes = {1, 10, 100, 1000, 10000}
Dim values = {1.0, 10.0, 100.0, 1000.0, 10000.0}
Dim v4 = Vector.CreateSparse(1000000, indexes, values)

let indexes = [| 1; 10; 100; 1000; 10000 |]
let values = [| 1.0; 10.0; 100.0; 1000.0; 10000.0 |]
let v4 = Vector.CreateSparse(1000000, indexes, values)

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 IndexValuePairT values that can be used to iterate over the nonzero elements. The IndexValuePairT 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);

For Each pair In v4.NonzeroElements
    Console.WriteLine("Element {0} = {1}", pair.Index, pair.Value)
Next

for pair in v4.NonzeroElements do
    printfn "Element %d = %f" pair.Index pair.Value

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();

Dim norm = v4.Norm()
Dim sum = v4.Sum()

let norm = v4.Norm()
let 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.