Class CSRSparseMatrix
- java.lang.Object
-
- dev.nm.algebra.linear.matrix.doubles.matrixtype.sparse.CSRSparseMatrix
-
- All Implemented Interfaces:
Matrix
,MatrixAccess
,MatrixRing
,MatrixTable
,Densifiable
,SparseMatrix
,SparseStructure
,AbelianGroup<Matrix>
,Monoid<Matrix>
,Ring<Matrix>
,Table
,DeepCopyable
public class CSRSparseMatrix extends 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 thevalues
.row_ptr
is the list ofvalues
indices where each row starts. For example: \[ \begin{bmatrix} 1 & 2 & 0 & 0\\ 0 & 3 & 9 & 0\\ 0 & 1 & 4 & 0 \end{bmatrix} \]
Note:value = [ 1 2 3 9 1 4 ] col_ind = [ 0 1 1 2 1 2 ] row_ptr = [ 0 2 4 6 ]
(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.
-
-
Nested Class Summary
-
Nested classes/interfaces inherited from interface dev.nm.algebra.linear.matrix.doubles.matrixtype.sparse.SparseMatrix
SparseMatrix.Entry, SparseMatrix.ValueArray
-
-
Constructor Summary
Constructors Constructor Description CSRSparseMatrix(int nRows, int nCols)
Constructs a sparse matrix in CSR format.CSRSparseMatrix(int nRows, int nCols, int[] rowIndices, int[] columnIndices, double[] values)
Constructs a sparse matrix in CSR format.CSRSparseMatrix(int nRows, int nCols, List<SparseMatrix.Entry> entries)
Constructs a sparse matrix in CSR format by a list of non-zero entries.CSRSparseMatrix(int nRows, int nCols, List<SparseMatrix.Entry> entryList, boolean areEntriesSorted)
Constructs a sparse matrix in CSR format by a list of non-zero entries.CSRSparseMatrix(Matrix A)
Constructs a sparse matrix from a matrix.CSRSparseMatrix(CSRSparseMatrix that)
Copy constructor.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description Matrix
add(Matrix that)
this + thatCSRSparseMatrix
deepCopy()
The implementation returns an instance created fromthis
by the copy constructor of the class, or justthis
if the instance itself is immutable.boolean
equals(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.List<SparseMatrix.Entry>
getEntryList()
Exports the non-zero values in the matrix as a list ofSparseMatrix.Entry
s.SparseVector
getRow(int i)
Get the specified row in the matrix as a vector.SparseMatrix.ValueArray
getValueArray()
Exports the non-zero values in the matrix as arrays of row/column indices and values.int
hashCode()
Matrix
minus(Matrix that)
this - thatMatrix
multiply(Matrix that)
this * thatVector
multiply(Vector v)
Right multiply this matrix, A, by a vector.int
nCols()
Gets the number of columns.int
nNonZeros()
Get the number of non-zero entries in the structure.int
nRows()
Gets 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.SparseMatrix
subMatrix(int rowFrom, int rowTo, int colFrom, int colTo)
Extracts a sub-matrix given the bounds of row and column indices (inclusive).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
.String
toString()
CSRSparseMatrix
ZERO()
Get a zero matrix that has the same dimension as this matrix.
-
-
-
Constructor Detail
-
CSRSparseMatrix
public CSRSparseMatrix(int nRows, int nCols)
Constructs a sparse matrix in CSR format.- Parameters:
nRows
- the number of rowsnCols
- the number of columns
-
CSRSparseMatrix
public CSRSparseMatrix(int nRows, int nCols, int[] rowIndices, int[] columnIndices, double[] values)
Constructs a sparse matrix in CSR format.- Parameters:
nRows
- the number of rowsnCols
- the number of columnsrowIndices
- the row indices of the non-zeros valuescolumnIndices
- the column indices of the non-zeros valuesvalues
- the non-zero values
-
CSRSparseMatrix
public CSRSparseMatrix(int nRows, int nCols, List<SparseMatrix.Entry> entries)
Constructs a sparse matrix in CSR format by a list of non-zero entries.- Parameters:
nRows
- the number of rowsnCols
- the number of columnsentries
- the list of entries
-
CSRSparseMatrix
public CSRSparseMatrix(int nRows, int nCols, List<SparseMatrix.Entry> entryList, boolean areEntriesSorted)
Constructs a sparse matrix in CSR format by a list of non-zero entries.- Parameters:
nRows
- the number of rowsnCols
- the number of columnsentryList
- the list of entriesareEntriesSorted
-true
if the list of entries are sorted in row-major order
-
CSRSparseMatrix
public CSRSparseMatrix(Matrix A)
Constructs a sparse matrix from a matrix.- Parameters:
A
- a matrix
-
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
Gets the number of rows. Rows count from 1.
-
nCols
public int nCols()
Description copied from interface:Table
Gets the number of columns. Columns count from 1.
-
getEntryList
public List<SparseMatrix.Entry> getEntryList()
Description copied from interface:SparseMatrix
Exports the non-zero values in the matrix as a list ofSparseMatrix.Entry
s. This is useful for converting between the different formats ofSparseMatrix.Entry
. 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.getEntryList());
- Specified by:
getEntryList
in interfaceSparseMatrix
- Returns:
- the sparse entries
-
getValueArray
public SparseMatrix.ValueArray getValueArray()
Description copied from interface:SparseMatrix
Exports the non-zero values in the matrix as arrays of row/column indices and values.- Specified by:
getValueArray
in interfaceSparseMatrix
- Returns:
- the arrays of indices and values
- See Also:
SparseMatrix.ValueArray
-
subMatrix
public SparseMatrix subMatrix(int rowFrom, int rowTo, int colFrom, int colTo)
Description copied from interface:SparseMatrix
Extracts a sub-matrix given the bounds of row and column indices (inclusive).- Specified by:
subMatrix
in interfaceSparseMatrix
- Parameters:
rowFrom
- the beginning row indexrowTo
- the ending row indexcolFrom
- the beginning column indexcolTo
- the ending column index- Returns:
- A[rowFrom:rowTo, colFrom:colTo]
-
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 interfaceMatrixAccess
- Parameters:
row
- the row indexcol
- the column indexvalue
- 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 interfaceMatrixAccess
- Parameters:
i
- the row indexj
- 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 interfaceMatrix
- 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 interfaceMatrix
- 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 interfaceAbelianGroup<Matrix>
- Specified by:
add
in interfaceMatrixRing
- Parameters:
that
- a matrix- Returns:
- the sum of
this
andthat
-
minus
public Matrix minus(Matrix that)
Description copied from interface:MatrixRing
this - that- Specified by:
minus
in interfaceAbelianGroup<Matrix>
- Specified by:
minus
in interfaceMatrixRing
- Parameters:
that
- a matrix- Returns:
- the difference between
this
andthat
-
multiply
public Matrix multiply(Matrix that)
Description copied from interface:MatrixRing
this * that- Specified by:
multiply
in interfaceMatrixRing
- Specified by:
multiply
in interfaceMonoid<Matrix>
- Parameters:
that
- a matrix- Returns:
- the product of
this
andthat
-
multiply
public Vector multiply(Vector v)
Description copied from interface:Matrix
Right multiply this matrix, A, by a vector.
-
scaled
public CSRSparseMatrix scaled(double c)
Description copied from interface:Matrix
Scale this matrix, A, by a constant.
-
opposite
public CSRSparseMatrix opposite()
Description copied from interface:MatrixRing
Get the opposite of this matrix.- Specified by:
opposite
in interfaceAbelianGroup<Matrix>
- Specified by:
opposite
in interfaceMatrixRing
- 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 interfaceMatrixRing
- 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 interfaceDensifiable
- 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 interfaceAbelianGroup<Matrix>
- Specified by:
ZERO
in interfaceMatrixRing
- 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 interfaceMatrixRing
- Specified by:
ONE
in interfaceMonoid<Matrix>
- Returns:
- an identity matrix
-
deepCopy
public CSRSparseMatrix deepCopy()
Description copied from interface:DeepCopyable
The implementation returns an instance created fromthis
by the copy constructor of the class, or justthis
if the instance itself is immutable.- Specified by:
deepCopy
in interfaceDeepCopyable
- Specified by:
deepCopy
in interfaceMatrix
- 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 interfaceSparseStructure
- Returns:
- the number of non-zero entries in the structure
-
-