public class SparseMatrix extends java.lang.Object implements Matrix, MatrixMultiplication<SparseMatrix,SparseMatrix>, java.lang.Iterable<SparseMatrix.Entry>
Operations using standard dense matrix structures and algorithms are slow and consume large amounts of memory when applied to large sparse matrices. Indeed, some very large sparse matrices are infeasible to manipulate with the standard dense algorithms. Sparse data is by nature easily compressed, and this compression almost always results in significantly less computer data storage usage.
This class employs Harwell-Boeing column-compressed sparse matrix format. Nonzero values are stored in an array (top-to-bottom, then left-to-right-bottom). The row indices corresponding to the values are also stored. Besides, a list of pointers are indexes where each column starts. This format is efficient for arithmetic operations, column slicing, and matrix-vector products. One typically uses SparseDataset for construction of SparseMatrix.
For iteration through the elements of a matrix, this class provides
a functional API to iterate through the non-zero elements. This iteration
can be done by passing a lambda to be called on each non-zero element or
by processing a stream of objects representing each non-zero element.
The direct functional API is faster (and is about as fast as writing the
low-level loops against the internals of the matrix itself) while the
streaming interface is more flexible. Here are some benchmarks that were
produced using jmh (and allowing access to internal data structures):
| Modifier and Type | Class and Description |
|---|---|
class |
SparseMatrix.Entry
Encapsulates an entry in a matrix for use in streaming.
|
| Constructor and Description |
|---|
SparseMatrix(double[][] D)
Constructor.
|
SparseMatrix(double[][] D,
double tol)
Constructor.
|
SparseMatrix(int nrows,
int ncols,
double[] x,
int[] rowIndex,
int[] colIndex)
Constructor.
|
| Modifier and Type | Method and Description |
|---|---|
SparseMatrix |
aat()
Returns A * A'
|
SparseMatrix |
abmm(SparseMatrix B)
Returns the matrix multiplication C = A * B.
|
SparseMatrix |
abtmm(SparseMatrix B)
Returns the result of matrix multiplication A * B'.
|
SparseMatrix |
ata()
Returns A' * A
|
SparseMatrix |
atbmm(SparseMatrix B)
Returns the result of matrix multiplication A' * B.
|
SparseMatrix |
atbtmm(SparseMatrix B)
Returns the result of matrix multiplication A' * B'.
|
double[] |
atx(double[] x,
double[] y)
y = A' * x
|
double[] |
atxpy(double[] x,
double[] y)
y = A' * x + y
|
double[] |
atxpy(double[] x,
double[] y,
double b)
y = A' * x + b * y
|
double[] |
ax(double[] x,
double[] y)
y = A * x
|
double[] |
axpy(double[] x,
double[] y)
y = A * x + y
|
double[] |
axpy(double[] x,
double[] y,
double b)
y = A * x + b * y
|
double[] |
diag()
Returns the diagonal elements.
|
double |
get(int i,
int j)
Returns the entry value at row i and column j.
|
static SparseMatrix |
harwell(java.nio.file.Path path)
Reads a sparse matrix from a Harwell-Boeing Exchange Format file.
|
boolean |
isSymmetric()
Returns true if the matrix is symmetric.
|
java.util.Iterator<SparseMatrix.Entry> |
iterator()
Returns an iterator of nonzero entries.
|
java.util.Iterator<SparseMatrix.Entry> |
iterator(int beginColumn,
int endColumn)
Returns an iterator of nonzero entries.
|
int |
length()
Returns the number of nonzero values.
|
int |
ncols()
Returns the number of columns.
|
java.util.stream.Stream<SparseMatrix.Entry> |
nonzeros()
Provides a stream over all of the non-zero elements of a sparse matrix.
|
java.util.stream.Stream<SparseMatrix.Entry> |
nonzeros(int beginColumn,
int endColumn)
Provides a stream over all of the non-zero elements of range of columns of a sparse matrix.
|
int |
nrows()
Returns the number of rows.
|
static SparseMatrix |
rutherford(java.nio.file.Path path)
Reads a sparse matrix from a Rutherford-Boeing Exchange Format file.
|
void |
setSymmetric(boolean symmetric)
Sets if the matrix is symmetric.
|
static SparseMatrix |
text(java.nio.file.Path path)
Reads a sparse matrix from a text file.
|
SparseMatrix |
transpose()
Returns the matrix transpose.
|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, waitpublic SparseMatrix(int nrows,
int ncols,
double[] x,
int[] rowIndex,
int[] colIndex)
nrows - the number of rows in the matrix.ncols - the number of columns in the matrix.rowIndex - the row indices of nonzero values.colIndex - the index of the start of columns.x - the array of nonzero values stored column by column.public SparseMatrix(double[][] D)
D - a dense matrix to converted into sparse matrix format.public SparseMatrix(double[][] D,
double tol)
D - a dense matrix to converted into sparse matrix format.tol - the tolerance to regard a value as zero if |x| < tol.public java.util.Iterator<SparseMatrix.Entry> iterator()
iterator in interface java.lang.Iterable<SparseMatrix.Entry>public java.util.Iterator<SparseMatrix.Entry> iterator(int beginColumn, int endColumn)
beginColumn - The beginning column, inclusive.endColumn - The end column, exclusive.public boolean isSymmetric()
MatrixisSymmetric in interface Matrixpublic void setSymmetric(boolean symmetric)
MatrixsetSymmetric in interface Matrixpublic int nrows()
Matrixpublic int ncols()
Matrixpublic int length()
public java.util.stream.Stream<SparseMatrix.Entry> nonzeros()
public java.util.stream.Stream<SparseMatrix.Entry> nonzeros(int beginColumn, int endColumn)
beginColumn - The beginning column, inclusive.endColumn - The end column, exclusive.public double get(int i,
int j)
Matrixpublic double[] ax(double[] x,
double[] y)
Matrixpublic double[] axpy(double[] x,
double[] y)
Matrixpublic double[] axpy(double[] x,
double[] y,
double b)
Matrixpublic double[] atx(double[] x,
double[] y)
Matrixpublic double[] atxpy(double[] x,
double[] y)
Matrixpublic double[] atxpy(double[] x,
double[] y,
double b)
Matrixpublic SparseMatrix transpose()
Matrixpublic SparseMatrix abmm(SparseMatrix B)
abmm in interface MatrixMultiplication<SparseMatrix,SparseMatrix>public SparseMatrix abtmm(SparseMatrix B)
MatrixMultiplicationabtmm in interface MatrixMultiplication<SparseMatrix,SparseMatrix>public SparseMatrix atbmm(SparseMatrix B)
MatrixMultiplicationatbmm in interface MatrixMultiplication<SparseMatrix,SparseMatrix>public SparseMatrix atbtmm(SparseMatrix B)
MatrixMultiplicationatbtmm in interface MatrixMultiplication<SparseMatrix,SparseMatrix>public SparseMatrix ata()
Matrixpublic SparseMatrix aat()
Matrixpublic double[] diag()
Matrixpublic static SparseMatrix harwell(java.nio.file.Path path) throws java.io.IOException
path - the input file path.java.io.IOExceptionpublic static SparseMatrix rutherford(java.nio.file.Path path) throws java.io.IOException
path - the input file path.java.io.IOExceptionpublic static SparseMatrix text(java.nio.file.Path path) throws java.io.IOException
Following the first line, there are m + 1 integers that are the indices of columns, where m is the number of columns. Then there are n integers that are the row indices of nonzero entries, where n is the number of nonzero entries. Finally, there are n float numbers that are the values of nonzero entries.
path - the input file path.java.io.IOException