com.numericalmethod.suanshu.matrix.doubles.matrixtype.sparse
Class CSRSparseMatrix

java.lang.Object
  com.numericalmethod.suanshu.matrix.doubles.matrixtype.sparse.CSRSparseMatrix

All Implemented Interfaces:

Table, DeepCopyable, AbelianGroup<Matrix>, Monoid<Matrix>, Ring<Matrix>, Matrix, MatrixAccess, MatrixRing, MatrixTable, Densifiable, SparseMatrix, SparseStructure

public class CSRSparseMatrix
extends java.lang.Object
implements SparseMatrix

The Compressed Sparse Row (CSR) format for sparse matrix has this representation: (value, col_ind, row_ptr). Three arrays are used to represent a sparse matrix: value stores all the non-zero entries of the matrix from left to right, top to bottom. col_ind is the column indices corresponding to the values. row_ptr is the list of values indices where each row starts. For example: \[ \begin{bmatrix} 1 & 2 & 0 & 0\\ 0 & 3 & 9 & 0\\ 0 & 1 & 4 & 0 \end{bmatrix} \]

 value   = [ 1 2 3 9 1 4 ]
 col_ind = [ 0 1 1 2 1 2 ]
 row_ptr = [ 0 2 4 6 ]
 

Note: (row_ptr[i] - row_ptr[i - 1]) is the number of non-zero entries in row i.

This format is very inefficient for incremental construction or changes using set(int, int, double), but efficient for matrix computation.

See Also:

Wikipedia: Compressed sparse row (CSR or CRS)

Constructor Summary

CSRSparseMatrix(CSRSparseMatrix that)
Copy constructor.

CSRSparseMatrix(int nRows, int nCols)
Construct a sparse matrix in CSR format.

CSRSparseMatrix(int nRows, int nCols, int[] rowIndices, int[] columnIndices, double[] value)
Construct a sparse matrix in CSR format.

CSRSparseMatrix(int nRows, int nCols, java.util.List<SparseEntry> entries)
Construct a sparse matrix in CSR format by a list of non-zero entries.

Method Summary

Matrix	add(Matrix that) this + that
CSRSparseMatrix	deepCopy() The implementation returns an instance created from this by the copy constructor of the class, or just this if the instance itself is immutable.
boolean	equals(java.lang.Object obj)
double	get(int i, int j) Get the matrix entry at [i,j].
SparseVector	getColumn(int j) Get the specified column in the matrix as a vector.
java.util.List<SparseEntry>	getEntrytList() Export the non-zero values in the matrix as a list of SparseEntrys.
SparseVector	getRow(int i) Get the specified row in the matrix as a vector.
int	hashCode()
Matrix	minus(Matrix that) this - that
Matrix	multiply(Matrix that) this * that
Vector	multiply(Vector v) Right multiply this matrix, A, by a vector.
int	nCols() Get the number of columns.
int	nNonZeros() Get the number of non-zero entries in the structure.
int	nRows() Get the number of rows.
CSRSparseMatrix	ONE() Get an identity matrix that has the same dimension as this matrix.
CSRSparseMatrix	opposite() Get the opposite of this matrix.
CSRSparseMatrix	scaled(double c) Scale this matrix, A, by a constant.
void	set(int row, int col, double value) Set the matrix entry at [i,j] to a value.
CSRSparseMatrix	t() Get the transpose of this matrix.
DenseMatrix	toDense() Densify a matrix, i.e., convert a matrix implementation to the standard dense matrix, DenseMatrix.
java.lang.String	toString()
CSRSparseMatrix	ZERO() Get a zero matrix that has the same dimension as this matrix.

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Constructor Detail

CSRSparseMatrix

public CSRSparseMatrix(int nRows,
                       int nCols)

Construct a sparse matrix in CSR format.

Parameters:

nRows - the number of rows

nCols - the number of columns

CSRSparseMatrix

public CSRSparseMatrix(int nRows,
                       int nCols,
                       int[] rowIndices,
                       int[] columnIndices,
                       double[] value)

Construct a sparse matrix in CSR format.

Parameters:

nRows - the number of rows

nCols - the number of columns

rowIndices - the row indices of the non-zeros values

columnIndices - the column indices of the non-zeros values

value - the non-zero values

CSRSparseMatrix

public CSRSparseMatrix(int nRows,
                       int nCols,
                       java.util.List<SparseEntry> entries)

Construct a sparse matrix in CSR format by a list of non-zero entries.

Parameters:

nRows - the number of rows

nCols - the number of columns

entries - the list of entries

CSRSparseMatrix

public CSRSparseMatrix(CSRSparseMatrix that)

Copy constructor.

Parameters:

that - the matrix to be copied

Method Detail

nRows

public int nRows()

Description copied from interface: Table

Get the number of rows. Rows count from 1.

Specified by:

nRows in interface Table

Returns:

the number of rows

nCols

public int nCols()

Description copied from interface: Table

Get the number of columns. Columns count from 1.

Specified by:

nCols in interface Table

Returns:

the number of columns

getEntrytList

public java.util.List<SparseEntry> getEntrytList()

Description copied from interface: SparseMatrix

Export the non-zero values in the matrix as a list of SparseEntrys. This is useful for converting between the different formats of SparseMatrix. For example,

 // construct matrix using DOK
 DOKSparseMatrix dok = new DOKSparseMatrix(5, 5);
 // ... insert some values to DOK matrix
 // convert to CSR matrix for efficient matrix operations
 CSRSparseMatrix csr = new CSRSparseMatrix(5, 5, dok.getEntrytList());
 

Specified by:

getEntrytList in interface SparseMatrix

Returns:

the sparse entries

set

public void set(int row,
                int col,
                double value)

Description copied from interface: MatrixAccess

Set the matrix entry at [i,j] to a value. This is the only method that may change a matrix.

Specified by:

set in interface MatrixAccess

Parameters:

row - the row index

col - the column index

value - the value to set A[i,j] to

get

public double get(int i,
                  int j)

Description copied from interface: MatrixAccess

Get the matrix entry at [i,j].

Specified by:

get in interface MatrixAccess

Parameters:

i - the row index

j - the column index

Returns:

A[i,j]

getRow

public SparseVector getRow(int i)
                    throws MatrixAccessException

Description copied from interface: Matrix

Get the specified row in the matrix as a vector.

Specified by:

getRow in interface Matrix

Parameters:

i - the row index

Returns:

the vector A[i, ]

Throws:

MatrixAccessException - when i < 1, or when i > the number of rows

getColumn

public SparseVector getColumn(int j)
                       throws MatrixAccessException

Description copied from interface: Matrix

Get the specified column in the matrix as a vector.

Specified by:

getColumn in interface Matrix

Parameters:

j - the column index

Returns:

a vector A[, j]

Throws:

MatrixAccessException - when j < 1, or when j > the number of columns

add

public Matrix add(Matrix that)

Description copied from interface: MatrixRing

this + that

Specified by:

add in interface AbelianGroup<Matrix>

Specified by:

add in interface MatrixRing

Parameters:

that - a matrix

Returns:

the sum of this and that

minus

public Matrix minus(Matrix that)

Description copied from interface: MatrixRing

this - that

Specified by:

minus in interface AbelianGroup<Matrix>

Specified by:

minus in interface MatrixRing

Parameters:

that - a matrix

Returns:

the difference between this and that

multiply

public Matrix multiply(Matrix that)

Description copied from interface: MatrixRing

this * that

Specified by:

multiply in interface Monoid<Matrix>

Specified by:

multiply in interface MatrixRing

Parameters:

that - a matrix

Returns:

the product ofthis and that

multiply

public Vector multiply(Vector v)

Description copied from interface: Matrix

Right multiply this matrix, A, by a vector.

Specified by:

multiply in interface Matrix

Parameters:

v - a vector

Returns:

Av, a vector

scaled

public CSRSparseMatrix scaled(double c)

Description copied from interface: Matrix

Scale this matrix, A, by a constant.

Specified by:

scaled in interface Matrix

Parameters:

c - a double

Returns:

cA

opposite

public CSRSparseMatrix opposite()

Description copied from interface: MatrixRing

Get the opposite of this matrix.

Specified by:

opposite in interface AbelianGroup<Matrix>

Specified by:

opposite in interface MatrixRing

Returns:

-this

See Also:

Wikipedia: Additive inverse

t

public CSRSparseMatrix t()

Description copied from interface: MatrixRing

Get the transpose of this matrix. This is the involution on the matrix ring.

Specified by:

t in interface MatrixRing

Returns:

the transpose of this matrix

toDense

public DenseMatrix toDense()

Description copied from interface: Densifiable

Densify a matrix, i.e., convert a matrix implementation to the standard dense matrix, DenseMatrix.

Specified by:

toDense in interface Densifiable

Returns:

a matrix representation in DenseMatrix

ZERO

public CSRSparseMatrix ZERO()

Description copied from interface: MatrixRing

Get a zero matrix that has the same dimension as this matrix.

Specified by:

ZERO in interface AbelianGroup<Matrix>

Specified by:

ZERO in interface MatrixRing

Returns:

the 0 matrix

ONE

public CSRSparseMatrix ONE()

Description copied from interface: MatrixRing

Get an identity matrix that has the same dimension as this matrix. For a non-square matrix, it zeros out the rows (columns) with index > nCols (nRows).

Specified by:

ONE in interface Monoid<Matrix>

Specified by:

ONE in interface MatrixRing

Returns:

an identity matrix

deepCopy

public CSRSparseMatrix deepCopy()

Description copied from interface: DeepCopyable

The implementation returns an instance created from this by the copy constructor of the class, or just this if the instance itself is immutable.

Specified by:

deepCopy in interface DeepCopyable

Specified by:

deepCopy in interface Matrix

Returns:

an independent (deep) copy of the instance

nNonZeros

public int nNonZeros()

Description copied from interface: SparseStructure

Get the number of non-zero entries in the structure.

Specified by:

nNonZeros in interface SparseStructure

Returns:

the number of non-zero entries in the structure

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

equals

public boolean equals(java.lang.Object obj)

Overrides:

equals in class java.lang.Object

hashCode

public int hashCode()

Overrides:

hashCode in class java.lang.Object