Package smile.math.matrix

Class SparseMatrix

java.lang.Object
smile.math.matrix.IMatrix
smile.math.matrix.SparseMatrix
All Implemented Interfaces:
Serializable, Cloneable, 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:

  • Constructor Details

    • SparseMatrix

      public SparseMatrix(int m, int n, double[] 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(double[][] A)
      Constructor.
      Parameters:
      A - a dense matrix to converted into sparse matrix format.

    • SparseMatrix

      public SparseMatrix(double[][] A, double 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

    • clone

      public SparseMatrix clone()
      Overrides:
      clone in class Object

    • 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(DoubleConsumer 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:
      consumer - The matrix element consumer.

    • forEachNonZero

      public void forEachNonZero(int beginColumn, int endColumn, DoubleConsumer 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 double get(int index)
      Returns the element at the storage index.
      Parameters:
      index - the storage index.
      Returns:
      the element.

    • set

      public void set(int index, double value)
      Sets the element at the storage index.
      Parameters:
      index - the storage index.
      value - the element.

    • get

      public double 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, double alpha, double[] x, double beta, double[] 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(double[] 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(double[] 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 double[] 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.