Package smile.math.matrix.fp32

Class SparseMatrix

java.lang.Object

smile.math.matrix.fp32.IMatrix

smile.math.matrix.fp32.SparseMatrix

All Implemented Interfaces:

Serializable, Iterable<SparseMatrix.Entry>

public class SparseMatrix
extends IMatrix
implements Iterable<SparseMatrix.Entry>

A sparse matrix is a matrix populated primarily with zeros. Conceptually, sparsity corresponds to systems which are loosely coupled. Huge sparse matrices often appear when solving partial differential equations.

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.

See Also:

• Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
class	SparseMatrix.Entry	Encapsulates an entry in a matrix for use in streaming.

Nested classes/interfaces inherited from class smile.math.matrix.fp32.IMatrix

IMatrix.Preconditioner

Constructor Summary

Constructors

Constructor	Description
SparseMatrix(float[][] A)	Constructor.
SparseMatrix(float[][] A, float tol)	Constructor.
SparseMatrix(int m, int n, float[] nonzeros, int[] rowIndex, int[] colIndex)	Constructor.

Method Summary

Modifier and Type	Method	Description
SparseMatrix	aat()	Returns A * A'.
SparseMatrix	ata()	Returns A' * A.
SparseMatrix	copy()	Returns a deep copy of matrix.
float[]	diag()	Returns the diagonal elements.
void	forEachNonZero(int beginColumn, int endColumn, FloatConsumer consumer)	For each loop on non-zero elements.
float	get(int index)	Returns the element at the storage index.
float	get(int i, int j)	Returns A[i,j].
static SparseMatrix	harwell(Path path)	Reads a sparse matrix from a Harwell-Boeing Exchange Format file.
Iterator<SparseMatrix.Entry>	iterator()	Returns the iterator of nonzero entries.
Iterator<SparseMatrix.Entry>	iterator(int beginColumn, int endColumn)	Returns the iterator of nonzero entries.
SparseMatrix	mm(SparseMatrix B)	Returns the matrix multiplication C = A * B.
void	mv(float[] work, int inputOffset, int outputOffset)	Matrix-vector multiplication A * x.
void	mv(Transpose trans, float alpha, float[] x, float beta, float[] y)	Matrix-vector multiplication.
int	ncol()	Returns the number of columns.
Stream<SparseMatrix.Entry>	nonzeros()	Returns the stream of the non-zero elements.
Stream<SparseMatrix.Entry>	nonzeros(int beginColumn, int endColumn)	Returns the stream of the non-zero elements in given column range.
int	nrow()	Returns the number of rows.
static SparseMatrix	rutherford(Path path)	Reads a sparse matrix from a Rutherford-Boeing Exchange Format file.
void	set(int index, float value)	Sets the element at the storage index.
long	size()	Returns the number of stored matrix elements.
static SparseMatrix	text(Path path)	Reads a sparse matrix from a text file.
SparseMatrix	transpose()	Returns the transpose of matrix.
void	tv(float[] work, int inputOffset, int outputOffset)	Matrix-vector multiplication A' * x.

Methods inherited from class smile.math.matrix.fp32.IMatrix

apply, colName, colNames, colNames, eigen, eigen, Jacobi, market, mv, mv, mv, rowName, rowNames, rowNames, set, solve, solve, square, toString, toString, toString, trace, tv, tv, tv, update

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Constructor Details

SparseMatrix

public SparseMatrix(int m,
 int n,
 float[] nonzeros,
 int[] rowIndex,
 int[] colIndex)

Constructor.

Parameters:

m - the number of rows in the matrix.

n - the number of columns in the matrix.

nonzeros - the array of nonzero values stored column by column.

rowIndex - the row indices of nonzero values.

colIndex - the index of the start of columns.

SparseMatrix

public SparseMatrix(float[][] A)

Constructor.

Parameters:

A - a dense matrix to converted into sparse matrix format.

SparseMatrix

public SparseMatrix(float[][] A,
 float tol)

Constructor.

Parameters:

A - a dense matrix to converted into sparse matrix format.

tol - the tolerance to regard a value as zero if |x| < tol.

Method Details

copy

public SparseMatrix copy()

Description copied from class: IMatrix

Returns a deep copy of matrix.

Overrides:

copy in class IMatrix

Returns:

a deep copy of matrix.

nrow

public int nrow()

Description copied from class: IMatrix

Returns the number of rows.

Specified by:

nrow in class IMatrix

Returns:

the number of rows.

ncol

public int ncol()

Description copied from class: IMatrix

Returns the number of columns.

Specified by:

ncol in class IMatrix

Returns:

the number of columns.

size

public long size()

Description copied from class: IMatrix

Returns the number of stored matrix elements. For conventional matrix, it is simply nrow * ncol. But it is usually much less for band, packed or sparse matrix.

Specified by:

size in class IMatrix

Returns:

the number of stored matrix elements.

nonzeros

public Stream<SparseMatrix.Entry> nonzeros()

Returns the stream of the non-zero elements.

Returns:

the stream of the non-zero elements

nonzeros

public Stream<SparseMatrix.Entry> nonzeros(int beginColumn,
 int endColumn)

Returns the stream of the non-zero elements in given column range.

Parameters:

beginColumn - the beginning column, inclusive.

endColumn - the end column, exclusive.

Returns:

the stream of non-zero elements.

iterator

public Iterator<SparseMatrix.Entry> iterator()

Returns the iterator of nonzero entries.

Specified by:

iterator in interface Iterable<SparseMatrix.Entry>

Returns:

the iterator of nonzero entries

iterator

public Iterator<SparseMatrix.Entry> iterator(int beginColumn,
 int endColumn)

Returns the iterator of nonzero entries.

Parameters:

beginColumn - the beginning column, inclusive.

endColumn - the end column, exclusive.

Returns:

the iterator of nonzero entries

forEachNonZero

public void forEachNonZero(int beginColumn,
 int endColumn,
 FloatConsumer consumer)

For each loop on non-zero elements. This will be a bit faster than iterator or stream by avoiding boxing. But it will be considerably less general.

Note that the consumer could be called on values that are either effectively or actually zero. The only guarantee is that no values that are known to be zero based on the structure of the matrix will be processed.

Parameters:

beginColumn - The beginning column, inclusive.

endColumn - The end column, exclusive.

consumer - The matrix element consumer.

get

public float get(int index)

Returns the element at the storage index.

Parameters:

index - the storage index.

Returns:

the element.

set

public void set(int index,
 float value)

Sets the element at the storage index.

Parameters:

index - the storage index.

value - the element.

get

public float get(int i,
 int j)

Description copied from class: IMatrix

Returns A[i,j].

Overrides:

get in class IMatrix

Parameters:

i - the row index.

j - the column index.

Returns:

the matrix cell value.

mv

public void mv(Transpose trans,
 float alpha,
 float[] x,
 float beta,
 float[] y)

Description copied from class: IMatrix

Matrix-vector multiplication.

     y = alpha * op(A) * x + beta * y
 

where op is the transpose operation.

Specified by:

mv in class IMatrix

Parameters:

trans - normal, transpose, or conjugate transpose operation on the matrix.

alpha - the scalar alpha.

x - the input vector.

beta - the scalar beta. When beta is supplied as zero, y need not be set on input.

y - the input and output vector.

mv

public void mv(float[] work,
 int inputOffset,
 int outputOffset)

Description copied from class: IMatrix

Matrix-vector multiplication A * x.

Specified by:

mv in class IMatrix

Parameters:

work - the workspace for both input and output vector.

inputOffset - the offset of input vector in workspace.

outputOffset - the offset of output vector in workspace.

tv

public void tv(float[] work,
 int inputOffset,
 int outputOffset)

Description copied from class: IMatrix

Matrix-vector multiplication A' * x.

Specified by:

tv in class IMatrix

Parameters:

work - the workspace for both input and output vector.

inputOffset - the offset of input vector in workspace.

outputOffset - the offset of output vector in workspace.

transpose

public SparseMatrix transpose()

Returns the transpose of matrix.

Returns:

the transpose of matrix.

mm

public SparseMatrix mm(SparseMatrix B)

Returns the matrix multiplication C = A * B.

Parameters:

B - the operand.

Returns:

the multiplication.

ata

public SparseMatrix ata()

Returns A' * A.

Returns:

A' * A

aat

public SparseMatrix aat()

Returns A * A'.

Returns:

A * A'

diag

public float[] diag()

Description copied from class: IMatrix

Returns the diagonal elements.

Overrides:

diag in class IMatrix

Returns:

the diagonal elements.

harwell

public static SparseMatrix harwell(Path path)
                            throws IOException

Reads a sparse matrix from a Harwell-Boeing Exchange Format file. For details, see http://people.sc.fsu.edu/~jburkardt/data/hb/hb.html.

Note that our implementation supports only real-valued matrix, and we ignore the optional supplementary data (e.g. right hand side vectors).

Parameters:

path - the input file path.

Returns:

the matrix.

Throws:

IOException - when fails to read the file.

rutherford

public static SparseMatrix rutherford(Path path)
                               throws IOException

Reads a sparse matrix from a Rutherford-Boeing Exchange Format file. The Rutherford Boeing format is an updated more flexible version of the Harwell Boeing format. For details, see http://people.sc.fsu.edu/~jburkardt/data/rb/rb.html. Especially, the supplementary data in the form of right-hand sides, estimates or solutions are treated as separate files.

Note that our implementation supports only real-valued matrix, and we ignore the optional supplementary data (e.g. right hand side vectors).

Parameters:

path - the input file path.

Returns:

the matrix.

Throws:

IOException - when fails to read the file.

text

public static SparseMatrix text(Path path)
                         throws IOException

Reads a sparse matrix from a text file. The first line contains three integers, which are the number of rows, the number of columns, and the number of nonzero entries in the matrix.

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.

Parameters:

path - the input file path.

Returns:

the matrix.

Throws:

IOException - when fails to read the file.