About CVS, CRS and CCS
When I discussed about compressed matrices, I mentioned two common compressed matrix formats, CRS and CCS, and described a third one I called CVS. These compressed matrices are supported in Mendz.Library.Matrices.
In Mendz.Library.Matrices, the CVS, CRS and CCS formats are implemented as tuples of 4 values, with the fourth being the (int rows, int columns) tuple size of the matrix. The CVS, CRS and CCS classes implement the Deconstruct() method, which allows their instances to be deconstructed in to their respective tuple representations.
In Mendz.Library.Matrices, the CVS, CRS and CCS formats are implemented as tuples of 4 values, with the fourth being the (int rows, int columns) tuple size of the matrix. The CVS, CRS and CCS classes implement the Deconstruct() method, which allows their instances to be deconstructed in to their respective tuple representations.
Compressed Value Storage (CVS)
Lossless compression exploits redundancy to compress data. The compressed value storage (CVS) applies basic lossless compression of the matrix, such that each distinct value is aligned with its list of linear indexes in the matrix.- A - is a list[NDNZ] of distinct non-zero values in the matrix.
- LA - is a list[NDNZ] such that LAi is Ai's list[Ng] of linear indexes in the matrix.
- L - is an indicator of the matrix linear indexing mode: 0 for row-major order, and 1 for column-major order.
- S - is the (int rows, int columns) tuple size of the matrix.
(
List<int> value,
List<List<int>> linearIndex,
MatrixLinearIndexMode linearIndexMode,
(int rows, int columns) size
)
Below is the full code of the Mendz.Library.Matrices.CVS class.
CVS.cs
using System;
using System.Collections.Generic;
using System.Threading.Tasks;
namespace Mendz.Library.Matrices
{
public sealed class CVS<T>
{
public List<T> Value { get; private set; } = new List<T>();
public List<List<int>> LinearIndex { get; private set; }
= new List<List<int>>();
public MatrixLinearIndexMode LinearIndexMode { get; private set; }
= MatrixLinearIndexMode.RowMajorOrder;
public (int rows, int columns) Size { get; private set; }
public CVS((int rows, int columns) size)
: this(MatrixLinearIndexMode.RowMajorOrder, size)
{
}
public CVS(MatrixLinearIndexMode linearIndexMode, (int rows, int columns) size)
{
LinearIndexMode = linearIndexMode;
Size = size;
}
public CVS(List<T> value, List<List<int>> linearIndex,
MatrixLinearIndexMode linearIndexMode, (int rows, int columns) size)
{
Value = value;
LinearIndex = linearIndex;
LinearIndexMode = linearIndexMode;
Size = size;
}
public void Compress<K>(IDOKSparseMatrix<K, T> sparseMatrix)
{
List<T> value = new List<T>();
List<List<int>> linearIndex = new List<List<int>>();
Size = sparseMatrix.Size;
if (typeof(K) == typeof(int))
{
LinearIndexMode = sparseMatrix.LinearIndexMode;
}
foreach (var item in sparseMatrix.Matrix)
{
T v = item.Value;
if (!value.Contains(v))
{
value.Add(v);
}
int i = value.IndexOf(v);
int count = linearIndex.Count;
if (count == 0 || i > count - 1)
{
linearIndex.Add(new List<int>());
}
dynamic key = item.Key;
var k = key;
if (typeof(K) == typeof(int))
{
linearIndex[i].Add(k);
}
else
{
linearIndex[i]
.Add(MatrixCoordinates.ToLinearIndex(Size, k, LinearIndexMode));
}
}
foreach (var lis in linearIndex)
{
lis.Sort();
}
Value = value;
LinearIndex = linearIndex;
}
public void Decompress<K>(IDOKSparseMatrix<K, T> sparseMatrix)
{
if (!sparseMatrix.Size.Equals(Size))
{
throw new InvalidOperationException("Sparse matrix size is invalid.");
}
if (sparseMatrix.LinearIndexMode != LinearIndexMode)
{
throw new InvalidOperationException(
"Sparse matrix linear index mode is invalid.");
}
Action<T, int> decompress = (v, li) =>
{
dynamic key;
if (typeof(K) == typeof(int))
{
key = li;
}
else
{
key = MatrixCoordinates.ToCoordinates(Size, li, LinearIndexMode);
}
sparseMatrix.SetEntry(key, v);
};
if (sparseMatrix.IsConcurrent)
{
Parallel.For(0, Value.Count, (i) =>
{
T v = Value[i];
Parallel.ForEach(LinearIndex[i], (li) =>
{
decompress(v, li);
});
});
}
else
{
for (int i = 0; i < Value.Count; i++)
{
T v = Value[i];
foreach (var li in LinearIndex[i])
{
decompress(v, li);
}
}
}
}
public void Transpose()
{
(int rows, int columns) size = (Size.columns, Size.rows);
Parallel.ForEach(LinearIndex, (lis) =>
{
for (int i = 0; i < lis.Count; i++)
{
lis[i] = MatrixCoordinates.TransposeLinearIndex(
Size, lis[i], LinearIndexMode).linearIndex;
}
lis.Sort();
});
Size = size;
}
public void SetLinearIndexMode(MatrixLinearIndexMode linearIndexMode)
{
if (linearIndexMode != LinearIndexMode)
{
Parallel.ForEach(LinearIndex, (lis) =>
{
for (int i = 0; i < lis.Count; i++)
{
lis[i] = MatrixCoordinates.ToLinearIndex(Size,
MatrixCoordinates.ToCoordinates(
Size, lis[i], LinearIndexMode),
linearIndexMode);
}
lis.Sort();
});
LinearIndexMode = linearIndexMode;
}
public void Deconstruct(out List<T> value,
out List<List<int>> linearIndex,
out MatrixLinearIndexMode linearIndexMode,
out (int rows, int columns) size)
{
value = Value;
linearIndex = LinearIndex;
linearIndexMode = LinearIndexMode;
size = Size;
}
}
}
This code defines a CVS. A couple of unique features are the Transpose() and SetLinearIndexMode() methods.
Compressed Row Storage (CRS)
The compressed row storage (CRS) format is one of the common compressed matrix formats. It is also known as compressed sparse row (CSR) or the Yale format. It compresses the row indexes by storing the extents of rows instead.- A - is a list[NNZ] of non-zero values in the matrix.
- IA - is a list[Ni + 1] of row pointers such that for A[k], k is between IA[i] and IA[i + 1] - 1.
- JA - is a list[NNZ] of column indexes such that JA[i] is A[i]'s column index in the matrix.
- S - is the (int rows, int columns) tuple size of the matrix.
(
List<int> value,
List<int> rowPointer,
List<int> columnIndex,
(int rows, int columns) size
)
Below is the full code of the Mendz.Library.Matrices.CRS class.
CRS.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Threading.Tasks;
namespace Mendz.Library.Matrices
{ public sealed class CRS<T>
{
public List<T> Value { get; private set; } = new List<T>();
public List<int> RowPointer { get; private set; } = new List<int>();
public List<int> ColumnIndex { get; private set; } = new List<int>();
public (int rows, int columns) Size { get; private set; }
public CRS((int rows, int columns) size)
{
Size = size;
}
public CRS(List<T> value,
List<int> rowPointer,
List<int> columnIndex,
(int rows, int columns) size)
{
Value = value;
RowPointer = rowPointer;
ColumnIndex = columnIndex;
Size = size;
}
public void Compress<K>(IDOKSparseMatrix<K, T> sparseMatrix)
{
List<T> value = new List<T>();
List<int> rowPointer = new List<int>();
List<int> columnIndex = new List<int>();
(int rows, int columns) size = sparseMatrix.Size;
Func<K, (int row, int column)> convert = (key) =>
{
(int row, int column) coordinates;
if (typeof(K) == typeof(int))
{
coordinates = MatrixCoordinates.ToCoordinates(
size, (dynamic)key, sparseMatrix.LinearIndexMode);
}
else
{
coordinates = (dynamic)key;
}
return coordinates;
};
var crs = from items in sparseMatrix.Matrix
orderby items.Key
select (convert(items.Key), items.Value);
int r = -1;
int rp = 0;
foreach (var item in crs)
{
(int row, int column) = item.Item1;
if (row > r)
{
// Fill-in for rows of 0's...
for (int i = row; i > r; i--)
{
rowPointer.Add(rp);
}
r = row;
}
value.Add(item.Item2);
columnIndex.Add(column);
rp++;
}
if (rp != value.Count)
{
throw new DataMisalignedException("JA[N] != NNZ");
}
if (size.rows - 1 > r)
{
// Fill-in for rows of 0's...
for (int i = size.rows - 1; i > r; i--)
{
rowPointer.Add(rp);
}
}
rowPointer.Add(rp);
Value = value;
RowPointer = rowPointer;
ColumnIndex = columnIndex;
Size = size;
}
public void Decompress<K>(IDOKSparseMatrix<K, T> sparseMatrix)
{
if (!sparseMatrix.Size.Equals(Size))
{
throw new InvalidOperationException("Sparse matrix size is invalid.");
}
Action<T, int, int> decompress = (v, r, c) =>
{
dynamic key;
if (typeof(K) == typeof(int))
{
key = MatrixCoordinates.ToLinearIndex(
Size, (r, c), sparseMatrix.LinearIndexMode);
}
else
{
key = (r, c);
}
sparseMatrix.SetEntry(key, v);
};
int rows = Size.rows;
if (sparseMatrix.IsConcurrent)
{
Parallel.For(0, rows, (j) =>
{
Parallel.For(RowPointer[j], RowPointer[j + 1], (i) =>
{
decompress(Value[i], j, ColumnIndex[i]);
});
});
}
else
{
for (int j = 0; j < rows; j++)
{
for (int i = RowPointer[j]; i < RowPointer[j + 1]; i++)
{
decompress(Value[i], j, ColumnIndex[i]);
}
}
}
}
public void Deconstruct(out List<T> value,
out List<int> rowPointer,
out List<int> columnIndex,
out (int rows, int columns) size)
{
value = Value;
rowPointer = RowPointer;
columnIndex = ColumnIndex;
size = Size;
}
}
}
Compressed Column Storage (CCS)
The compressed column storage (CCS) is also known as the compressed sparse column (CSC). It is also one of the common compressed matrix formats. It compresses the column indexes by storing the extents of columns instead.- A - is a list[NNZ] of non-zero values in the matrix.
- IA - is a list[Ni + 1] of column pointers such that for A[k], k is between IA[i] and IA[i + 1] - 1.
- JA - is a list[NNZ] of row indexes such that JA[i] is A[i]'s row index in the matrix.
- S - is the (int rows, int columns) tuple size of the matrix.
(
List<int> value,
List<int> columnPointer,
List<int> rowIndex,
(int rows, int columns) size
)
Below is the full code of the Mendz.Library.Matrices.CCS class.
CCS.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Threading.Tasks;
namespace Mendz.Library.Matrices
{
public sealed class CCS<T>
{
public List<T> Value { get; private set; } = new List<T>();
public List<int> ColumnPointer { get; private set; } = new List<int>();
public List<int> RowIndex { get; private set; } = new List<int>();
public (int rows, int columns) Size { get; private set; }
public CCS((int rows, int columns) size)
{
Size = size;
}
public CCS(List<T> value,
List<int> columnPointer,
List<int> rowIndex,
(int rows, int columns) size)
{
Value = value;
ColumnPointer = columnPointer;
RowIndex = rowIndex;
Size = size;
}
public void Compress<K>(IDOKSparseMatrix<K, T> sparseMatrix)
{
List<T> value = new List<T>();
List<int> columnPointer = new List<int>();
List<int> rowIndex = new List<int>();
(int rows, int columns) size = sparseMatrix.Size;
Func<K, int> order = (key) =>
{
int linearIndex;
if (typeof(K) == typeof(int))
{
linearIndex = (dynamic)key;
}
else
{
linearIndex = MatrixCoordinates.ToLinearIndex(
size, (dynamic)key, MatrixLinearIndexMode.ColumnMajorOrder);
}
return linearIndex;
};
Func<K, (int row, int column)> convert = (key) =>
{
(int row, int column) coordinates;
if (typeof(K) == typeof(int))
{
coordinates = MatrixCoordinates.ToCoordinates(
size, (dynamic)key, sparseMatrix.LinearIndexMode);
}
else
{
coordinates = (dynamic)key;
}
return coordinates;
};
var ccs = from items in sparseMatrix.Matrix
orderby order(items.Key)
select (convert(items.Key), items.Value);
int c = -1;
int cp = 0;
foreach (var item in ccs)
{
(int row, int column) = item.Item1;
if (column > c)
{
// Fill-in for columns of 0's...
for (int i = column; i > c; i--)
{
columnPointer.Add(cp);
}
c = column;
}
value.Add(item.Item2);
rowIndex.Add(row);
cp++;
}
if (cp != value.Count)
{
throw new DataMisalignedException("JA[N] != NNZ");
}
if (size.columns - 1 > c)
{
// Fill-in for columns of 0's...
for (int i = size.columns - 1; i > c; i--)
{
columnPointer.Add(cp);
}
}
columnPointer.Add(cp);
Value = value;
ColumnPointer = columnPointer;
RowIndex = rowIndex;
Size = size;
}
public void Decompress<K>(IDOKSparseMatrix<K, T> sparseMatrix)
{
int columns = Size.columns;
if (!sparseMatrix.Size.Equals(Size))
{
throw new InvalidOperationException("Sparse matrix size is invalid.");
}
Action<T, int, int> decompress = (v, r, c) =>
{
dynamic key;
if (typeof(K) == typeof(int))
{
key = MatrixCoordinates.ToLinearIndex(
Size, (r, c), sparseMatrix.LinearIndexMode);
}
else
{
key = (r, c);
}
sparseMatrix.SetEntry(key, v);
};
if (sparseMatrix.IsConcurrent)
{
Parallel.For(0, columns, (j) =>
{
Parallel.For(ColumnPointer[j], ColumnPointer[j + 1], (i) =>
{
decompress(Value[i], RowIndex[i], j);
});
});
}
else
{
for (int j = 0; j < columns; j++)
{
for (int i = ColumnPointer[j]; i < ColumnPointer[j + 1]; i++)
{
decompress(Value[i], RowIndex[i], j);
}
}
}
}
public void Deconstruct(out List<T> value,
out List<int> columnPointer,
out List<int> rowIndex,
out (int rows, int columns) size)
{
value = Value;
columnPointer = ColumnPointer;
rowIndex = RowIndex;
size = Size;
}
}
}
Comments
Post a Comment