Extreme Optimization >
User's Guide >
Vector and Matrix Library >
Sparse Vectors and Matrices >
Sparse Vectors
Extreme Optimization User's Guide
User's Guide
Up: Sparse Vectors and Matrices Next: Sparse Matrices Previous: Sparse Vectors and Matrices Contents
Sparse Vectors
The Extreme Optimization Numerical Libraries for .NET has three types that represent sparse vectors. The
SparseVector type is an abstract type that
serves as the base class for all types that implement sparse vectors. The SparseGeneralVector is the only type that has
a public constructor. Other sparse vector types are used internally to represent rows or columns of a sparse matrix,
or subvectors of a sparse vector.
Constructing sparse vectors
The SparseGeneralVector class has
four constructors. The first constructor takes one argument: the length of the vector. The second constructor takes
an additional parameter: a Double value between 0 and 1 that specifies the proportion
of nonzero values that is expected. The third constructor is similar to the second, but takes as its second parameter
an integer that specifies the exact capacity.
The example below constructs three sparse vectors, each with one million components. The second and third vectors
have an initial capacity of 100 nonzero values:
| C# | Copy Code |
|---|
SparseGeneralVector v1 = new SparseGeneralVector(1000000);
SparseGeneralVector v2 = new SparseGeneralVector(1000000, 1e-4);
SparseGeneralVector v3 = new SparseGeneralVector(1000000, 100); |
| Visual Basic | Copy Code |
|---|
Dim v1 As SparseGeneralVector = New SparseGeneralVector(1000000)
Dim v2 As SparseGeneralVector = New SparseGeneralVector(1000000, 1e-4)
Dim v3 As SparseGeneralVector = New SparseGeneralVector(1000000, 100) |
The fourth and final constructor takes three parameters. The first is once again the length. The second parameter
is an integer array containing the indexes of the nonzero components of the vector. The third parameter 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 component equals the sum of the all the values with that index.
The next example constructs a new sparse vector of length one million, with nonzeros at index 10k for k
in the range 0 to 5:
| C# | Copy Code |
|---|
int[] indexes = { 1, 10, 100, 1000, 10000 };
double[] values = { 1.0, 10.0, 100.0, 1000.0, 10000.0 };
SparseGeneralVector v4 = new SparseGeneralVector(1000000, indexes, values); |
| Visual Basic | Copy Code |
|---|
Dim indexes As Int() = { 1, 10, 100, 1000, 10000 }
Dim values As Double() = { 1.0, 10.0, 100.0, 1000.0, 10000.0 }
Dim v4 As SparseGeneralVector = New SparseGeneralVector(1000000, 100) |
Accessing Components
Components of sparse vectors can be accessed in the same way as for any other vector. If a component is set to a
nonzero value, the component is automatically added to the list of nonzero components. If the vector was at full
capacity, then the capacity is automatically extended.
It is possible to iterate over the nonzero components of a sparse vector efficiently. The NonzeroComponents property returns
a collection of IndexValuePair values that can
be used to iterate over the nonzero components. The IndexValuePair 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 NonzeroComponents property to list
the nonzero components of the vector v4:
| C# | Copy Code |
|---|
foreach(IndexValuePair pair in v4.NonzeroComponents)
Console.WriteLine("Component {0} = {1}", pair.Index, pair.Value); |
| Visual Basic | Copy Code |
|---|
For Each pair As IndexValuePair In v4.NonzeroComponents
Console.WriteLine("Component {0} = {1}", pair.Index, pair.Value)
Next |
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:
| C# | Copy Code |
|---|
Console.WriteLine("Norm(v4) = {0}", v4.Norm());
Console.WriteLine("Sum(v4) = {0}", v4.GetSum()); |
| Visual Basic | Copy Code |
|---|
Console.WriteLine("Norm(v4) = {0}", v4.Norm())
Console.WriteLine("Sum(v4) = {0}", v4.GetSum()) |
Note that some operations convert a sparse vector to a GeneralVector, causing memory to be allocated for all
components. Most importantly, static operations that return new vectors, including overloaded operators, usually
return a GeneralVector even if the result type
can be expected to be sparse. You can avoid this by cloning the sparse vector and calling the corresponding instance
method.
Up: Sparse Vectors and Matrices Next: Sparse Matrices Previous: Sparse Vectors and Matrices Contents
Copyright 2004-2008,
Extreme Optimization. All rights reserved.
Extreme Optimization, Complexity made simple, M#, and M
Sharp are trademarks of ExoAnalytics Inc.
Microsoft, Visual C#, Visual Basic, Visual Studio, Visual
Studio.NET, and the Visual Studio Logo are registered trademarks of Microsoft Corporation