Extreme Optimization > User's Guide > Vector and Matrix Library > Sparse Vectors and Matrices > Sparse Matrices

Extreme Optimization User's Guide

User's Guide

Up: Sparse Vectors and Matrices Next: Solving Sparse Systems Previous: Sparse Vectors Contents

Sparse Matrices

How sparse matrices are stored

There are many representations for sparse matrices. Each has its advantages and disadvantages. Each has a set of applications for which it is particularly well suited.

The Extreme Optimization Numerical Libraries for .NET store sparse matrices in Compressed Sparse Column format. The components are stored in column-major order. Only the indexes and values of the nonzero components are stored. It consists of four arrays:

An array, values, containing the values of the nonzero matrix components.
An array, rows, containing the row indices of the elements of values.
An array, pointerB, of length ColumnCount containing the index into values and rows where the ith column begins.
An array, pointerE, of length ColumnCount containing the index into values and rows where the ith column ends.

Other representations (compressed sparse row format, coordinate format, sparse diagonal format) may be supported in the future. To allow for such a future extension, there are currently two sparse matrix types:

The SparseMatrix class is an abstract class that serves as the base class for all sparse matrix types. It defines methods that are common to all sparse matrices.

The SparseCompressedColumnMatrix class represents sparse matrices in Compressed Sparse Column format.

Constructing sparse matrices

Currently, only SparseCompressedColumnMatrix objects can be created. This class has four constructors.

The first constructor has two parameters: the number of rows and the number of columns in the matrix. This creates a sparse matrix with the specified number of rows and columns. All components are initially set to zero. The example below creates a sparse matrix with 3000 rows and 4000 columns:

C#	Copy Code
SparseMatrix m1 = new SparseCompressedColumnMatrix(3000, 4000);

Visual Basic	Copy Code
Dim m1 As SparseMatrix = New SparseCompressedColumnMatrix(3000, 4000)

The second constructor adds a third parameter: a real number between 0 and 1 that specifies the fill factor. This is the proportion of nonzero components compared to the total number of components in the matrix. The following creates a sparse matrix, and indicates that only 1 in 50 components are nonzero:

C#	Copy Code
SparseMatrix m2 = new SparseCompressedColumnMatrix(3000, 4000, 0.02);

Visual Basic	Copy Code
Dim m2 As SparseMatrix = New SparseCompressedColumnMatrix(3000, 4000, 0.02)

The third constructor is similar, but takes as its third parameter the expected number of nonzero components. This is useful in situations where this number is known. Note that this number is only the initial capacity. Should the number of nonzero components grow, then more space will be allocated. However, this is a relatively expensive operation, so it is generally preferable to overestimate this number rather than risk a reallocation. The code below creates a sparse matrix with room for exactly 7777 components:

C#	Copy Code
SparseMatrix m3 = new SparseCompressedColumnMatrix(3000, 4000, 7777);

Visual Basic	Copy Code
Dim m3 As SparseMatrix = New SparseCompressedColumnMatrix(3000, 4000, 7777)

The three constructors so far construct a sparse matrix with no actual components set. The next section outlines ways of adding the nonzero components.

The fourth constructor creates a sparse matrix and fills it with the specified components. It takes 5 parameters in all. The first two are once again the number of rows and columns. The third and fourth parameters are integer arrays that specify the row and column indexes of the nonzero components. The fifth parameter is a double array that specifies the corresponding values of the nonzero components.

All three arrays must have the same number of components. They do not need to be sorted in any particular order. They may also contain duplicate row and column indexes. If the same row and column occur multiple times, the value of the component is the sum of the corresponding values.

Building sparse matrices

All but one constructor in the previous section creates an empty sparse matrix. This section shows how to insert nonzero components into the matrix. The SparseMatrix class has a number of methods to simplify this process. All these methods start with Insert. The behavior complies with the Sparse BLAS specification.

The simplest method is InsertEntry, which inserts a single component into the matrix. It has three parameters. The first is the value of the component. The second and third parameters are the row and column. Any existing nonzero value is overwritten with the new value.

Up one level is the InsertEntries method. This method inserts multiple components at once. It also has three parameters. The first is an array containing the values of the components. The second and third parameters are integer arrays that specify the row and column where each value is to be inserted.,

Any existing nonzero value is overwritten with the new value. This also means that when a row column pair occurs multiple times, the component's value equals the last value that was encountered.

The InsertRow method creates entries in a single column. The first parameter is the row index. The second parameter is an array containing the values. The third parameter is an integer array containing the column indexes. There is also a InsertColumn method with a similar meaning and syntax.

Finally, the InsertClique method inserts a clique. A clique is a two-dimensional array of values, together with arrays of row and column indexes that specify where in the sparse matrix the entries will be inserted. The method has three parameters. The first is a Matrix that contains the values. The second and third parameters are integer arrays that contain row and column indexes.

Note: The names of the methods for building up sparse matrices are inherited from the sparse BLAS specification. The word "Insert" refers to the fact that nonzero components are inserted where previously there was a zero. All these methods leave the dimensions of the matrix unchanged.

Importing sparse matrices

Several common formats exist to exchange sparse matrices between applications. The Matrix Market format was inspired by the Matrix Market, an online repository of sparse test matrices and problems. You can import Matrix Market files into sparse matrix objects using the MatrixMarketReader class. This class has one static method, ReadMatrix, which has three overloads. Each of these takes one parameter. The first takes a string that is the path to the file name containing the data. The second takes a TextReader, and the third takes a Stream.

Accessing Sparse Matrix Components

The mechanisms for accessing components available to dense and structured matrices are also available for sparse matrices. Note, however, that accessing individual components is relatively slow, and should be avoided, if at all possible.

The most efficient way to access a SparseCompressedColumnMatrix's components is column by column. The GetColumn method returns a SparseVector that can access the components of the matrix efficiently.

It is possible to iterate over the nonzero components of a sparse matrix efficiently. The NonzeroComponents property returns a collection of RowColumnValueTriplet values that can be used to iterate over the nonzero components. The RowColumnValueTriplet structure has three read-only fields: Row, Column, and Value that contain the row and column indexes, and the value of each successive nonzero, respectively.

The code below uses the NonzeroComponents property to list the nonzero components of the matrix m3:

C#	Copy Code
foreach(RowColumnValueTriplet triplet in m3.NonzeroComponents) Console.WriteLine("Component ({0},{1}) = {2}", triplet.Row, triplet.Column triplet.Value);

Visual Basic	Copy Code
For Each triplet As RowColumnValueTriplet In m3.NonzeroComponents Console.WriteLine("Component ({0},{1}) = {2}", _ triplet.Row, triplet.Column triplet.Value) Next

There is also a GetNonzeroComponents method that returns the nonzero components in arrays. The method returns a Double array containing the values of the nonzero components. The method takes two out parameters. Both are integer arrays that, on return, contain the corresponding row and column indexes of the nonzero components.

Operations On Sparse Matrices

All operations that are available for dense and structured matrices are also available for sparse matrices. However, these operations may not always be efficient, and may even destroy sparsity and the advantages that come with it. Worse still, inappropriate use of sparse matrices may make code using sparse matrices perform orders of magnitude slower than their equivalent dense counterparts.

The key to working with sparse matrices is realizing that operations on individual components are very expensive. Finding the value of a component usually entails some form of lookup.

Operations on individual components

Even though operations on individual components of a sparse matrix are discouraged, they may at times be necessary. To avoid looking up the storage location of the component twice, a number of methods have been defined that operate directly on a component:

Method	Description
AddAt	Adds a value to a component.
SubtractAt	Subtracts a value from a component.
MultiplyAt	Multiplies a component by a value.
DivideAt	Divides a component by a value.

Table 1. Operations on individual matrix components.

Matrix arithmetic

The most important question regarding sparse matrix arithmetic is whether the return value is sparse or dense. Componentwise operations, such as addition, subtraction, componentwise multiplication and division, maintain sparsity. Multiplication of two sparse matrices returns a sparse matrix. All other operations return a dense matrix.

The solution of a system of equations is always dense, even if both the matrix and the right-hand side are sparse.

Other operations such as the computation of eigenvalues and singular values currently use a dense algorithm.