Matrix Formats - ku-fpg/ecc-ldpc GitHub Wiki

There are several Matrix formats in ecc-lpdc, that help when implementing LDPC.

Matrix

module	Bit	Sparse	Unboxed	Notes
Data.BitMatrix.Alist	:white_check_mark:	:white_check_mark:	-	often used for LDPC (to make sparse)
Data.BitMatrix.Matlab	:white_check_mark:	-	-	rows and columns of 0 / 1
Data.BitMatrix.Sparse	:white_check_mark:	:white_check_mark:	-	optimized sparse matrix
Data.BitVector.Word64	:white_check_mark:	compact	:white_check_mark:	Vector of Bit Vector
Data.Matrix.Matlab	-	-	-	regular matrix
Data.Matrix.QuasiCyclic	-	only stores every n-th row	-	-

Matrix possibilities

Bit	Sparse	Unboxed	Description
-	-	-	A typical matrix that could hold soft (or hard) values (such as in the matrix package or matrices package)
-	-	:white_check_mark:	An general unboxed matrix that could old soft or hard values (as in the matrices package)
-	:white_check_mark:	-	There are several different sparse matrix representations (TODO: Add section detailing these
-	:white_check_mark:	:white_check_mark:	Again, several different sparse matrix representations exist
:white_check_mark:	-	-	Designed to hold binary data
:white_check_mark:	-	:white_check_mark:	Also designed to hold binary data (likely to be more efficient than boxed)
:white_check_mark:	:white_check_mark:	-	Designed to hold binary data that is also sparse. This can be done in several particularly efficient ways, depending on the structure of the matrix.
:white_check_mark:	:white_check_mark:	:white_check_mark:	This could be very efficient. Has the potential to be very space and time efficient.

Possible sparse representations

For a sparse bit matrix:

type BitMatrix1 = Set (Int, Int) -- Stores locations of the 1s in the matrix

For a sparse bit vector:

type BitVector1 = IntSet

For a general sparse matrix:

type SparseMatrix1 a = Map (Int, Int) a

2. Edward Kmett has a sparse matrix package that uses a Morton ordered representation. He has a six-part series of articles describing this.

Vector

module	Bit	Sparse	Unboxed	Notes
Data.BitVector.Sparse	:white_check_mark:	:white_check_mark:	-	list of set bit
Data.BitVector.Word64	:white_check_mark:	compact	:white_check_mark:	vector of Word64