This is an automated email from the ASF dual-hosted git repository.
mboehm7 pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/systemds.git
The following commit(s) were added to refs/heads/main by this push:
new 81efec85db [SYSTEMDS-3172] Additional CSC sparse block implementation
81efec85db is described below
commit 81efec85dbd654dac1fcfa2b8009b4239f59d0c3
Author: ReneEnjilian <[email protected]>
AuthorDate: Fri Oct 25 11:53:27 2024 +0200
[SYSTEMDS-3172] Additional CSC sparse block implementation
Closes #2132.
---
.../org/apache/sysds/runtime/data/SparseBlock.java | 1 +
.../apache/sysds/runtime/data/SparseBlockCSC.java | 1455 ++++++++++++++++++++
.../sysds/runtime/data/SparseBlockFactory.java | 2 +
.../component/sparse/SparseBlockAlignment.java | 30 +
.../component/sparse/SparseBlockAppendSort.java | 36 +-
.../test/component/sparse/SparseBlockDelete.java | 15 +
.../component/sparse/SparseBlockGetFirstIndex.java | 53 +-
.../test/component/sparse/SparseBlockGetSet.java | 87 +-
.../component/sparse/SparseBlockIndexRange.java | 31 +
.../test/component/sparse/SparseBlockIterator.java | 32 +
.../component/sparse/SparseBlockMemEstimate.java | 3 +
.../test/component/sparse/SparseBlockMerge.java | 278 +++-
.../test/component/sparse/SparseBlockScan.java | 16 +
.../test/component/sparse/SparseBlockSize.java | 34 +
14 files changed, 2023 insertions(+), 50 deletions(-)
diff --git a/src/main/java/org/apache/sysds/runtime/data/SparseBlock.java
b/src/main/java/org/apache/sysds/runtime/data/SparseBlock.java
index 648f42b690..91bba40d0c 100644
--- a/src/main/java/org/apache/sysds/runtime/data/SparseBlock.java
+++ b/src/main/java/org/apache/sysds/runtime/data/SparseBlock.java
@@ -50,6 +50,7 @@ public abstract class SparseBlock implements Serializable,
Block
public enum Type {
COO, // coordinate
CSR, // compressed sparse rows
+ CSC, // compressed sparse column
DCSR, // double compressed sparse rows
MCSR, // modified compressed sparse rows (update-friendly)
MCSC, // modified compressed sparse column
diff --git a/src/main/java/org/apache/sysds/runtime/data/SparseBlockCSC.java
b/src/main/java/org/apache/sysds/runtime/data/SparseBlockCSC.java
new file mode 100644
index 0000000000..1532c02b7c
--- /dev/null
+++ b/src/main/java/org/apache/sysds/runtime/data/SparseBlockCSC.java
@@ -0,0 +1,1455 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.sysds.runtime.data;
+
+import org.apache.sysds.runtime.util.SortUtils;
+import org.apache.sysds.runtime.util.UtilFunctions;
+import org.apache.sysds.utils.MemoryEstimates;
+
+import java.io.DataInput;
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.BitSet;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.List;
+
+/**
+ * SparseBlock implementation that realizes a traditional 'compressed sparse
column' representation, where the entire
+ * sparse block is stored as three arrays: ptr of length clen+1 to store
offsets per column, and indexes/values of
+ * length nnz to store row indexes and values of non-zero entries. This format
is very memory efficient for sparse (but
+ * not ultra-sparse) matrices and provides very good performance for common
operations, partially due to lower memory
+ * bandwidth requirements. However, this format is slow on incremental
construction (because it does not allow
+ * append/sort per row) without reshifting. For these types of operations, the
'modified compressed sparse row/column'
+ * representations are better suited since they are update friendlier.
Further, this representation implements both the
+ * row oriented and the column oriented one. By implementing the row-oriented
API, we ensure interoperability with
+ * existing operators. Finally, the total nnz is limited to INTEGER_MAX,
whereas for SparseBlockMCSR only the nnz per
+ * row are limited to INTEGER_MAX.
+ *
+ * TODO performance - currently this sparse block is very slow and this slows
down even the component tests
+ */
+
+public class SparseBlockCSC extends SparseBlock {
+
+ private static final long serialVersionUID = -8020198259526080455L;
+ private int[] _ptr = null; //column pointer array (size: clen+1)
+ private int[] _indexes = null; //row index array (size: >=nnz)
+ private double[] _values = null; //value array (size: >=nnz)
+ private int _size = 0; //actual number of nnz
+ private int _rlen = -1; // number of rows
+ private int _clenInferred = -1;
+
+ public SparseBlockCSC(int rlen, int clen) {
+ _rlen = rlen;
+ _ptr = new int[clen + 1];
+ _indexes = new int[INIT_CAPACITY];
+ _values = new double[INIT_CAPACITY];
+ _size = 0;
+ }
+
+ public SparseBlockCSC(int clen, int capacity, int size) {
+ _ptr = new int[clen + 1]; //ix0=0
+ _indexes = new int[capacity];
+ _values = new double[capacity];
+ _size = size;
+ }
+
+ public SparseBlockCSC(int[] rowPtr, int[] rowInd, double[] values, int
nnz) {
+ _ptr = rowPtr;
+ _indexes = rowInd;
+ _values = values;
+ _size = nnz;
+ }
+
+ public SparseBlockCSC(SparseBlock sblock, int clen) {
+ _clenInferred = clen;
+ _rlen = sblock.numRows();
+ _size = (int) sblock.size();
+ initialize(sblock);
+ }
+
+ public SparseBlockCSC(SparseBlock sblock) {
+ inferNumCol(sblock);
+ _rlen = sblock.numRows();
+ _size = (int) sblock.size();
+ initialize(sblock);
+ }
+
+ private void initialize(SparseBlock sblock) {
+
+ if(_size > Integer.MAX_VALUE)
+ throw new RuntimeException("SparseBlockCSC supports
nnz<=Integer.MAX_VALUE but got " + _size);
+
+ //special case SparseBlockCSC
+ if(sblock instanceof SparseBlockCSC) {
+ SparseBlockCSC originalCSC = (SparseBlockCSC) sblock;
+ _ptr = Arrays.copyOf(originalCSC._ptr,
originalCSC.numCols() + 1);
+ _indexes = Arrays.copyOf(originalCSC._indexes,
originalCSC._size);
+ _values = Arrays.copyOf(originalCSC._values,
originalCSC._size);
+ }
+
+ //special case SparseBlockMCSC
+ else if(sblock instanceof SparseBlockMCSC) {
+ SparseBlockMCSC originalMCSC = (SparseBlockMCSC) sblock;
+ _ptr = new int[originalMCSC.numCols() + 1];
+ _ptr[0] = 0;
+ _values = new double[(int) originalMCSC.size()];
+ _indexes = new int[(int) originalMCSC.size()];
+ int ptrPos = 1;
+ int valPos = 0;
+ SparseRow columns[] = originalMCSC.getCols();
+ for(SparseRow column : columns) {
+ int rowIdx[] = column.indexes();
+ double vals[] = column.values();
+ for(int i = 0; i < column.size(); i++) {
+ _indexes[valPos + i] = rowIdx[i];
+ _values[valPos + i] = vals[i];
+ }
+ _ptr[ptrPos] = _ptr[ptrPos - 1] + column.size();
+ ptrPos++;
+ valPos += column.size();
+ }
+ }
+
+ // general case sparse block (CSR, MCSR, DCSR)
+ else {
+ int rlen = _rlen;
+ int clen = _clenInferred;
+ int nnz = _size; // total number of non-zero elements
+
+ // Step 1: Count non-zero elements per column
+ int[] colCounts = new int[clen];
+ for(int i = 0; i < rlen; i++) {
+ if(!sblock.isEmpty(i)) {
+ int alen = sblock.size(i);
+ int apos = sblock.pos(i);
+ int[] aix = sblock.indexes(i);
+ for(int k = apos; k < apos + alen; k++)
{
+ int col = aix[k];
+ colCounts[col]++;
+ }
+ }
+ }
+
+ // Step 2: Compute CSC pointer array (_ptr)
+ _ptr = new int[clen + 1];
+ _ptr[0] = 0;
+ for(int j = 0; j < clen; j++) {
+ _ptr[j + 1] = _ptr[j] + colCounts[j];
+ }
+
+ // Step 3: Initialize arrays for indexes and values
+ _size = nnz;
+ _indexes = new int[nnz];
+ _values = new double[nnz];
+
+ // Step 4: Initialize position trackers for each column
+ int[] colPositions = new int[clen];
+ System.arraycopy(_ptr, 0, colPositions, 0, clen);
+
+ // Step 5: Fill CSC indexes (_indexes) and values
(_values) arrays
+ for(int i = 0; i < rlen; i++) {
+ if(!sblock.isEmpty(i)) {
+ int alen = sblock.size(i);
+ int apos = sblock.pos(i);
+ int[] aix = sblock.indexes(i);
+ double[] avals = sblock.values(i);
+ for(int k = apos; k < apos + alen; k++)
{
+ int col = aix[k];
+ int pos = colPositions[col];
+ _indexes[pos] = i; //
row index
+ _values[pos] = avals[k]; //
value
+ colPositions[col]++;
+ }
+ }
+ }
+ }
+ }
+
+ public SparseBlockCSC(SparseRow[] cols, int nnz) {
+
+ int clen = cols.length;
+ _clenInferred = clen;
+ _ptr = new int[clen + 1]; //ix0=0
+ _indexes = new int[nnz];
+ _values = new double[nnz];
+ _size = nnz;
+
+ for(int i = 0, pos = 0; i < clen; i++) {
+ if(cols[i] != null && !cols[i].isEmpty()) {
+ int alen = cols[i].size();
+ int[] aix = cols[i].indexes();
+ double[] avals = cols[i].values();
+ System.arraycopy(aix, 0, _indexes, pos, alen);
+ System.arraycopy(avals, 0, _values, pos, alen);
+ pos += alen;
+ }
+ _ptr[i + 1] = pos;
+ }
+ }
+
+ public SparseBlockCSC(int cols, int[] rowInd, int[] colInd, double[]
values) {
+ int nnz = values.length;
+ _ptr = new int[cols + 1];
+ _indexes = Arrays.copyOf(rowInd, rowInd.length);
+ _values = Arrays.copyOf(values, nnz);
+ _size = nnz;
+ _clenInferred = cols;
+
+ //single-pass construction of pointers
+ int clast = 0;
+ for(int i = 0; i < nnz; i++) {
+ int c = colInd[i];
+ if(clast < c)
+ Arrays.fill(_ptr, clast + 1, c + 1, i);
+ clast = c;
+ }
+ Arrays.fill(_ptr, clast + 1, numCols() + 1, nnz);
+
+ }
+
+ public SparseBlockCSC(int cols, int nnz, int[] rowInd) {
+
+ _clenInferred = cols;
+ _ptr = new int[cols + 1];
+ _indexes = Arrays.copyOf(rowInd, nnz);
+ _values = new double[nnz];
+ Arrays.fill(_values, 1);
+ _size = nnz;
+
+ //single-pass construction of col pointers
+ //and copy of row indexes if necessary
+ for(int i = 0, pos = 0; i < cols; i++) {
+ if(rowInd[i] >= 0) {
+ if(cols > nnz)
+ _indexes[pos] = rowInd[i];
+ pos++;
+ }
+ _ptr[i + 1] = pos;
+ }
+ }
+
+ /**
+ * Initializes the CSC sparse block from an ordered input stream of
ultra-sparse ijv triples.
+ *
+ * @param nnz number of non-zeros to read
+ * @param in data input stream of ijv triples, ordered by column and
row indices
+ * @throws IOException if deserialization error occurs
+ */
+ public void initUltraSparse(int nnz, DataInput in) throws IOException {
+ // Allocate space if necessary
+ if(_values.length < nnz)
+ resize(newCapacity(nnz));
+
+ // Read ijv triples, append and update pointers
+ int clast = 0;
+ for(int i = 0; i < nnz; i++) {
+ int r = in.readInt();
+ int c = in.readInt();
+ double v = in.readDouble();
+
+ if(clast < c)
+ Arrays.fill(_ptr, clast + 1, c + 1, i);
+ clast = c;
+
+ _indexes[i] = r; // Row indices in CSC
+ _values[i] = v;
+ }
+ Arrays.fill(_ptr, clast + 1, numCols() + 1, nnz);
+
+ // Update meta data
+ _size = nnz;
+ }
+
+ /**
+ * Initializes the CSC sparse block from an ordered input stream of
sparse columns (colnnz, iv-pairs*).
+ *
+ * @param clen number of columns
+ * @param nnz number of non-zeros to read
+ * @param in data input stream of sparse columns, ordered by column
index
+ * @throws IOException if deserialization error occurs
+ */
+ public void initSparse(int clen, int nnz, DataInput in) throws
IOException {
+ // Allocate space if necessary
+ if(_values.length < nnz) {
+ resize(newCapacity(nnz));
+ System.out.println("hallo");
+ }
+ // Read sparse columns, append and update pointers
+ _ptr[0] = 0;
+ for(int c = 0, pos = 0; c < clen; c++) {
+ int lnnz = in.readInt(); // Number of non-zeros in
column c
+ for(int j = 0; j < lnnz; j++, pos++) {
+ _indexes[pos] = in.readInt(); // Row index
+ _values[pos] = in.readDouble(); // Value
+ }
+ _ptr[c + 1] = pos;
+ }
+
+ // Update meta data
+ _size = nnz;
+ }
+
+ /**
+ * Get the estimated in-memory size of the sparse block in CSC with the
given dimensions w/o accounting for
+ * overallocation.
+ *
+ * @param nrows number of rows
+ * @param ncols number of columns
+ * @param sparsity sparsity ratio
+ * @return memory estimate
+ */
+ public static long estimateSizeInMemory(long nrows, long ncols, double
sparsity) {
+ double lnnz = Math.max(INIT_CAPACITY, Math.ceil(sparsity *
nrows * ncols));
+
+ //32B overhead per array, int arr in nrows, int/double arr in
nnz
+ double size = 16 + 4 + 4; //object +
int field + padding
+ size += MemoryEstimates.intArrayCost(nrows + 1); //ptr
array (row pointers)
+ size += MemoryEstimates.intArrayCost((long) lnnz); //indexes
array (column indexes)
+ size += MemoryEstimates.doubleArrayCost((long) lnnz);//values
array (non-zero values)
+
+ //robustness for long overflows
+ return (long) Math.min(size, Long.MAX_VALUE);
+ }
+
+ /**
+ * Get raw access to underlying array of column pointers For use in GPU
code
+ *
+ * @return array of column pointers
+ */
+ public int[] colPointers() {
+ return _ptr;
+ }
+
+ /**
+ * Get raw access to underlying array of row indices For use in GPU code
+ *
+ * @return array of row indexes
+ */
+ public int[] indexes() {
+ return indexes(0);
+ }
+
+ /**
+ * Get raw access to underlying array of values For use in GPU code
+ *
+ * @return array of values
+ */
+ public double[] values() {
+ return values(0);
+ }
+
+ ///////////////////
+ //SparseBlock implementation
+
+ @Override
+ public void allocate(int r) {
+ //do nothing everything preallocated
+ }
+
+ @Override
+ public void allocate(int r, int nnz) {
+ //do nothing everything preallocated
+ }
+
+ @Override
+ public void allocate(int r, int ennz, int maxnnz) {
+ //do nothing everything preallocated
+ }
+
+ @Override
+ public void compact(int r) {
+ //do nothing everything preallocated
+ }
+
+ @Override
+ public int numRows() {
+ if(_rlen > -1)
+ return _rlen;
+ else {
+ int rlen = Arrays.stream(_indexes).max().getAsInt();
+ _rlen = rlen;
+ return rlen;
+ }
+ }
+
+ /**
+ * Get the number of columns in the CSC block
+ *
+ * @return number of columns
+ */
+ public int numCols() {
+ return _ptr.length - 1;
+ }
+
+ @Override
+ public boolean isThreadSafe() {
+ return false;
+ }
+
+ @Override
+ public boolean isContiguous() {
+ return true;
+ }
+
+ @Override
+ public boolean isAllocated(int r) {
+ return true;
+ }
+
+ @Override
+ public void reset() {
+ if(_size > 0) {
+ Arrays.fill(_ptr, 0);
+ _size = 0;
+ }
+ }
+
+ @Override
+ public void reset(int ennz, int maxnnz) {
+ if(_size > 0) {
+ Arrays.fill(_ptr, 0);
+ _size = 0;
+ }
+ }
+
+ @Override
+ public void reset(int r, int ennz, int maxnnz) {
+ List<Integer> cols = new ArrayList<>();
+ List<Integer> posIdx = new ArrayList<>();
+ // find columns containing marked row index and
+ // position in indexes
+ for(int i = 0; i < _ptr.length - 1; i++) {
+ for(int j = _ptr[i]; j < _ptr[i + 1]; j++) {
+ if(_indexes[j] == r) {
+ cols.add(i);
+ posIdx.add(j);
+ }
+ }
+ }
+ // reduce pointer array.
+ for(int c : cols) {
+ decrPtr(c + 1);
+ }
+ // adapt indexes and values
+ for(int i = posIdx.size() - 1; i >= 0; i--) {
+ if(posIdx.get(i) < _size - 1) {
+ System.arraycopy(_indexes, posIdx.get(i) + 1,
_indexes, posIdx.get(i), _size - (posIdx.get(i) + 1));
+ System.arraycopy(_values, posIdx.get(i) + 1,
_values, posIdx.get(i), _size - (posIdx.get(i) + 1));
+ }
+ }
+ _size -= posIdx.size();
+ }
+
+ public void resetCol(int c) {
+ int pos = posCol(c);
+ int len = sizeCol(c);
+
+ if(len > 0) {
+ //overlapping array copy (shift rhs values left)
+ System.arraycopy(_indexes, pos + len, _indexes, pos,
_size - (pos + len));
+ System.arraycopy(_values, pos + len, _values, pos,
_size - (pos + len));
+ _size -= len;
+ decrPtr(c + 1, len);
+ }
+ }
+
+ @Override
+ public long size() {
+ return _ptr[_ptr.length - 1];
+ }
+
+ @Override
+ public int size(int r) {
+ if(r < 0)
+ throw new RuntimeException("Row index has to be zero or
larger.");
+
+ int nnz = 0;
+ for(int i = 0; i < _size; i++) {
+ if(_indexes[i] == r)
+ nnz++;
+ }
+ return nnz;
+ }
+
+ public int sizeCol(int c) {
+ return _ptr[c + 1] - _ptr[c];
+ }
+
+ @Override
+ public long size(int rl, int ru) {
+ if(rl < 0 || ru > _rlen)
+ throw new RuntimeException("Incorrect row boundaries.");
+
+ int nnz = 0;
+ int row = -1;
+ for(int i = 0; i < _size; i++) {
+ row = _indexes[i];
+ for(int j = rl; j < ru; j++) {
+ if(row == j) {
+ nnz++;
+ break;
+ }
+ }
+ }
+ return nnz;
+ }
+
+ public long sizeCol(int cl, int cu) {
+ return _ptr[cu] - _ptr[cl];
+ }
+
+ @Override
+ public long size(int rl, int ru, int cl, int cu) {
+ long nnz = 0;
+ for(int i = cl; i < cu; i++)
+ if(!isEmptyCol(i)) {
+ int start = internPosFIndexGTECol(rl, i);
+ int end = internPosFIndexLTECol(ru - 1, i);
+ nnz += (start != -1 && end != -1) ? (end -
start + 1) : 0;
+ }
+ return nnz;
+ }
+
+ @Override
+ public boolean isEmpty(int r) {
+ boolean empty = true;
+ for(int i = 0; i < _size; i++) {
+ if(_indexes[i] == r)
+ return false;
+ }
+ return empty;
+ }
+
+ public boolean isEmptyCol(int c) {
+ return (_ptr[c + 1] - _ptr[c] == 0);
+ }
+
+ @Override
+ public boolean checkValidity(int rlen, int clen, long nnz, boolean
strict) {
+ //1. correct meta data
+ if(rlen < 0 || clen < 0) {
+ throw new RuntimeException("Invalid block dimensions: "
+ rlen + " " + clen);
+ }
+
+ //2. correct array lengths
+ if(_size != nnz && _ptr.length < clen + 1 && _values.length <
nnz && _indexes.length < nnz) {
+ throw new RuntimeException("Incorrect array lengths.");
+ }
+
+ //3. non-decreasing row pointers
+ for(int i = 1; i < clen; i++) {
+ if(_ptr[i - 1] > _ptr[i] && strict)
+ throw new RuntimeException(
+ "Column pointers are decreasing at
column: " + i + ", with pointers " + _ptr[i - 1] + " > " +
+ _ptr[i]);
+ }
+
+ //4. sorted row indexes per column
+ for(int i = 0; i < clen; i++) {
+ int apos = posCol(i);
+ int alen = sizeCol(i);
+ for(int k = apos + 1; k < apos + alen; k++)
+ if(_indexes[k - 1] >= _indexes[k])
+ throw new RuntimeException(
+ "Wrong sparse column ordering:
" + k + " " + _indexes[k - 1] + " " + _indexes[k]);
+ for(int k = apos; k < apos + alen; k++)
+ if(_values[k] == 0)
+ throw new RuntimeException("Wrong
sparse column: zero at " + k + " at row index " + _indexes[k]);
+ }
+
+ //5. non-existing zero values
+ for(int i = 0; i < _size; i++) {
+ if(_values[i] == 0) {
+ throw new RuntimeException(
+ "The values array should not contain
zeros." + " The " + i + "th value is " + _values[i]);
+ }
+ }
+
+ //6. a capacity that is no larger than nnz times resize factor.
+ int capacity = _values.length;
+ if(capacity > nnz * RESIZE_FACTOR1) {
+ throw new RuntimeException(
+ "Capacity is larger than the nnz times a resize
factor." + " Current size: " + capacity +
+ ", while Expected size:" + nnz *
RESIZE_FACTOR1);
+ }
+
+ return true;
+ }
+
+ @Override
+ public long getExactSizeInMemory() {
+ //32B overhead per array, int arr in nrows, int/double arr in
nnz
+ double size = 16 + 4 + 4;
//object + int field + padding
+ size += MemoryEstimates.intArrayCost(_ptr.length); //ptr
array (row pointers)
+ size += MemoryEstimates.intArrayCost(_indexes.length);
//indexes array (column indexes)
+ size += MemoryEstimates.doubleArrayCost(_values.length);
//values array (non-zero values)
+
+ //robustness for long overflows
+ return (long) Math.min(size, Long.MAX_VALUE);
+ }
+
+ @Override
+ public int[] indexes(int r) {
+ //Count elements per row
+ //int[] rowCounts = numElemPerRow();
+
+ // Compute csr pointers
+ int[] csrPtr = rowPointerAll();
+
+ // Populate CSR indices array
+ int[] csrIndices = new int[_size];
+ // Temporary array to keep track of the current position in
each row
+ int[] currentPos = Arrays.copyOf(csrPtr, _rlen);
+
+ for(int col = 0; col < numCols(); col++) {
+ for(int i = _ptr[col]; i < _ptr[col + 1]; i++) {
+ int row = _indexes[i];
+ int pos = currentPos[row]++;
+ csrIndices[pos] = col;
+ }
+ }
+
+ return csrIndices;
+ }
+
+ public int[] indexesCol(int c) {
+ return _indexes;
+ }
+
+ @Override
+ public double[] values(int r) {
+ // Only use first _size elements for sorting
+ Integer[] idx = new Integer[_size];
+ for(int i = 0; i < _size; i++)
+ idx[i] = i;
+
+ // Sort indices based on corresponding index values
+ Arrays.sort(idx, Comparator.comparingInt(i -> _indexes[i]));
+
+ // Create values array sorted in row order
+ double[] csrValues = new double[_size];
+ for(int i = 0; i < _size; i++) {
+ csrValues[i] = _values[idx[i]];
+ }
+ return csrValues;
+ }
+
+ public double[] valuesCol(int c) {
+ return _values;
+ }
+
+ @Override
+ public int pos(int r) {
+ int nnz = 0;
+ for(int i = 0; i < _size; i++) {
+ if(_indexes[i] < r)
+ nnz++;
+ }
+ return nnz;
+ }
+
+ public int posCol(int c) {
+ return _ptr[c];
+ }
+
+ @Override
+ public boolean set(int r, int c, double v) {
+ int pos = posCol(c);
+ int len = sizeCol(c);
+
+ //search for existing col index
+ int index = Arrays.binarySearch(_indexes, pos, pos + len, r);
+ if(index >= 0) {
+ //delete/overwrite existing value (on value delete, we
shift
+ //left for (1) correct nnz maintenance, and (2) smaller
size)
+ if(v == 0) {
+ shiftLeftAndDelete(index);
+ decrPtr(c + 1);
+ return true; // nnz--
+ }
+ else {
+ _values[index] = v;
+ return false;
+ }
+ }
+
+ //early abort on zero (if no overwrite)
+ if(v == 0)
+ return false;
+
+ //insert new index-value pair
+ index = Math.abs(index + 1);
+ if(_size == _values.length)
+ resizeAndInsert(index, r, v);
+ else
+ shiftRightAndInsert(index, r, v);
+ incrPtr(c + 1);
+ return true; // nnz++
+ }
+
+ @Override
+ public void set(int r, SparseRow row, boolean deep) {
+ double[] values = row.values();
+ int[] colIndexes = row.indexes();
+ for(int i = 0; i < row.size(); i++) {
+ set(r, colIndexes[i], values[i]);
+ }
+ }
+
+ public void setCol(int c, SparseRow col, boolean deep) {
+ int pos = posCol(c);
+ int len = sizeCol(c);
+ int alen = col.size();
+ int[] aix = col.indexes();
+ double[] avals = col.values();
+
+ //delete existing values if necessary
+ if(len > 0) //incl size update
+ deleteIndexRange(c, aix[pos], aix[pos + len - 1] + 1);
+
+ //prepare free space (allocate and shift)
+ int lsize = _size + alen;
+ if(_values.length < lsize)
+ resize(lsize);
+ shiftRightByN(pos, alen); //incl size update
+ incrPtr(c + 1, alen);
+
+ //copy input row into internal representation
+ System.arraycopy(aix, 0, _indexes, pos, alen);
+ System.arraycopy(avals, 0, _values, pos, alen);
+ }
+
+ @Override
+ public boolean add(int r, int c, double v) {
+ //early abort on zero
+ if(v == 0)
+ return false;
+
+ int pos = posCol(c);
+ int len = sizeCol(c);
+
+ //search for existing col index
+ int index = Arrays.binarySearch(_indexes, pos, pos + len, r);
+ if(index >= 0) {
+ //add to existing value
+ _values[index] += v;
+ return false;
+ }
+
+ //insert new index-value pair
+ index = Math.abs(index + 1);
+ if(_size == _values.length)
+ resizeAndInsert(index, r, v);
+ else
+ shiftRightAndInsert(index, r, v);
+ incrPtr(c + 1);
+ return true; // nnz++
+ }
+
+ @Override
+ public void append(int r, int c, double v) {
+ //early abort on zero
+ if(v == 0)
+ return;
+
+ int pos = posCol(c);
+ int len = sizeCol(c);
+ if(pos + len == _size) {
+ //resize and append
+ if(_size == _values.length)
+ resize();
+ insert(_size, r, v);
+ }
+ else {
+ //resize, shift and insert
+ if(_size == _values.length)
+ resizeAndInsert(pos + len, r, v);
+ else
+ shiftRightAndInsert(pos + len, r, v);
+ }
+ incrPtr(c + 1);
+
+ }
+
+ @Override
+ public void setIndexRange(int r, int cl, int cu, double[] v, int vix,
int vlen) {
+ //delete existing values in range if necessary
+ if(!isEmpty(r))
+ deleteIndexRange(r, cl, cu);
+
+ //determine input nnz
+ int lnnz = UtilFunctions.computeNnz(v, vix, vlen);
+
+ //prepare free space (allocate and shift)
+ int lsize = _size + lnnz;
+ if(_values.length < lsize)
+ resize(lsize);
+
+ // calculate insertion points / positions to shift
+ int[] posIdx = new int[vlen];
+ int insertionPnt = 0;
+ for(int i = cl; i < cu; i++) {
+ for(int j = _ptr[i]; j < _ptr[i + 1]; j++) {
+ if(_indexes[j] > r) {
+ posIdx[insertionPnt] = j;
+ break;
+ }
+ if(j == _ptr[i + 1] - 1)
+ posIdx[insertionPnt] = j + 1;
+ }
+ insertionPnt++;
+ }
+
+ // shift to the right by 1 given insertion points stored in
posIdx
+ for(int i = vix + vlen - 1; i >= vix; i--) {
+ System.arraycopy(_indexes, posIdx[i - vix], _indexes,
posIdx[i - vix] + 1, _size - posIdx[i - vix]);
+ System.arraycopy(_values, posIdx[i - vix], _values,
posIdx[i - vix] + 1, _size - posIdx[i - vix]);
+ _size++;
+ _values[posIdx[i - vix]] = v[i];
+ _indexes[posIdx[i - vix]] = r;
+ }
+
+ // Increment pointer array
+ for(int c = cl; c < cu; c++)
+ incrPtr(c + 1);
+
+ }
+
+ public void setIndexRangeCol(int c, int rl, int ru, double[] v, int
vix, int vlen) {
+ //delete existing values in range if necessary
+ if(!isEmptyCol(c))
+ deleteIndexRangeCol(c, rl, ru);
+
+ //determine input nnz
+ int lnnz = UtilFunctions.computeNnz(v, vix, vlen);
+
+ //prepare free space (allocate and shift)
+ int lsize = _size + lnnz;
+ if(_values.length < lsize)
+ resize(lsize);
+ int index = internPosFIndexGTCol(rl, c);
+ int index2 = (index > 0) ? index : posCol(c + 1);
+ shiftRightByN(index2, lnnz);
+
+ //insert values
+ for(int i = vix; i < vix + vlen; i++)
+ if(v[i] != 0) {
+ _indexes[index2] = rl + i - vix;
+ _values[index2] = v[i];
+ index2++;
+ }
+ incrPtr(c + 1, lnnz);
+ }
+
+ @Override
+ public void setIndexRange(int r, int cl, int cu, double[] v, int[] vix,
int vpos, int vlen) {
+ //delete existing values in range if necessary
+ if(!isEmpty(r))
+ deleteIndexRange(r, cl, cu);
+
+ //prepare free space (allocate and shift)
+ int lsize = _size + vlen;
+ if(_values.length < lsize)
+ resize(lsize);
+
+ int[] posIdx = new int[vlen];
+ int insertionPnt = 0;
+ int currentCol = 0;
+ for(int i = vpos; i < vpos + vlen; i++) {
+ currentCol = vix[i];
+ for(int j = _ptr[currentCol]; j < _ptr[currentCol + 1];
j++) {
+ if(_indexes[j] > r) {
+ posIdx[insertionPnt] = j;
+ break;
+ }
+ if(j == _ptr[currentCol + 1] - 1)
+ posIdx[insertionPnt] = j + 1;
+ }
+ insertionPnt++;
+ }
+
+ // shift to the right by 1 given insertion points stored in
posIdx
+ for(int i = vpos + vlen - 1; i >= vpos; i--) {
+ System.arraycopy(_indexes, posIdx[i - vpos], _indexes,
posIdx[i - vpos] + 1, _size - posIdx[i - vpos]);
+ System.arraycopy(_values, posIdx[i - vpos], _values,
posIdx[i - vpos] + 1, _size - posIdx[i - vpos]);
+ _size++;
+ _values[posIdx[i - vpos]] = v[i];
+ _indexes[posIdx[i - vpos]] = r;
+ }
+
+ // Increment pointer array
+ for(int i = vpos; i < vpos + vlen; i++) {
+ currentCol = vix[i];
+ incrPtr(currentCol + 1);
+ }
+ }
+
+ public void setIndexRangeCol(int c, int rl, int ru, double[] v, int[]
vix, int vpos, int vlen) {
+ //delete existing values in range if necessary
+ if(!isEmptyCol(c))
+ deleteIndexRangeCol(c, rl, ru);
+
+ //prepare free space (allocate and shift)
+ int lsize = _size + vlen;
+ if(_values.length < lsize)
+ resize(lsize);
+ int index = internPosFIndexGTCol(rl, c);
+ int index2 = (index > 0) ? index : posCol(c + 1);
+ shiftRightByN(index2, vlen);
+
+ //insert values
+ for(int i = vpos; i < vpos + vlen; i++) {
+ _indexes[index2] = vix[i];
+ _values[index2] = v[i];
+ index2++;
+ }
+ incrPtr(c + 1, vlen);
+ }
+
+ @Override
+ public void deleteIndexRange(int r, int cl, int cu) {
+ List<Integer> cols = new ArrayList<>();
+ List<Integer> posIdx = new ArrayList<>();
+ // find columns containing marked row index and
+ // position in indexes
+ for(int i = cl; i < cu; i++) {
+ for(int j = _ptr[i]; j < _ptr[i + 1]; j++) {
+ if(_indexes[j] == r) {
+ cols.add(i);
+ posIdx.add(j);
+ }
+ }
+ }
+ // reduce pointer array.
+ for(int c : cols) {
+ decrPtr(c + 1);
+ }
+ // adapt indexes and values
+ for(int i = posIdx.size() - 1; i >= 0; i--) {
+ if(posIdx.get(i) < _size - 1) {
+ System.arraycopy(_indexes, posIdx.get(i) + 1,
_indexes, posIdx.get(i), _size - (posIdx.get(i) + 1));
+ System.arraycopy(_values, posIdx.get(i) + 1,
_values, posIdx.get(i), _size - (posIdx.get(i) + 1));
+ }
+ }
+ _size -= posIdx.size();
+ }
+
+ public void deleteIndexRangeCol(int c, int rl, int ru) {
+ int start = internPosFIndexGTECol(rl, c);
+ if(start < 0) //nothing to delete
+ return;
+
+ int len = sizeCol(c);
+ int end = internPosFIndexGTECol(ru, c);
+ if(end < 0) //delete all remaining
+ end = start + len;
+
+ //overlapping array copy (shift rhs values left)
+ System.arraycopy(_indexes, end, _indexes, start, _size - end);
+ System.arraycopy(_values, end, _values, start, _size - end);
+ _size -= (end - start);
+
+ decrPtr(c + 1, end - start);
+ }
+
+ @Override
+ public void sort() {
+ for(int i = 0; i < numCols() && posCol(i) < _size; i++) {
+ sortCol(i);
+ }
+ }
+
+ @Override
+ public void sort(int r) {
+ sort();
+ }
+
+ public void sortCol(int c) {
+ int pos = posCol(c);
+ int len = sizeCol(c);
+
+ if(len <= 100 || !SortUtils.isSorted(pos, pos + len, _indexes))
+ SortUtils.sortByIndex(pos, pos + len, _indexes,
_values);
+ }
+
+ @Override
+ public double get(int r, int c) {
+ if(isEmptyCol(c))
+ return 0;
+ int pos = posCol(c);
+ int len = sizeCol(c);
+
+ //search for existing col index in [pos,pos+len)
+ int index = Arrays.binarySearch(_indexes, pos, pos + len, r);
+ return (index >= 0) ? _values[index] : 0;
+ }
+
+ @Override
+ public SparseRow get(int r) {
+ int rowSize = size(r);
+ if(rowSize == 0)
+ return new SparseRowScalar();
+
+ //Create sparse row
+ SparseRowVector row = new SparseRowVector(rowSize);
+
+ for(int i = 0; i < _size; i++) {
+ if(_indexes[i] == r) {
+ //Search for index i in pointer array
+ for(int j = 0; j < _ptr.length; j++) {
+ // two possible cases
+ if(_ptr[j] < i && _ptr[j + 1] > i) {
+ row.set(j, _values[i]);
+ }
+ else if(_ptr[j] == i && _ptr[j + 1] >
i) {
+ row.set(j, _values[i]);
+ break;
+ }
+ }
+ }
+ }
+ return row;
+ }
+
+ public SparseRow getCol(int c) {
+ if(isEmptyCol(c))
+ return new SparseRowScalar();
+ int pos = posCol(c);
+ int len = sizeCol(c);
+
+ SparseRowVector col = new SparseRowVector(len);
+ System.arraycopy(_indexes, pos, col.indexes(), 0, len);
+ System.arraycopy(_values, pos, col.values(), 0, len);
+ col.setSize(len);
+ return col;
+ }
+
+ @Override
+ public int posFIndexLTE(int r, int c) {
+ int index = internPosFIndexLTE(r, c);
+ return (index >= 0) ? index - pos(r) : index;
+ }
+
+ public int posFIndexLTECol(int r, int c) {
+ int index = internPosFIndexLTECol(r, c);
+ return (index >= 0) ? index - posCol(c) : index;
+ }
+
+ @Override
+ public int posFIndexGTE(int r, int c) {
+ final int pos = pos(r);
+ final int len = size(r);
+ final int end = pos + len;
+
+ // search for existing col index
+ int index = Arrays.binarySearch(indexes(r), pos, end, c);
+ if(index < 0)
+ // search gt col index (see binary search)
+ index = Math.abs(index + 1);
+
+ return (index < end) ? index - pos : -1;
+ }
+
+ public int posFIndexGTECol(int r, int c) {
+ final int pos = posCol(c);
+ final int len = sizeCol(c);
+ final int end = pos + len;
+
+ // search for existing row index
+ int index = Arrays.binarySearch(_indexes, pos, end, r);
+ if(index < 0)
+ // search gt row index (see binary search)
+ index = Math.abs(index + 1);
+
+ return (index < end) ? index - pos : -1;
+ }
+
+ @Override
+ public int posFIndexGT(int r, int c) {
+ int index = internPosFIndexGT(r, c);
+ return (index >= 0) ? index - pos(r) : index;
+ }
+
+ public int posFIndexGTCol(int r, int c) {
+ int index = internPosFIndexGTCol(r, c);
+ return (index >= 0) ? index - posCol(c) : index;
+ }
+
+ @Override
+ public String toString() {
+ StringBuilder sb = new StringBuilder();
+ sb.append("SparseBlockCSR: clen=");
+ sb.append(numCols());
+ sb.append(", nnz=");
+ sb.append(size());
+ sb.append("\n");
+ final int colDigits = (int)
Math.max(Math.ceil(Math.log10(numCols())), 1);
+ for(int i = 0; i < numCols(); i++) {
+ // append column
+ final int pos = posCol(i);
+ final int len = sizeCol(i);
+ if(pos < pos + len) {
+ sb.append(String.format("%0" + colDigits + "d
", i));
+ for(int j = pos; j < pos + len; j++) {
+ if(_values[j] == (long) _values[j])
+ sb.append(String.format("%" +
colDigits + "d:%d", _indexes[j], (long) _values[j]));
+ else
+ sb.append(String.format("%" +
colDigits + "d:%s", _indexes[j], Double.toString(_values[j])));
+ if(j + 1 < pos + len)
+ sb.append(" ");
+ }
+ sb.append("\n");
+ }
+ }
+
+ return sb.toString();
+ }
+
+ @Override
+ public Iterator<Integer> getNonEmptyRowsIterator(int rl, int ru) {
+ return new NonEmptyRowsIteratorCSC(rl, ru);
+ }
+
+ public class NonEmptyRowsIteratorCSC implements Iterator<Integer> {
+ private int _rpos;
+ private final int _ru;
+ private BitSet _rows = null;
+
+ public NonEmptyRowsIteratorCSC(int rl, int ru) {
+ _rpos = rl;
+ _ru = ru;
+ checkNonEmptyRows();
+ }
+
+ @Override
+ public boolean hasNext() {
+ while(_rpos < _ru && !_rows.get(_rpos))
+ _rpos++;
+ return _rpos < _ru;
+ }
+
+ @Override
+ public Integer next() {
+ return _rpos++;
+ }
+
+ private void checkNonEmptyRows() {
+ int rlen = numRows();
+ _rows = new BitSet(rlen);
+ for(int i = 0; i < _size; i++)
+ _rows.set(_indexes[i]);
+ }
+ }
+
+ public Iterator<Integer> getNonEmptyColumnsIterator(int cl, int cu) {
+ return new SparseBlockCSC.NonEmptyColumnsIteratorCSC(cl, cu);
+ }
+
+ public class NonEmptyColumnsIteratorCSC implements Iterator<Integer> {
+ private int _cpos;
+ private final int _cu;
+
+ public NonEmptyColumnsIteratorCSC(int cl, int cu) {
+ _cpos = cl;
+ _cu = cu;
+ }
+
+ @Override
+ public boolean hasNext() {
+ while(_cpos < _cu && isEmptyCol(_cpos)) {
+ _cpos++;
+ }
+ return _cpos < _cu;
+ }
+
+ @Override
+ public Integer next() {
+ return _cpos++;
+ }
+
+ }
+
+ @SuppressWarnings("unused")
+ private class SparseNonEmptyColumnIterable implements Iterable<Integer>
{
+ private final int _cl; //column lower
+ private final int _cu; //column upper
+
+ protected SparseNonEmptyColumnIterable(int cl, int cu) {
+ _cl = cl;
+ _cu = cu;
+ }
+
+ @Override
+ public Iterator<Integer> iterator() {
+ //use specialized non-empty row iterators of sparse
blocks
+ return getNonEmptyColumnsIterator(_cl, _cu);
+ }
+ }
+
+ ///////////////////////////
+ // private helper methods
+
+ private void inferNumCol(SparseBlock sblock) {
+ int[] indexes = null;
+ if(sblock instanceof SparseBlockMCSR) {
+ SparseRow[] origRows = ((SparseBlockMCSR)
sblock).getRows();
+ for(SparseRow row : origRows) {
+ if(row != null) {
+ indexes = row.indexes();
+ int max =
Arrays.stream(indexes).max().getAsInt();
+ if(max > _clenInferred)
+ _clenInferred = max;
+ }
+ }
+ }
+ else if(sblock instanceof SparseBlockMCSC) {
+ _clenInferred = ((SparseBlockMCSC)
sblock).getCols().length;
+ }
+ else if(sblock instanceof SparseBlockCSC) {
+ _clenInferred = ((SparseBlockCSC) sblock).numCols();
+ }
+ // SparseBlockCSR and SparseBlockDCSR
+ else {
+ indexes = sblock.indexes(0);
+ _clenInferred = Arrays.stream(indexes).max().getAsInt();
+ }
+ _clenInferred += 1;
+ }
+
+ private int newCapacity(int minsize) {
+ //compute new size until minsize reached
+ double tmpCap = Math.max(_values.length, 1);
+ while(tmpCap < minsize) {
+ tmpCap *= (tmpCap <= 1024) ? RESIZE_FACTOR1 :
RESIZE_FACTOR2;
+ }
+ return (int) Math.min(tmpCap, Integer.MAX_VALUE);
+ }
+
+ private void resize() {
+ //resize by at least by 1
+ int newCap = newCapacity(_values.length + 1);
+ resizeCopy(newCap);
+ }
+
+ private void resize(int minsize) {
+ int newCap = newCapacity(minsize);
+ resizeCopy(newCap);
+ }
+
+ private void resizeCopy(int capacity) {
+ //reallocate arrays and copy old values
+ _indexes = Arrays.copyOf(_indexes, capacity);
+ _values = Arrays.copyOf(_values, capacity);
+ }
+
+ private void resizeAndInsert(int ix, int r, double v) {
+ //compute new size
+ int newCap = newCapacity(_values.length + 1);
+
+ int[] oldindexes = _indexes;
+ double[] oldvalues = _values;
+ _indexes = new int[newCap];
+ _values = new double[newCap];
+
+ //copy lhs values to new array
+ System.arraycopy(oldindexes, 0, _indexes, 0, ix);
+ System.arraycopy(oldvalues, 0, _values, 0, ix);
+
+ //copy rhs values to new array
+ System.arraycopy(oldindexes, ix, _indexes, ix + 1, _size - ix);
+ System.arraycopy(oldvalues, ix, _values, ix + 1, _size - ix);
+
+ //insert new value
+ insert(ix, r, v);
+ }
+
+ private void shiftRightAndInsert(int ix, int r, double v) {
+ //overlapping array copy (shift rhs values right by 1)
+ System.arraycopy(_indexes, ix, _indexes, ix + 1, _size - ix);
+ System.arraycopy(_values, ix, _values, ix + 1, _size - ix);
+
+ //insert new value
+ insert(ix, r, v);
+ }
+
+ private void shiftLeftAndDelete(int ix) {
+ //overlapping array copy (shift rhs values left by 1)
+ System.arraycopy(_indexes, ix + 1, _indexes, ix, _size - ix -
1);
+ System.arraycopy(_values, ix + 1, _values, ix, _size - ix - 1);
+ _size--;
+ }
+
+ private void shiftRightByN(int ix, int n) {
+ //overlapping array copy (shift rhs values right by 1)
+ System.arraycopy(_indexes, ix, _indexes, ix + n, _size - ix);
+ System.arraycopy(_values, ix, _values, ix + n, _size - ix);
+ _size += n;
+ }
+
+ @SuppressWarnings("unused")
+ private void shiftLeftByN(int ix, int n) {
+ //overlapping array copy (shift rhs values left by n)
+ System.arraycopy(_indexes, ix, _indexes, ix - n, _size - ix);
+ System.arraycopy(_values, ix, _values, ix - n, _size - ix);
+ _size -= n;
+ }
+
+ private void insert(int ix, int r, double v) {
+ _indexes[ix] = r;
+ _values[ix] = v;
+ _size++;
+ }
+
+ private void incrPtr(int cl) {
+ incrPtr(cl, 1);
+ }
+
+ private void incrPtr(int cl, int cnt) {
+ int clen = numCols();
+ for(int i = cl; i < clen + 1; i++)
+ _ptr[i] += cnt;
+ }
+
+ private void incrRowPtr(int rl, int[] csrPtr) {
+ incrRowPtr(rl, csrPtr, 1);
+ }
+
+ private void incrRowPtr(int rl, int[] csrPtr, int cnt) {
+ for(int i = rl; i < csrPtr.length; i++) {
+ csrPtr[i] += cnt;
+ }
+ }
+
+ private void decrPtr(int cl) {
+ decrPtr(cl, 1);
+ }
+
+ private void decrPtr(int cl, int cnt) {
+ for(int i = cl; i < _ptr.length; i++)
+ _ptr[i] -= cnt;
+ }
+
+ @SuppressWarnings("unused")
+ private int[] numElemPerRow() {
+ int rlen = numRows();
+ int[] rowCount = new int[rlen];
+ for(int i = 0; i < _size; i++) {
+ rowCount[_indexes[i]] += 1;
+ }
+ return rowCount;
+ }
+
+ private int[] rowPointerAll() {
+ int rlen = numRows();
+ int[] csrPtr = new int[rlen + 1];
+ csrPtr[0] = 0;
+ for(int i = 0; i < _size; i++)
+ incrRowPtr(_indexes[i] + 1, csrPtr);
+
+ return csrPtr;
+ }
+
+ private int internPosFIndexLTECol(int r, int c) {
+ int pos = posCol(c);
+ int len = sizeCol(c);
+
+ //search for existing row index in [pos,pos+len)
+ int index = Arrays.binarySearch(_indexes, pos, pos + len, r);
+ if(index >= 0)
+ return (index < pos + len) ? index : -1;
+
+ //search lt row index (see binary search)
+ index = Math.abs(index + 1);
+ return (index - 1 >= pos) ? index - 1 : -1;
+ }
+
+ private int internPosFIndexGTECol(int r, int c) {
+ int pos = posCol(c);
+ int len = sizeCol(c);
+
+ //search for existing row index
+ int index = Arrays.binarySearch(_indexes, pos, pos + len, r);
+ if(index >= 0)
+ return (index < pos + len) ? index : -1;
+
+ //search gt row index (see binary search)
+ index = Math.abs(index + 1);
+ return (index < pos + len) ? index : -1;
+ }
+
+ private int internPosFIndexGTCol(int r, int c) {
+ int pos = posCol(c);
+ int len = sizeCol(c);
+
+ //search for existing row index
+ int index = Arrays.binarySearch(_indexes, pos, pos + len, r);
+ if(index >= 0)
+ return (index + 1 < pos + len) ? index + 1 : -1;
+
+ //search gt row index (see binary search)
+ index = Math.abs(index + 1);
+ return (index < pos + len) ? index : -1;
+ }
+
+ private int internPosFIndexLTE(int r, int c) {
+ int pos = pos(r);
+ int len = size(r);
+
+ //search for existing col index in [pos,pos+len)
+ int index = Arrays.binarySearch(indexes(r), pos, pos + len, c);
+ if(index >= 0)
+ return (index < pos + len) ? index : -1;
+
+ //search lt col index (see binary search)
+ index = Math.abs(index + 1);
+ return (index - 1 >= pos) ? index - 1 : -1;
+ }
+
+ @SuppressWarnings("unused")
+ private int internPosFIndexGTE(int r, int c) {
+ int pos = pos(r);
+ int len = size(r);
+
+ //search for existing col index
+ int index = Arrays.binarySearch(indexes(r), pos, pos + len, c);
+ if(index >= 0)
+ return (index < pos + len) ? index : -1;
+
+ //search gt col index (see binary search)
+ index = Math.abs(index + 1);
+ return (index < pos + len) ? index : -1;
+ }
+
+ private int internPosFIndexGT(int r, int c) {
+ int pos = pos(r);
+ int len = size(r);
+
+ //search for existing col index
+ int index = Arrays.binarySearch(indexes(r), pos, pos + len, c);
+ if(index >= 0)
+ return (index + 1 < pos + len) ? index + 1 : -1;
+
+ //search gt col index (see binary search)
+ index = Math.abs(index + 1);
+ return (index < pos + len) ? index : -1;
+ }
+}
diff --git
a/src/main/java/org/apache/sysds/runtime/data/SparseBlockFactory.java
b/src/main/java/org/apache/sysds/runtime/data/SparseBlockFactory.java
index 106dd36ba9..22dfe5417e 100644
--- a/src/main/java/org/apache/sysds/runtime/data/SparseBlockFactory.java
+++ b/src/main/java/org/apache/sysds/runtime/data/SparseBlockFactory.java
@@ -71,6 +71,7 @@ public abstract class SparseBlockFactory{
case COO: return new SparseBlockCOO(sblock);
case DCSR: return new SparseBlockDCSR(sblock);
case MCSC: return new SparseBlockMCSC(sblock, clen);
+ case CSC: return new SparseBlockCSC(sblock, clen);
default:
throw new RuntimeException("Unexpected sparse
block type: "+type.toString());
}
@@ -90,6 +91,7 @@ public abstract class SparseBlockFactory{
switch( type ) {
case MCSR: return
SparseBlockMCSR.estimateSizeInMemory(nrows, ncols, sparsity);
case CSR: return
SparseBlockCSR.estimateSizeInMemory(nrows, ncols, sparsity);
+ case CSC: return
SparseBlockCSC.estimateSizeInMemory(nrows, ncols, sparsity);
case COO: return
SparseBlockCOO.estimateSizeInMemory(nrows, ncols, sparsity);
case DCSR: return
SparseBlockDCSR.estimateSizeInMemory(nrows, ncols, sparsity);
case MCSC: return
SparseBlockMCSC.estimateSizeInMemory(nrows, ncols, sparsity);
diff --git
a/src/test/java/org/apache/sysds/test/component/sparse/SparseBlockAlignment.java
b/src/test/java/org/apache/sysds/test/component/sparse/SparseBlockAlignment.java
index 41caea2e37..3c2ed30adc 100644
---
a/src/test/java/org/apache/sysds/test/component/sparse/SparseBlockAlignment.java
+++
b/src/test/java/org/apache/sysds/test/component/sparse/SparseBlockAlignment.java
@@ -122,6 +122,21 @@ public class SparseBlockAlignment extends AutomatedTestBase
runSparseBlockScanTest(SparseBlock.Type.MCSC, sparsity3, true);
}
+ @Test
+ public void testSparseBlockCSC1Pos() {
+ runSparseBlockScanTest(SparseBlock.Type.CSC, sparsity1, true);
+ }
+
+ @Test
+ public void testSparseBlockCSC2Pos() {
+ runSparseBlockScanTest(SparseBlock.Type.CSC, sparsity2, true);
+ }
+
+ @Test
+ public void testSparseBlockCSC3Pos() {
+ runSparseBlockScanTest(SparseBlock.Type.CSC, sparsity3, true);
+ }
+
@Test
public void testSparseBlockMCSR1Neg() {
runSparseBlockScanTest(SparseBlock.Type.MCSR, sparsity1, false);
@@ -197,6 +212,21 @@ public class SparseBlockAlignment extends AutomatedTestBase
runSparseBlockScanTest(SparseBlock.Type.MCSC, sparsity3, false);
}
+ @Test
+ public void testSparseBlockCSC1Neg() {
+ runSparseBlockScanTest(SparseBlock.Type.CSC, sparsity1, false);
+ }
+
+ @Test
+ public void testSparseBlockCSC2Neg() {
+ runSparseBlockScanTest(SparseBlock.Type.CSC, sparsity2, false);
+ }
+
+ @Test
+ public void testSparseBlockCSC3Neg() {
+ runSparseBlockScanTest(SparseBlock.Type.CSC, sparsity3, false);
+ }
+
private void runSparseBlockScanTest( SparseBlock.Type btype, double
sparsity, boolean positive)
{
try
diff --git
a/src/test/java/org/apache/sysds/test/component/sparse/SparseBlockAppendSort.java
b/src/test/java/org/apache/sysds/test/component/sparse/SparseBlockAppendSort.java
index 37bdd4fb87..401a19e8bb 100644
---
a/src/test/java/org/apache/sysds/test/component/sparse/SparseBlockAppendSort.java
+++
b/src/test/java/org/apache/sysds/test/component/sparse/SparseBlockAppendSort.java
@@ -19,14 +19,15 @@
package org.apache.sysds.test.component.sparse;
-import org.apache.sysds.runtime.data.SparseBlockDCSR;
import org.junit.Assert;
import org.junit.Test;
import org.apache.sysds.runtime.data.SparseBlock;
import org.apache.sysds.runtime.data.SparseBlockCOO;
+import org.apache.sysds.runtime.data.SparseBlockCSC;
import org.apache.sysds.runtime.data.SparseBlockCSR;
-import org.apache.sysds.runtime.data.SparseBlockMCSR;
+import org.apache.sysds.runtime.data.SparseBlockDCSR;
import org.apache.sysds.runtime.data.SparseBlockMCSC;
+import org.apache.sysds.runtime.data.SparseBlockMCSR;
import org.apache.sysds.runtime.util.LongLongDoubleHashMap;
import org.apache.sysds.runtime.util.LongLongDoubleHashMap.ADoubleEntry;
import org.apache.sysds.test.AutomatedTestBase;
@@ -207,6 +208,36 @@ public class SparseBlockAppendSort extends
AutomatedTestBase
public void testSparseBlockMCSC3Rand() {
runSparseBlockAppendSortTest(SparseBlock.Type.MCSC, sparsity3,
InitType.RAND_SET);
}
+
+ @Test
+ public void testSparseBlockCSC1Seq() {
+ runSparseBlockAppendSortTest(SparseBlock.Type.CSC, sparsity1,
InitType.SEQ_SET);
+ }
+
+ @Test
+ public void testSparseBlockCSC2Seq() {
+ runSparseBlockAppendSortTest(SparseBlock.Type.CSC, sparsity2,
InitType.SEQ_SET);
+ }
+
+ @Test
+ public void testSparseBlockCSC3Seq() {
+ runSparseBlockAppendSortTest(SparseBlock.Type.CSC, sparsity3,
InitType.SEQ_SET);
+ }
+
+ @Test
+ public void testSparseBlockCSC1Rand() {
+ runSparseBlockAppendSortTest(SparseBlock.Type.CSC, sparsity1,
InitType.RAND_SET);
+ }
+
+ @Test
+ public void testSparseBlockCSC2Rand() {
+ runSparseBlockAppendSortTest(SparseBlock.Type.CSC, sparsity2,
InitType.RAND_SET);
+ }
+
+ @Test
+ public void testSparseBlockCSC3Rand() {
+ runSparseBlockAppendSortTest(SparseBlock.Type.CSC, sparsity3,
InitType.RAND_SET);
+ }
private void runSparseBlockAppendSortTest( SparseBlock.Type btype,
double sparsity, InitType itype)
{
@@ -223,6 +254,7 @@ public class SparseBlockAppendSort extends AutomatedTestBase
case COO: sblock = new SparseBlockCOO(rows,
cols); break;
case DCSR: sblock = new SparseBlockDCSR(rows,
cols); break;
case MCSC: sblock = new SparseBlockMCSC(rows,
cols); break;
+ case CSC: sblock = new SparseBlockCSC(rows,
cols); break;
}
if(itype == InitType.SEQ_SET) {
diff --git
a/src/test/java/org/apache/sysds/test/component/sparse/SparseBlockDelete.java
b/src/test/java/org/apache/sysds/test/component/sparse/SparseBlockDelete.java
index 7ac63c0cee..009eb14162 100644
---
a/src/test/java/org/apache/sysds/test/component/sparse/SparseBlockDelete.java
+++
b/src/test/java/org/apache/sysds/test/component/sparse/SparseBlockDelete.java
@@ -126,6 +126,21 @@ public class SparseBlockDelete extends AutomatedTestBase
public void testSparseBlockMCSC3() {
runSparseBlockDeleteTest(SparseBlock.Type.MCSC, sparsity3);
}
+
+ @Test
+ public void testSparseBlockCSC1() {
+ runSparseBlockDeleteTest(SparseBlock.Type.CSC, sparsity1);
+ }
+
+ @Test
+ public void testSparseBlockCSC2() {
+ runSparseBlockDeleteTest(SparseBlock.Type.CSC, sparsity2);
+ }
+
+ @Test
+ public void testSparseBlockCSC3() {
+ runSparseBlockDeleteTest(SparseBlock.Type.CSC, sparsity3);
+ }
private void runSparseBlockDeleteTest( SparseBlock.Type btype, double
sparsity)
{
diff --git
a/src/test/java/org/apache/sysds/test/component/sparse/SparseBlockGetFirstIndex.java
b/src/test/java/org/apache/sysds/test/component/sparse/SparseBlockGetFirstIndex.java
index 5816ba6b26..aee6ffa7c4 100644
---
a/src/test/java/org/apache/sysds/test/component/sparse/SparseBlockGetFirstIndex.java
+++
b/src/test/java/org/apache/sysds/test/component/sparse/SparseBlockGetFirstIndex.java
@@ -19,14 +19,15 @@
package org.apache.sysds.test.component.sparse;
-import org.apache.sysds.runtime.data.SparseBlockDCSR;
import org.junit.Assert;
import org.junit.Test;
import org.apache.sysds.runtime.data.SparseBlock;
import org.apache.sysds.runtime.data.SparseBlockCOO;
+import org.apache.sysds.runtime.data.SparseBlockCSC;
import org.apache.sysds.runtime.data.SparseBlockCSR;
-import org.apache.sysds.runtime.data.SparseBlockMCSR;
+import org.apache.sysds.runtime.data.SparseBlockDCSR;
import org.apache.sysds.runtime.data.SparseBlockMCSC;
+import org.apache.sysds.runtime.data.SparseBlockMCSR;
import org.apache.sysds.runtime.matrix.data.MatrixBlock;
import org.apache.sysds.runtime.util.DataConverter;
import org.apache.sysds.test.AutomatedTestBase;
@@ -281,6 +282,51 @@ public class SparseBlockGetFirstIndex extends
AutomatedTestBase
public void testSparseBlockMCSC3LTE() {
runSparseBlockGetFirstIndexTest(SparseBlock.Type.MCSC,
sparsity3, IndexType.LTE);
}
+
+ @Test
+ public void testSparseBlockCSC1GT() {
+ runSparseBlockGetFirstIndexTest(SparseBlock.Type.CSC,
sparsity1, IndexType.GT);
+ }
+
+ @Test
+ public void testSparseBlockCSC2GT() {
+ runSparseBlockGetFirstIndexTest(SparseBlock.Type.CSC,
sparsity2, IndexType.GT);
+ }
+
+ @Test
+ public void testSparseBlockCSC3GT() {
+ runSparseBlockGetFirstIndexTest(SparseBlock.Type.CSC,
sparsity3, IndexType.GT);
+ }
+
+ @Test
+ public void testSparseBlockCSC1GTE() {
+ runSparseBlockGetFirstIndexTest(SparseBlock.Type.CSC,
sparsity1, IndexType.GTE);
+ }
+
+ @Test
+ public void testSparseBlockCSC2GTE() {
+ runSparseBlockGetFirstIndexTest(SparseBlock.Type.CSC,
sparsity2, IndexType.GTE);
+ }
+
+ @Test
+ public void testSparseBlockCSC3GTE() {
+ runSparseBlockGetFirstIndexTest(SparseBlock.Type.CSC,
sparsity3, IndexType.GTE);
+ }
+
+ @Test
+ public void testSparseBlockCSC1LTE() {
+ runSparseBlockGetFirstIndexTest(SparseBlock.Type.CSC,
sparsity1, IndexType.LTE);
+ }
+
+ @Test
+ public void testSparseBlockCSC2LTE() {
+ runSparseBlockGetFirstIndexTest(SparseBlock.Type.CSC,
sparsity2, IndexType.LTE);
+ }
+
+ @Test
+ public void testSparseBlockCSC3LTE() {
+ runSparseBlockGetFirstIndexTest(SparseBlock.Type.CSC,
sparsity3, IndexType.LTE);
+ }
private void runSparseBlockGetFirstIndexTest( SparseBlock.Type btype,
double sparsity, IndexType itype)
{
@@ -309,6 +355,9 @@ public class SparseBlockGetFirstIndex extends
AutomatedTestBase
case MCSC:
sblock = new SparseBlockMCSC(srtmp,
cols);
break;
+ case CSC:
+ sblock = new SparseBlockCSC(srtmp,
cols);
+ break;
}
//check for correct number of non-zeros
diff --git
a/src/test/java/org/apache/sysds/test/component/sparse/SparseBlockGetSet.java
b/src/test/java/org/apache/sysds/test/component/sparse/SparseBlockGetSet.java
index 2f357d3c8a..a73256d6c4 100644
---
a/src/test/java/org/apache/sysds/test/component/sparse/SparseBlockGetSet.java
+++
b/src/test/java/org/apache/sysds/test/component/sparse/SparseBlockGetSet.java
@@ -19,15 +19,16 @@
package org.apache.sysds.test.component.sparse;
-import org.apache.sysds.runtime.data.SparseBlockDCSR;
-import org.apache.sysds.runtime.data.SparseBlockFactory;
import org.junit.Assert;
import org.junit.Test;
import org.apache.sysds.runtime.data.SparseBlock;
import org.apache.sysds.runtime.data.SparseBlockCOO;
+import org.apache.sysds.runtime.data.SparseBlockCSC;
import org.apache.sysds.runtime.data.SparseBlockCSR;
-import org.apache.sysds.runtime.data.SparseBlockMCSR;
+import org.apache.sysds.runtime.data.SparseBlockDCSR;
+import org.apache.sysds.runtime.data.SparseBlockFactory;
import org.apache.sysds.runtime.data.SparseBlockMCSC;
+import org.apache.sysds.runtime.data.SparseBlockMCSR;
import org.apache.sysds.runtime.matrix.data.MatrixBlock;
import org.apache.sysds.runtime.util.DataConverter;
import org.apache.sysds.runtime.util.LongLongDoubleHashMap;
@@ -278,19 +279,62 @@ public class SparseBlockGetSet extends AutomatedTestBase
}
@Test
- public void testSparseBlockMCSC2Rand() {
+ public void testSparseBlockMCSC2Rand() {
runSparseBlockGetSetTest(SparseBlock.Type.MCSC, sparsity2,
InitType.RAND_SET);
}
@Test
- public void testSparseBlockMCSC3Rand() {
+ public void testSparseBlockMCSC3Rand() {
runSparseBlockGetSetTest(SparseBlock.Type.MCSC, sparsity3,
InitType.RAND_SET);
}
-
- private void runSparseBlockGetSetTest( SparseBlock.Type btype, double
sparsity, InitType itype)
- {
- try
- {
+
+ @Test
+ public void testSparseBlockCSC1Bulk() {
+ runSparseBlockGetSetTest(SparseBlock.Type.CSC, sparsity1,
InitType.BULK);
+ }
+
+ @Test
+ public void testSparseBlockCSC2Bulk() {
+ runSparseBlockGetSetTest(SparseBlock.Type.CSC, sparsity2,
InitType.BULK);
+ }
+
+ @Test
+ public void testSparseBlockCSC3Bulk() {
+ runSparseBlockGetSetTest(SparseBlock.Type.CSC, sparsity3,
InitType.BULK);
+ }
+
+ @Test
+ public void testSparseBlockCSC1Seq() {
+ runSparseBlockGetSetTest(SparseBlock.Type.CSC, sparsity1,
InitType.SEQ_SET);
+ }
+
+ @Test
+ public void testSparseBlockCSC2Seq() {
+ runSparseBlockGetSetTest(SparseBlock.Type.CSC, sparsity2,
InitType.SEQ_SET);
+ }
+
+ @Test
+ public void testSparseBlockCSC3Seq() {
+ runSparseBlockGetSetTest(SparseBlock.Type.CSC, sparsity3,
InitType.SEQ_SET);
+ }
+
+ @Test
+ public void testSparseBlockCSC1Rand() {
+ runSparseBlockGetSetTest(SparseBlock.Type.CSC, sparsity1,
InitType.RAND_SET);
+ }
+
+ @Test
+ public void testSparseBlockCSC2Rand() {
+ runSparseBlockGetSetTest(SparseBlock.Type.CSC, sparsity2,
InitType.RAND_SET);
+ }
+
+ @Test
+ public void testSparseBlockCSC3Rand() {
+ runSparseBlockGetSetTest(SparseBlock.Type.CSC, sparsity3,
InitType.RAND_SET);
+ }
+
+ private void runSparseBlockGetSetTest(SparseBlock.Type btype, double
sparsity, InitType itype) {
+ try {
//data generation
double[][] A = getRandomMatrix(rows, cols, -10, 10,
sparsity, 7654321);
@@ -303,11 +347,24 @@ public class SparseBlockGetSet extends AutomatedTestBase
}
else if( itype == InitType.SEQ_SET || itype ==
InitType.RAND_SET ) {
switch( btype ) {
- case MCSR: sblock = new
SparseBlockMCSR(rows, cols); break;
- case CSR: sblock = new
SparseBlockCSR(rows, cols); break;
- case COO: sblock = new
SparseBlockCOO(rows, cols); break;
- case DCSR: sblock = new
SparseBlockDCSR(rows, cols); break;
- case MCSC: sblock = new
SparseBlockMCSC(rows, cols); break;
+ case MCSR:
+ sblock = new
SparseBlockMCSR(rows, cols);
+ break;
+ case CSR:
+ sblock = new
SparseBlockCSR(rows, cols);
+ break;
+ case COO:
+ sblock = new
SparseBlockCOO(rows, cols);
+ break;
+ case DCSR:
+ sblock = new
SparseBlockDCSR(rows, cols);
+ break;
+ case MCSC:
+ sblock = new
SparseBlockMCSC(rows, cols);
+ break;
+ case CSC:
+ sblock = new
SparseBlockCSC(rows, cols);
+ break;
}
if(itype == InitType.SEQ_SET) {
diff --git
a/src/test/java/org/apache/sysds/test/component/sparse/SparseBlockIndexRange.java
b/src/test/java/org/apache/sysds/test/component/sparse/SparseBlockIndexRange.java
index d51f9d1f6d..2125be294f 100644
---
a/src/test/java/org/apache/sysds/test/component/sparse/SparseBlockIndexRange.java
+++
b/src/test/java/org/apache/sysds/test/component/sparse/SparseBlockIndexRange.java
@@ -206,6 +206,36 @@ public class SparseBlockIndexRange extends
AutomatedTestBase
public void testSparseBlockMCSC3Insert() {
runSparseBlockIndexRangeTest(SparseBlock.Type.MCSC, sparsity3,
UpdateType.INSERT);
}
+
+ @Test
+ public void testSparseBlockCSC1Delete() {
+ runSparseBlockIndexRangeTest(SparseBlock.Type.CSC, sparsity1,
UpdateType.DELETE);
+ }
+
+ @Test
+ public void testSparseBlockCSC2Delete() {
+ runSparseBlockIndexRangeTest(SparseBlock.Type.CSC, sparsity2,
UpdateType.DELETE);
+ }
+
+ @Test
+ public void testSparseBlockCSC3Delete() {
+ runSparseBlockIndexRangeTest(SparseBlock.Type.CSC, sparsity3,
UpdateType.DELETE);
+ }
+
+ @Test
+ public void testSparseBlockCSC1Insert() {
+ runSparseBlockIndexRangeTest(SparseBlock.Type.CSC, sparsity1,
UpdateType.INSERT);
+ }
+
+ @Test
+ public void testSparseBlockCSC2Insert() {
+ runSparseBlockIndexRangeTest(SparseBlock.Type.CSC, sparsity2,
UpdateType.INSERT);
+ }
+
+ @Test
+ public void testSparseBlockCSC3Insert() {
+ runSparseBlockIndexRangeTest(SparseBlock.Type.CSC, sparsity3,
UpdateType.INSERT);
+ }
private void runSparseBlockIndexRangeTest( SparseBlock.Type btype,
double sparsity, UpdateType utype)
{
@@ -224,6 +254,7 @@ public class SparseBlockIndexRange extends AutomatedTestBase
case COO: sblock = new SparseBlockCOO(srtmp);
break;
case DCSR: sblock = new SparseBlockDCSR(srtmp);
break;
case MCSC: sblock = new SparseBlockMCSC(srtmp,
cols); break;
+ case CSC: sblock = new SparseBlockCSC(srtmp,
cols); break;
}
//delete range per row via set
diff --git
a/src/test/java/org/apache/sysds/test/component/sparse/SparseBlockIterator.java
b/src/test/java/org/apache/sysds/test/component/sparse/SparseBlockIterator.java
index 736f981025..57cee617fb 100644
---
a/src/test/java/org/apache/sysds/test/component/sparse/SparseBlockIterator.java
+++
b/src/test/java/org/apache/sysds/test/component/sparse/SparseBlockIterator.java
@@ -202,6 +202,38 @@ public class SparseBlockIterator extends AutomatedTestBase
{
runSparseBlockIteratorTest(SparseBlock.Type.MCSC, sparsity3,
true);
}
+ @Test
+ public void testSparseBlockCSC1Full() {
+ runSparseBlockIteratorTest(SparseBlock.Type.CSC, sparsity1,
false);
+ }
+
+ @Test
+ public void testSparseBlockCSC2Full() {
+ runSparseBlockIteratorTest(SparseBlock.Type.CSC, sparsity2,
false);
+ }
+
+ @Test
+ public void testSparseBlockCSC3Full() {
+ runSparseBlockIteratorTest(SparseBlock.Type.CSC, sparsity3,
false);
+ }
+
+ @Test
+ public void testSparseBlockCSC1Partial() {
+ runSparseBlockIteratorTest(SparseBlock.Type.CSC, sparsity1,
true);
+ }
+
+ @Test
+ public void testSparseBlockCSC2Partial() {
+ runSparseBlockIteratorTest(SparseBlock.Type.CSC, sparsity2,
true);
+ }
+
+ @Test
+ public void testSparseBlockCSC3Partial() {
+ runSparseBlockIteratorTest(SparseBlock.Type.CSC, sparsity3,
true);
+ }
+
+
+
private void runSparseBlockIteratorTest(SparseBlock.Type btype, double
sparsity, boolean partial) {
try {
//data generation
diff --git
a/src/test/java/org/apache/sysds/test/component/sparse/SparseBlockMemEstimate.java
b/src/test/java/org/apache/sysds/test/component/sparse/SparseBlockMemEstimate.java
index 1c0c2aa7c5..8269e1b0e0 100644
---
a/src/test/java/org/apache/sysds/test/component/sparse/SparseBlockMemEstimate.java
+++
b/src/test/java/org/apache/sysds/test/component/sparse/SparseBlockMemEstimate.java
@@ -59,6 +59,7 @@ public class SparseBlockMemEstimate extends AutomatedTestBase
double memMCSC =
SparseBlockFactory.estimateSizeSparseInMemory(SparseBlock.Type.MCSC, rows,
cols, sparsity);
double memMCSR =
SparseBlockFactory.estimateSizeSparseInMemory(SparseBlock.Type.MCSR, rows,
cols, sparsity);
double memCSR =
SparseBlockFactory.estimateSizeSparseInMemory(SparseBlock.Type.CSR, rows, cols,
sparsity);
+ double memCSC =
SparseBlockFactory.estimateSizeSparseInMemory(SparseBlock.Type.CSC, rows, cols,
sparsity);
double memCOO =
SparseBlockFactory.estimateSizeSparseInMemory(SparseBlock.Type.COO, rows, cols,
sparsity);
double memDCSR =
SparseBlockFactory.estimateSizeSparseInMemory(SparseBlock.Type.DCSR, rows,
cols, sparsity);
double memDense = MatrixBlock.estimateSizeDenseInMemory(rows,
cols);
@@ -70,6 +71,8 @@ public class SparseBlockMemEstimate extends AutomatedTestBase
Assert.fail("SparseBlockMCSR memory estimate <= 0.");
if( memCSR <= 0 )
Assert.fail("SparseBlockCSR memory estimate <= 0.");
+ if( memCSC <= 0 )
+ Assert.fail("SparseBlockCSC memory estimate <= 0.");
if( memCOO <= 0 )
Assert.fail("SparseBlockCOO memory estimate <= 0.");
if( memDCSR <= 0 )
diff --git
a/src/test/java/org/apache/sysds/test/component/sparse/SparseBlockMerge.java
b/src/test/java/org/apache/sysds/test/component/sparse/SparseBlockMerge.java
index 7c061eaf27..acba9ac938 100644
--- a/src/test/java/org/apache/sysds/test/component/sparse/SparseBlockMerge.java
+++ b/src/test/java/org/apache/sysds/test/component/sparse/SparseBlockMerge.java
@@ -134,22 +134,42 @@ public class SparseBlockMerge extends AutomatedTestBase
}
@Test
- public void testMergeMCSR_MCSC_2() {
+ public void testMergeMCSR_MCSC_2() {
runSparseBlockMergeTest(SparseBlock.Type.MCSR,
SparseBlock.Type.MCSC, sparsity2);
}
@Test
- public void testMergeMCSR_MCSC_3() {
+ public void testMergeMCSR_MCSC_3() {
runSparseBlockMergeTest(SparseBlock.Type.MCSR,
SparseBlock.Type.MCSC, sparsity3);
}
-
+
+ @Test
+ public void testMergeMCSR_CSC_0() {
+ runSparseBlockMergeTest(SparseBlock.Type.MCSR,
SparseBlock.Type.CSC, sparsity0);
+ }
+
+ @Test
+ public void testMergeMCSR_CSC_1() {
+ runSparseBlockMergeTest(SparseBlock.Type.MCSR,
SparseBlock.Type.CSC, sparsity1);
+ }
+
+ @Test
+ public void testMergeMCSR_CSC_2() {
+ runSparseBlockMergeTest(SparseBlock.Type.MCSR,
SparseBlock.Type.CSC, sparsity2);
+ }
+
+ @Test
+ public void testMergeMCSR_CSC_3() {
+ runSparseBlockMergeTest(SparseBlock.Type.MCSR,
SparseBlock.Type.CSC, sparsity3);
+ }
+
@Test
- public void testMergeCSR_CSR_0() {
+ public void testMergeCSR_CSR_0() {
runSparseBlockMergeTest(SparseBlock.Type.CSR,
SparseBlock.Type.CSR, sparsity0);
}
-
+
@Test
- public void testMergeCSR_CSR_1() {
+ public void testMergeCSR_CSR_1() {
runSparseBlockMergeTest(SparseBlock.Type.CSR,
SparseBlock.Type.CSR, sparsity1);
}
@@ -234,22 +254,42 @@ public class SparseBlockMerge extends AutomatedTestBase
}
@Test
- public void testMergeCSR_MCSC_2() {
+ public void testMergeCSR_MCSC_2() {
runSparseBlockMergeTest(SparseBlock.Type.CSR,
SparseBlock.Type.MCSC, sparsity2);
}
@Test
- public void testMergeCSR_MCSC_3() {
+ public void testMergeCSR_MCSC_3() {
runSparseBlockMergeTest(SparseBlock.Type.CSR,
SparseBlock.Type.MCSC, sparsity3);
}
-
+
@Test
- public void testMergeCOO_COO_0() {
+ public void testMergeCSR_CSC_0() {
+ runSparseBlockMergeTest(SparseBlock.Type.CSR,
SparseBlock.Type.CSC, sparsity0);
+ }
+
+ @Test
+ public void testMergeCSR_CSC_1() {
+ runSparseBlockMergeTest(SparseBlock.Type.CSR,
SparseBlock.Type.CSC, sparsity1);
+ }
+
+ @Test
+ public void testMergeCSR_CSC_2() {
+ runSparseBlockMergeTest(SparseBlock.Type.CSR,
SparseBlock.Type.CSC, sparsity2);
+ }
+
+ @Test
+ public void testMergeCSR_CSC_3() {
+ runSparseBlockMergeTest(SparseBlock.Type.CSR,
SparseBlock.Type.CSC, sparsity3);
+ }
+
+ @Test
+ public void testMergeCOO_COO_0() {
runSparseBlockMergeTest(SparseBlock.Type.COO,
SparseBlock.Type.COO, sparsity0);
}
-
+
@Test
- public void testMergeCOO_COO_1() {
+ public void testMergeCOO_COO_1() {
runSparseBlockMergeTest(SparseBlock.Type.COO,
SparseBlock.Type.COO, sparsity1);
}
@@ -334,22 +374,42 @@ public class SparseBlockMerge extends AutomatedTestBase
}
@Test
- public void testMergeCOO_MCSC_2() {
+ public void testMergeCOO_MCSC_2() {
runSparseBlockMergeTest(SparseBlock.Type.COO,
SparseBlock.Type.MCSC, sparsity2);
}
@Test
- public void testMergeCOO_MCSC_3() {
+ public void testMergeCOO_MCSC_3() {
runSparseBlockMergeTest(SparseBlock.Type.COO,
SparseBlock.Type.MCSC, sparsity3);
}
@Test
- public void testMergeDCSR_DCSR_0() {
+ public void testMergeCOO_CSC_0() {
+ runSparseBlockMergeTest(SparseBlock.Type.COO,
SparseBlock.Type.CSC, sparsity0);
+ }
+
+ @Test
+ public void testMergeCOO_CSC_1() {
+ runSparseBlockMergeTest(SparseBlock.Type.COO,
SparseBlock.Type.CSC, sparsity1);
+ }
+
+ @Test
+ public void testMergeCOO_CSC_2() {
+ runSparseBlockMergeTest(SparseBlock.Type.COO,
SparseBlock.Type.CSC, sparsity2);
+ }
+
+ @Test
+ public void testMergeCOO_CSC_3() {
+ runSparseBlockMergeTest(SparseBlock.Type.COO,
SparseBlock.Type.CSC, sparsity3);
+ }
+
+ @Test
+ public void testMergeDCSR_DCSR_0() {
runSparseBlockMergeTest(SparseBlock.Type.DCSR,
SparseBlock.Type.DCSR, sparsity0);
}
@Test
- public void testMergeDCSR_DCSR_1() {
+ public void testMergeDCSR_DCSR_1() {
runSparseBlockMergeTest(SparseBlock.Type.DCSR,
SparseBlock.Type.DCSR, sparsity1);
}
@@ -434,22 +494,42 @@ public class SparseBlockMerge extends AutomatedTestBase
}
@Test
- public void testMergeDCSR_MCSC_2() {
+ public void testMergeDCSR_MCSC_2() {
runSparseBlockMergeTest(SparseBlock.Type.DCSR,
SparseBlock.Type.MCSC, sparsity2);
}
@Test
- public void testMergeDCSR_MCSC_3() {
+ public void testMergeDCSR_MCSC_3() {
runSparseBlockMergeTest(SparseBlock.Type.DCSR,
SparseBlock.Type.MCSC, sparsity3);
}
@Test
- public void testMergeMCSC_MCSC_0() {
+ public void testMergeDCSR_CSC_0() {
+ runSparseBlockMergeTest(SparseBlock.Type.DCSR,
SparseBlock.Type.CSC, sparsity0);
+ }
+
+ @Test
+ public void testMergeDCSR_CSC_1() {
+ runSparseBlockMergeTest(SparseBlock.Type.DCSR,
SparseBlock.Type.CSC, sparsity1);
+ }
+
+ @Test
+ public void testMergeDCSR_CSC_2() {
+ runSparseBlockMergeTest(SparseBlock.Type.DCSR,
SparseBlock.Type.CSC, sparsity2);
+ }
+
+ @Test
+ public void testMergeDCSR_CSC_3() {
+ runSparseBlockMergeTest(SparseBlock.Type.DCSR,
SparseBlock.Type.CSC, sparsity3);
+ }
+
+ @Test
+ public void testMergeMCSC_MCSC_0() {
runSparseBlockMergeTest(SparseBlock.Type.MCSC,
SparseBlock.Type.MCSC, sparsity0);
}
@Test
- public void testMergeMCSC_MCSC_1() {
+ public void testMergeMCSC_MCSC_1() {
runSparseBlockMergeTest(SparseBlock.Type.MCSC,
SparseBlock.Type.MCSC, sparsity1);
}
@@ -494,43 +574,179 @@ public class SparseBlockMerge extends AutomatedTestBase
}
@Test
- public void testMergeMCSC_MCSR_2() {
+ public void testMergeMCSC_MCSR_2() {
runSparseBlockMergeTest(SparseBlock.Type.MCSC,
SparseBlock.Type.MCSR, sparsity2);
}
@Test
- public void testMergeMCSC_MCSR_3() {
+ public void testMergeMCSC_MCSR_3() {
runSparseBlockMergeTest(SparseBlock.Type.MCSC,
SparseBlock.Type.MCSR, sparsity3);
}
@Test
- public void testMergeMCSC_COO_0() {
+ public void testMergeMCSC_DCSR_0() {
+ runSparseBlockMergeTest(SparseBlock.Type.MCSC,
SparseBlock.Type.DCSR, sparsity0);
+ }
+
+ @Test
+ public void testMergeMCSC_DCSR_1() {
+ runSparseBlockMergeTest(SparseBlock.Type.MCSC,
SparseBlock.Type.DCSR, sparsity1);
+ }
+
+ @Test
+ public void testMergeMCSC_DCSR_2() {
+ runSparseBlockMergeTest(SparseBlock.Type.MCSC,
SparseBlock.Type.DCSR, sparsity2);
+ }
+
+ @Test
+ public void testMergeMCSC_DCSR_3() {
+ runSparseBlockMergeTest(SparseBlock.Type.MCSC,
SparseBlock.Type.DCSR, sparsity3);
+ }
+
+ @Test
+ public void testMergeMCSC_COO_0() {
runSparseBlockMergeTest(SparseBlock.Type.MCSC,
SparseBlock.Type.COO, sparsity0);
}
@Test
- public void testMergeMCSC_COO_1() {
+ public void testMergeMCSC_COO_1() {
runSparseBlockMergeTest(SparseBlock.Type.MCSC,
SparseBlock.Type.COO, sparsity1);
}
@Test
- public void testMergeMCSC_COO_2() {
+ public void testMergeMCSC_COO_2() {
runSparseBlockMergeTest(SparseBlock.Type.MCSC,
SparseBlock.Type.COO, sparsity2);
}
@Test
- public void testMergeMCSC_COO_3() {
+ public void testMergeMCSC_COO_3() {
runSparseBlockMergeTest(SparseBlock.Type.MCSC,
SparseBlock.Type.COO, sparsity3);
}
+ @Test
+ public void testMergeMCSC_CSC_0() {
+ runSparseBlockMergeTest(SparseBlock.Type.MCSC,
SparseBlock.Type.CSC, sparsity0);
+ }
+
+ @Test
+ public void testMergeMCSC_CSC_1() {
+ runSparseBlockMergeTest(SparseBlock.Type.MCSC,
SparseBlock.Type.CSC, sparsity1);
+ }
+
+ @Test
+ public void testMergeMCSC_CSC_2() {
+ runSparseBlockMergeTest(SparseBlock.Type.MCSC,
SparseBlock.Type.CSC, sparsity2);
+ }
+
+ @Test
+ public void testMergeMCSC_CSC_3() {
+ runSparseBlockMergeTest(SparseBlock.Type.MCSC,
SparseBlock.Type.CSC, sparsity3);
+ }
+
+ @Test
+ public void testMergeCSC_CSC_0() {
+ runSparseBlockMergeTest(SparseBlock.Type.CSC,
SparseBlock.Type.CSC, sparsity0);
+ }
+ @Test
+ public void testMergeCSC_CSC_1() {
+ runSparseBlockMergeTest(SparseBlock.Type.CSC,
SparseBlock.Type.CSC, sparsity1);
+ }
+
+ @Test
+ public void testMergeCSC_CSC_2() {
+ runSparseBlockMergeTest(SparseBlock.Type.CSC,
SparseBlock.Type.CSC, sparsity2);
+ }
+
+ @Test
+ public void testMergeCSC_CSC_3() {
+ runSparseBlockMergeTest(SparseBlock.Type.CSC,
SparseBlock.Type.CSC, sparsity3);
+ }
+
+ @Test
+ public void testMergeCSC_MCSC_0() {
+ runSparseBlockMergeTest(SparseBlock.Type.CSC,
SparseBlock.Type.MCSC, sparsity0);
+ }
+
+ @Test
+ public void testMergeCSC_MCSC_1() {
+ runSparseBlockMergeTest(SparseBlock.Type.CSC,
SparseBlock.Type.MCSC, sparsity1);
+ }
+
+ @Test
+ public void testMergeCSC_MCSC_2() {
+ runSparseBlockMergeTest(SparseBlock.Type.CSC,
SparseBlock.Type.MCSC, sparsity2);
+ }
+
+ @Test
+ public void testMergeCSC_MCSC_3() {
+ runSparseBlockMergeTest(SparseBlock.Type.CSC,
SparseBlock.Type.MCSC, sparsity3);
+ }
+
+ @Test
+ public void testMergeCSC_CSR_0() {
+ runSparseBlockMergeTest(SparseBlock.Type.CSC,
SparseBlock.Type.CSR, sparsity0);
+ }
+
+ @Test
+ public void testMergeCSC_CSR_1() {
+ runSparseBlockMergeTest(SparseBlock.Type.CSC,
SparseBlock.Type.CSR, sparsity1);
+ }
+
+ @Test
+ public void testMergeCSC_CSR_2() {
+ runSparseBlockMergeTest(SparseBlock.Type.CSC,
SparseBlock.Type.CSR, sparsity2);
+ }
+
+ @Test
+ public void testMergeCSC_CSR_3() {
+ runSparseBlockMergeTest(SparseBlock.Type.CSC,
SparseBlock.Type.CSR, sparsity3);
+ }
+
+ @Test
+ public void testMergeCSC_MCSR_0() {
+ runSparseBlockMergeTest(SparseBlock.Type.CSC,
SparseBlock.Type.MCSR, sparsity0);
+ }
+
+ @Test
+ public void testMergeCSC_MCSR_1() {
+ runSparseBlockMergeTest(SparseBlock.Type.CSC,
SparseBlock.Type.MCSR, sparsity1);
+ }
+
+ @Test
+ public void testMergeCSC_MCSR_2() {
+ runSparseBlockMergeTest(SparseBlock.Type.CSC,
SparseBlock.Type.MCSR, sparsity2);
+ }
+
+ @Test
+ public void testMergeCSC_MCSR_3() {
+ runSparseBlockMergeTest(SparseBlock.Type.CSC,
SparseBlock.Type.MCSR, sparsity3);
+ }
+
+ @Test
+ public void testMergeCSC_COO_0() {
+ runSparseBlockMergeTest(SparseBlock.Type.CSC,
SparseBlock.Type.COO, sparsity0);
+ }
+
+ @Test
+ public void testMergeCSC_COO_1() {
+ runSparseBlockMergeTest(SparseBlock.Type.CSC,
SparseBlock.Type.COO, sparsity1);
+ }
+
+ @Test
+ public void testMergeCSC_COO_2() {
+ runSparseBlockMergeTest(SparseBlock.Type.CSC,
SparseBlock.Type.COO, sparsity2);
+ }
+
+ @Test
+ public void testMergeCSC_COO_3() {
+ runSparseBlockMergeTest(SparseBlock.Type.CSC,
SparseBlock.Type.COO, sparsity3);
+ }
- private void runSparseBlockMergeTest( SparseBlock.Type btype1,
SparseBlock.Type btype2, double sparsity)
- {
- try
- {
+ private void runSparseBlockMergeTest(SparseBlock.Type btype1,
SparseBlock.Type btype2, double sparsity) {
+ try {
//data generation
- double[][] A = getRandomMatrix(rows, cols, -10, 10,
sparsity, 1234);
+ double[][] A = getRandomMatrix(rows, cols, -10, 10,
sparsity, 1234);
double[][] B1 = new double[A.length][];
double[][] B2 = new double[A.length][];
for(int i=0; i<A.length; i++) {
diff --git
a/src/test/java/org/apache/sysds/test/component/sparse/SparseBlockScan.java
b/src/test/java/org/apache/sysds/test/component/sparse/SparseBlockScan.java
index 8163b49a6e..6729580209 100644
--- a/src/test/java/org/apache/sysds/test/component/sparse/SparseBlockScan.java
+++ b/src/test/java/org/apache/sysds/test/component/sparse/SparseBlockScan.java
@@ -120,6 +120,21 @@ public class SparseBlockScan extends AutomatedTestBase
public void testSparseBlockMCSC3Full() {
runSparseBlockScanTest(SparseBlock.Type.MCSC, sparsity3);
}
+
+ @Test
+ public void testSparseBlockCSC1Full() {
+ runSparseBlockScanTest(SparseBlock.Type.CSC, sparsity1);
+ }
+
+ @Test
+ public void testSparseBlockCSC2Full() {
+ runSparseBlockScanTest(SparseBlock.Type.CSC, sparsity2);
+ }
+
+ @Test
+ public void testSparseBlockCSC3Full() {
+ runSparseBlockScanTest(SparseBlock.Type.CSC, sparsity3);
+ }
private void runSparseBlockScanTest( SparseBlock.Type btype, double
sparsity)
{
@@ -138,6 +153,7 @@ public class SparseBlockScan extends AutomatedTestBase
case COO: sblock = new SparseBlockCOO(srtmp);
break;
case DCSR: sblock = new SparseBlockDCSR(srtmp);
break;
case MCSC: sblock = new SparseBlockMCSC(srtmp);
break;
+ case CSC: sblock = new SparseBlockCSC(srtmp);
break;
}
//check for correct number of non-zeros
diff --git
a/src/test/java/org/apache/sysds/test/component/sparse/SparseBlockSize.java
b/src/test/java/org/apache/sysds/test/component/sparse/SparseBlockSize.java
index edc84098ca..7059dfe333 100644
--- a/src/test/java/org/apache/sysds/test/component/sparse/SparseBlockSize.java
+++ b/src/test/java/org/apache/sysds/test/component/sparse/SparseBlockSize.java
@@ -125,6 +125,21 @@ public class SparseBlockSize extends AutomatedTestBase
public void testSparseBlockMCSC3(){
runSparseBlockSizeTest(SparseBlock.Type.MCSC, _sparsity3);
}
+
+ @Test
+ public void testSparseBlockCSC1(){
+ runSparseBlockSizeTest(SparseBlock.Type.CSC, _sparsity1);
+ }
+
+ @Test
+ public void testSparseBlockCSC2(){
+ runSparseBlockSizeTest(SparseBlock.Type.CSC, _sparsity2);
+ }
+
+ @Test
+ public void testSparseBlockCSC3(){
+ runSparseBlockSizeTest(SparseBlock.Type.CSC, _sparsity3);
+ }
@Test
public void testSparseBlockMCSRFixed1(){
@@ -143,6 +158,12 @@ public class SparseBlockSize extends AutomatedTestBase
double[][] A = getFixedData1();
runSparseBlockSizeTest(A, 0, 4, 0, 6, SparseBlock.Type.COO);
}
+
+ @Test
+ public void testSparseBlockCSCFixed1(){
+ double[][] A = getFixedData1();
+ runSparseBlockSizeTest(A, 0, 4, 0, 6, SparseBlock.Type.CSC);
+ }
@Test
public void testSparseBlockMCSRFixed2(){
@@ -155,6 +176,12 @@ public class SparseBlockSize extends AutomatedTestBase
double[][] A = getFixedData2();
runSparseBlockSizeTest(A, 0, 4, 2, 4, SparseBlock.Type.CSR);
}
+
+ @Test
+ public void testSparseBlockCSCFixed2(){
+ double[][] A = getFixedData2();
+ runSparseBlockSizeTest(A, 0, 4, 2, 4, SparseBlock.Type.CSC);
+ }
@Test
public void testSparseBlockCOOFixed2(){
@@ -173,6 +200,12 @@ public class SparseBlockSize extends AutomatedTestBase
double[][] A = getFixedData3();
runSparseBlockSizeTest(A, 0, 4, 3, 3, SparseBlock.Type.CSR);
}
+
+ @Test
+ public void testSparseBlockCSCFixed3(){
+ double[][] A = getFixedData3();
+ runSparseBlockSizeTest(A, 0, 4, 3, 3, SparseBlock.Type.CSC);
+ }
@Test
public void testSparseBlockCOOFixed3(){
@@ -204,6 +237,7 @@ public class SparseBlockSize extends AutomatedTestBase
case COO: sblock = new SparseBlockCOO(srtmp);
break;
case DCSR: sblock = new SparseBlockDCSR(srtmp);
break;
case MCSC: sblock = new SparseBlockMCSC(srtmp,
cols); break;
+ case CSC: sblock = new SparseBlockCSC(srtmp,
cols); break;
}
//prepare summary statistics nnz
