Class SparseMatrix

java.lang.Object
smile.tensor.SparseMatrix
All Implemented Interfaces:
Serializable, Iterable<SparseMatrix.Entry>, Matrix, Tensor
public class SparseMatrix extends Object implements Matrix, Iterable<SparseMatrix.Entry>, Serializable
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

    • copy

      public SparseMatrix copy()
      Description copied from interface: Matrix
      Returns a deep copy of matrix.
      Specified by:
      copy in interface Matrix
      Returns:
      a deep copy of matrix.

    • scalarType

      public ScalarType scalarType()
      Description copied from interface: Tensor
      Returns the element data type.
      Specified by:
      scalarType in interface Tensor
      Returns:
      the element data type.

    • nrow

      public int nrow()
      Description copied from interface: Matrix
      Returns the number of rows.
      Specified by:
      nrow in interface Matrix
      Returns:
      the number of rows.

    • ncol

      public int ncol()
      Description copied from interface: Matrix
      Returns the number of columns.
      Specified by:
      ncol in interface Matrix
      Returns:
      the number of columns.

    • length

      public long length()
      Description copied from interface: Tensor
      Returns the number of tensor elements. For tensors with packed storage (e.g., BandMatrix, SparseMatrix, SymmMatrix), it returns the number of non-zero elements.
      Specified by:
      length in interface Matrix
      Specified by:
      length in interface Tensor
      Returns:
      the number of tensor elements.

    • scale

      public SparseMatrix scale(double alpha)
      Description copied from interface: Matrix
      A *= alpha
      Specified by:
      scale in interface Matrix
      Parameters:
      alpha - the scaling factor.
      Returns:
      this matrix.

    • 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 interface: Matrix
      Returns A[i,j].
      Specified by:
      get in interface Matrix
      Parameters:
      i - the row index.
      j - the column index.
      Returns:
      the matrix element value.

    • set

      public void set(int i, int j, double x)
      Description copied from interface: Matrix
      Sets A[i,j] = x.
      Specified by:
      set in interface Matrix
      Parameters:
      i - the row index.
      j - the column index.
      x - the matrix element value.

    • add

      public void add(int i, int j, double x)
      Description copied from interface: Matrix
      Sets A[i,j] += x.
      Specified by:
      add in interface Matrix
      Parameters:
      i - the row index.
      j - the column index.
      x - the operand.

    • sub

      public void sub(int i, int j, double x)
      Description copied from interface: Matrix
      Sets A[i,j] -= x.
      Specified by:
      sub in interface Matrix
      Parameters:
      i - the row index.
      j - the column index.
      x - the operand.

    • mul

      public void mul(int i, int j, double x)
      Description copied from interface: Matrix
      Sets A[i,j] *= x.
      Specified by:
      mul in interface Matrix
      Parameters:
      i - the row index.
      j - the column index.
      x - the operand.

    • div

      public void div(int i, int j, double x)
      Description copied from interface: Matrix
      Sets A[i,j] /= x.
      Specified by:
      div in interface Matrix
      Parameters:
      i - the row index.
      j - the column index.
      x - the operand.

    • mv

      public void mv(Transpose trans, double alpha, Vector x, double beta, Vector y)
      Description copied from interface: Matrix
      Matrix-vector multiplication. 
          y = alpha * A * x + beta * y
      Specified by:
      mv in interface Matrix
      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(Vector work, int inputOffset, int outputOffset)
      Description copied from interface: Matrix
      Matrix-vector multiplication A * x.
      Specified by:
      mv in interface Matrix
      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(Vector work, int inputOffset, int outputOffset)
      Description copied from interface: Matrix
      Matrix-vector multiplication A' * x.
      Specified by:
      tv in interface Matrix
      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.
      Specified by:
      transpose in interface Matrix
      Returns:
      the transpose of matrix.

    • mm

      public SparseMatrix mm(SparseMatrix B)
      Matrix multiplication 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'

    • diagonal

      public Vector diagonal()
      Description copied from interface: Matrix
      Returns the diagonal elements.
      Specified by:
      diagonal in interface Matrix
      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.