Class SparseUtils

java.lang.Object
org.flag4j.linalg.ops.sparse.SparseUtils
public final class SparseUtils extends Object

Contains common utility functions for working with sparse matrices.

All methods in this class which accept non-zero data and non-zero indices, they are assumed to be sorted lexicographically. Similarly, all ops which store results in user provided destination arrays will also produce in lexicographically sorted arrays.

  • Constructor Details

    • SparseUtils

      public SparseUtils()

  • Method Details

    • cooFlattenIndices

      public static int[][] cooFlattenIndices(Shape shape, int[][] indices)
      Flattens the non-zero indices of a sparse COO tensor. This reduced the rank of this tensor to rank 1.
      Parameters:
      indices - Shape of the sparse COO tensor.
      Shape - Shape of the sparse COO tensor.
      Returns:
      The flattened indices of the sparse COO tensor.
      See Also:

    • cooFlattenIndices

      public static int[][] cooFlattenIndices(Shape shape, int[][] indices, int axis)
      Flattens the non-zero indices of a sparse COO tensor along a specified axis. Unlike cooFlattenIndices(Shape, int[][]) this method preserves the rank of the tensor.
      Parameters:
      shape - Shape of the sparse COO tensor.
      indices - Shape of the sparse COO tensor.
      axis - Axis along which to flatten the tensor.
      Returns:
      The non-zero indices flattened along the specified axis.

    • cooReshape

      public static int[][] cooReshape(Shape oldShape, Shape newShape, int[][] indices)
      Computes new indices for the reshaping of a sparse COO tensor.
      Parameters:
      oldShape - Current shape (before reshaping) of the sparse COO tensor.
      newShape - New shape of the tensor.
      indices - The non-zero indices of the tensor to be reshaped.
      Returns:
      The non-zero indices corresponding to the reshaped tensor.

    • createMap

      public static Map<Integer,List<Integer>> createMap(int nnz, int[] rowIndices)
      Creates a HashMap where the keys are row indices and the value is a list of all indices in src with that row index.
      Parameters:
      nnz - Number of non-zero data in the sparse matrix.
      rowIndices - Row indices of sparse matrix.
      Returns:
      A HashMap where the keys are row indices and the value is a list of all indices in src with that row index.

    • sortCsrMatrix

      public static void sortCsrMatrix(double[] entries, int[] rowPointers, int[] colIndices)
      Sorts the non-zero data and column indices of a sparse CSR matrix lexicographically by row and column index. The row pointers in the CSR matrix are assumed to be correct already.
      Parameters:
      entries - Non-zero data of the CSR matrix.
      rowPointers - Row pointer array of the CSR matrix. Stores the starting index for each row of the CSR matrix in data and
      colIndices - Non-zero column indices of the CSR matrix.

    • sortCsrMatrix

      public static void sortCsrMatrix(Object[] entries, int[] rowPointers, int[] colIndices)
      Sorts the non-zero data and column indices of a sparse CSR matrix lexicographically by row and column index. The row pointers in the CSR matrix are assumed to be correct already.
      Parameters:
      entries - Non-zero data of the CSR matrix.
      rowPointers - Row pointer array of the CSR matrix. Stores the starting index for each row of the CSR matrix in data and
      colIndices - Non-zero column indices of the CSR matrix.

    • CSREquals

      public static boolean CSREquals(CsrMatrix src1, CsrMatrix src2)

      Checks if two CSR Matrices are equal considering the fact that one may explicitly store zeros at some position that the other does not store.

      If zeros are explicitly stored at some position in only one matrix, it will be checked that the other matrix does not have a non-zero value at the same index. If it does, the matrices will not be equal. If no value is stored for that index then it is assumed to be zero by definition of the CSR format and the equality check continues with the remaining values.

      Parameters:
      src1 - First CSR matrix in the equality comparison.
      src2 - Second CSR matrix in the equality comparison.
      Returns:
      True if all non-zero values stored in the two matrices are equal and occur at the same indices.

    • CSREquals

      public static <T extends Semiring<T>> boolean CSREquals(AbstractCsrSemiringMatrix<?,?,?,T> src1, AbstractCsrSemiringMatrix<?,?,?,T> src2)

      Checks if two CSR Field matrices are equal considering the fact that one may explicitly store zeros at some position that the other does not store.

      If zeros are explicitly stored at some position in only one matrix, it will be checked that the other matrix does not have a non-zero value at the same index. If it does, the matrices will not be equal. If no value is stored for that index then it is assumed to be zero by definition of the CSR format and the equality check continues with the remaining values.

      Parameters:
      src1 - First CSR matrix in the equality comparison.
      src2 - Second CSR matrix in the equality comparison.
      Returns:
      True if all non-zero values stored in the two matrices are equal and occur at the same indices.

    • copyRanges

      public static <T> void copyRanges(T[] srcEntries, int[] srcRowIndices, int[] srcColIndices, T[] destEntries, int[] destRowIndices, int[] destColIndices, int[] startEnd)
      A helper method which copies from a sparse COO matrix to a set of three arrays (non-zero data, row indices, and column indices) but skips over a specified range.
      Parameters:
      srcEntries - Non-zero matrix to copy ranges from.
      srcRowIndices - Row indices of matrix to copy ranges from.
      srcColIndices - Column indices of matrix to copy ranges from.
      destEntries - Array to copy src non-zero data to.
      destRowIndices - Array to copy src row indices data to.
      destColIndices - Array to copy src column indices data to.
      startEnd - An array of length two specifying the start (inclusive) and end (exclusive) indices of the range to skip during the copy.

    • coalesce

      public static <T> SparseMatrixData<T> coalesce(BinaryOperator<T> aggregator, Shape shape, T[] data, int[] rowIndices, int[] colIndices)
      Coalesces this sparse COO matrix. An uncoalesced matrix is a sparse matrix with multiple data for a single index. This method will ensure that each index only has one non-zero value by aggregating duplicated data.
      Parameters:
      aggregator - Custom aggregation function to combine multiple.
      shape - Shape of the COO matrix.
      data - The non-zero data of the COO matrix.
      rowIndices - The non-zero row indices of the COO matrix.
      colIndices - The non-zero column indices of the COO matrix.
      Returns:
      A SparseMatrixData object containing the data of the COO matrix resulting from the coalesce operation.

    • coalesce

      public static <T> SparseTensorData<T> coalesce(BinaryOperator<T> aggregator, Shape shape, T[] data, int[][] indices)
      Coalesces this sparse COO tensor. An uncoalesced matrix is a sparse tensor with multiple data for a single index. This method will ensure that each index only has one non-zero value by aggregating duplicated data.
      Parameters:
      aggregator - Custom aggregation function to combine multiple.
      shape - Shape of the COO tensor.
      data - The non-zero data of the COO tensor.
      rowIndices - The non-zero row indices of the COO tensor.
      colIndices - The non-zero column indices of the COO tensor.
      Returns:
      A SparseTensorData object containing the data of the COO tensor resulting from the coalesce operation.

    • coalesce

      public static <T> SparseVectorData<T> coalesce(BinaryOperator<T> aggregator, Shape shape, T[] data, int[] indices)
      Coalesces this sparse COO vector. An uncoalesced matrix is a sparse vector with multiple data for a single index. This method will ensure that each index only has one non-zero value by aggregating duplicated data.
      Parameters:
      aggregator - Custom aggregation function to combine multiple.
      shape - Shape of the COO vector.
      data - The non-zero data of the COO vector.
      rowIndices - The non-zero row indices of the COO vector.
      colIndices - The non-zero column indices of the COO vector.
      Returns:
      A SparseVectorData object containing the data of the COO vector resulting from the coalesce operation.

    • dropZeros

      public static <T extends Semiring<T>> SparseMatrixData<T> dropZeros(Shape shape, T[] data, int[] rowIndices, int[] colIndices)
      Drops any explicit zeros in this sparse COO matrix.
      Returns:
      A SparseMatrixData object containing the data of the COO matrix resulting from dropping all explicit zeros.

    • dropZeros

      public static <T extends Semiring<T>> SparseTensorData<T> dropZeros(Shape shape, T[] data, int[][] indices)
      Drops any explicit zeros in this sparse COO tensor.
      Returns:
      A SparseTensorData object containing the data of the COO tensor resulting from dropping all explicit zeros.

    • dropZeros

      public static <T extends Semiring<T>> SparseVectorData<T> dropZeros(Shape shape, T[] data, int[] indices)
      Drops any explicit zeros in this sparse COO vector.
      Returns:
      A SparseVectorData object containing the data of the COO vector resulting from dropping all explicit zeros.

    • coalesce

      public static SparseMatrixData<Double> coalesce(BinaryOperator<Double> aggregator, Shape shape, double[] data, int[] rowIndices, int[] colIndices)
      Coalesces this sparse COO matrix. An uncoalesced matrix is a sparse matrix with multiple data for a single index. This method will ensure that each index only has one non-zero value by aggregating duplicated data.
      Parameters:
      aggregator - Custom aggregation function to combine multiple.
      shape - Shape of the COO matrix.
      data - The non-zero data of the COO matrix.
      rowIndices - The non-zero row indices of the COO matrix.
      colIndices - The non-zero column indices of the COO matrix.
      Returns:
      A SparseMatrixData object containing the data of the COO matrix resulting from the coalesce operation.

    • coalesce

      public static SparseTensorData<Double> coalesce(BinaryOperator<Double> aggregator, Shape shape, double[] data, int[][] indices)
      Coalesces this sparse COO tensor. An uncoalesced matrix is a sparse tensor with multiple data for a single index. This method will ensure that each index only has one non-zero value by aggregating duplicated data.
      Parameters:
      aggregator - Custom aggregation function to combine multiple.
      shape - Shape of the COO tensor.
      data - The non-zero data of the COO tensor.
      rowIndices - The non-zero row indices of the COO tensor.
      colIndices - The non-zero column indices of the COO tensor.
      Returns:
      A SparseTensorData object containing the data of the COO tensor resulting from the coalesce operation.

    • dropZeros

      public static SparseMatrixData<Double> dropZeros(Shape shape, double[] data, int[] rowIndices, int[] colIndices)
      Drops any explicit zeros in this sparse COO matrix.
      Returns:
      A SparseMatrixData object containing the data of the COO matrix resulting from dropping all explicit zeros.

    • dropZeros

      public static SparseTensorData<Double> dropZeros(Shape shape, double[] data, int[][] indices)
      Drops any explicit zeros in this sparse COO tensor.
      Returns:
      A SparseTensorData object containing the data of the COO tensor resulting from dropping all explicit zeros.

    • coalesce

      public static SparseVectorData<Double> coalesce(BinaryOperator<Double> aggregator, Shape shape, double[] data, int[] indices)
      Coalesces this sparse COO vector. An uncoalesced matrix is a sparse vector with multiple data for a single index. This method will ensure that each index only has one non-zero value by aggregating duplicated data.
      Parameters:
      aggregator - Custom aggregation function to combine multiple.
      shape - Shape of the COO vector.
      data - The non-zero data of the COO vector.
      rowIndices - The non-zero row indices of the COO vector.
      colIndices - The non-zero column indices of the COO vector.
      Returns:
      A SparseVectorData object containing the data of the COO vector resulting from the coalesce operation.

    • dropZeros

      public static SparseVectorData<Double> dropZeros(Shape shape, double[] data, int[] indices)
      Drops any explicit zeros in this sparse COO vector.
      Returns:
      A SparseVectorData object containing the data of the COO vector resulting from dropping all explicit zeros.

    • dropZerosCsr

      public static CsrMatrix dropZerosCsr(CsrMatrix src)
      Drops all explicit zeros within a sparse CSR matrix.
      Parameters:
      src - Matrix to drop zeros from.
      Returns:
      A copy of the src matrix with all zeros dropped.

    • dropZerosCsr

      public static <T extends Semiring<T>> SparseMatrixData<T> dropZerosCsr(Shape shape, T[] data, int[] rowPointers, int[] colIndices)
      Drops all explicit zeros within a sparse CSR matrix.
      Parameters:
      shape - Shape of the CSR matrix.
      data - Non-zero entries of the CSR matrix.
      rowPointers - Non-zero row indices of the CSR matrix.
      colIndices - Non-zero column indices of the CSR matrix.
      Returns:
      A SparseMatrixData containing the data of the CSR matrix resulting from dropping all zeros from the specified CSR matrix. Note, the returned data will be in COO format and not CSR.

    • validateSlice

      public static void validateSlice(Shape shape, int rowStart, int rowEnd, int colStart, int colEnd)
      Validates that the specified slice is a valid slice of a matrix with the specified shape.
      Parameters:
      shape - Shape of the matrix.
      rowStart - Starting row index of the slice (inclusive).
      rowEnd - Ending row index of the slice (exclusive).
      colStart - Starting column index of the slice (inclusive).
      colEnd - Ending column index of the slice (exclusive).
      Throws:
      IllegalArgumentException - If any of the following are true:
      • rowStart >= rowEnd
      • colStart >= colEnd
      • rowStart < 0 || rowEnd > shape.get(0)
      • colStart < 0 || colEnd > shape.get(1)

    • validateCsrMatrix

      public static void validateCsrMatrix(Shape shape, int nnz, int[] rowPointers, int[] colIndices)
      Validates that the provided arguments specify a valid CSR matrix.
      Parameters:
      shape - Shape of the CSR matrix.
      nnz - The number of non-zero entries of the CSR matrix.
      rowPointers - The non-zero row pointers of the CSR matrix.
      colIndices - The non-zero column indices of the CSR matrix.
      Throws:
      IllegalArgumentException - If any of the following are true:
      • shape.getRank() != 2
      • rowPointers.length != shape.get(0) + 1
      • nnz != colIndices.length

    • main

      public static void main(String[] args)