This module implements operations on matrices in which the elements are all 0 or 1, with addition and multiplication being done modulo 2. The matrices are stored with consecutive bits of a column packed into 32-bit words, and the procedures are implemented where possible using bit operations on these words.

This is an appropriate representation when the matrices are dense (ie, 0s and 1s are about equally frequent). Matrices in which most elements are 0s may be better handled with the sparse modulo-2 matrix routines. Matrices can be converted between these two formats using the module-2 matrix conversion routines.

All procedures in this module display an error message on standard error and terminate the program if passed an invalid argument (indicative of a programming error), or if memory cannot be allocated. Errors from invalid contents of a file result in an error code being returned to the caller, with no message being printed by this module.

This module represents a matrix by a pointer to a structure of type
`mod2dense`. This structure records the number of rows and
columns in the matrix, and contains an array of pointers to where the
bits making up each column are stored. These bits are packed 32 per
word. When possible, bits in a column are manipulated 32 bits at a
time, which operations such as adding one column to another much
faster than the corresponding operations on rows. The pointer
structure also allows the columns of a matrix to easily be rearranged,
which may be necessary when doing matrix inversion.

**Header files required**:
`mod2dense.h`

The following macros take a pointer to a mod2dense structure as their argument, and return the number of rows or the number of columns in the matrix pointed to, which will have been fixed when the matrix was created with mod2dense_allocate:

mod2dense_rows(m) /* Returns the number of rows in m */ mod2dense_cols(m) /* Returns the number of columns in m */

Allocates space for a matrix with the given number of rows and columns, and returns a pointer to it. If there is not enough memory available, a message is displayed on standard error and the program is terminated. The matrix should be freed withmod2dense *mod2dense_allocate ( int n_rows, /* Number of rows in matrix */ int n_cols /* Number of columns in matrix */ )

Frees the space occupied by the matrix for re-use. The pointer passed should no longer be used.void mod2dense_free ( mod2dense *m /* Pointer to matrix to free */ )

Sets all of the elements of the matrix passed to 0.void mod2dense_clear ( mod2dense *m /* Pointer to matrix to clear */ )

Copies the contents of the first matrix passed,void mod2dense_copy ( mod2dense *m /* Pointer to matrix to copy from */ mod2dense *r /* Pointer to matrix to receive data */ )

Copies selected rows of the first matrix,void mod2dense_copyrows ( mod2dense *m, /* Pointer to matrix to copy columns from */ mod2dense *r, /* Pointer to matrix in which to store data */ int *rows /* Indexes of rows, numbered from 0 */ )

Copies selected columns of the first matrix,void mod2dense_copycols ( mod2dense *m, /* Pointer to matrix to copy columns from */ mod2dense *r, /* Pointer to matrix in which to store data */ int *cols /* Indexes of columns, numbered from 0 */ )

The matrix is printed on standard output as "0" and "1" characters, each preceded by a space, with one line of "0"s and "1"s for each row of the matrix.void mod2dense_print ( FILE *f, /* File to print to */ mod2dense *m /* Pointer to matrix to print */ )

Writes a machine-readable representation the dense matrixint mod2dense_write ( FILE *f, /* File to write data to */ mod2dense *m /* Pointer to matrix write out */ )

The data written to the file consists of the number of rows and the
number of columns, followed by the bits in each column, packed into
32-bit words. The data should be readable by `mod2dense_read` even on a machine with a
different byte-ordering.

The value returned by `mod2dense_write` is one if the
operation was successful, zero if an error of some sort occurred.

Reads a dense modulo-2 matrix from the filemod2dense *mod2dense_read ( FILE *f, /* File to read data from */ )

The value returned is a pointer to the matrix read, for which space
will have been allocated by `mod2dense_read`, or zero if an
error occurred (either an error reading the file, or data not in the
right format).

Returns the value (0 or 1) of the element in the given row and column of the matrixint mod2dense_get ( mod2dense *m, /* Pointer to matrix to get element from */ int row, /* Row of element (indexed from zero) */ int col /* Column of element (indexed from zero) */ )

Set the element in the given row and column of the matrixvoid mod2dense_set ( mod2dense *m, /* Pointer to matrix to get element from */ int row, /* Row of element (indexed from zero) */ int col, /* Column of element (indexed from zero) */ int value /* New value of element (0 or 1) */ )

Flips the value of the element in the given row and column of the matrixint mod2dense_flip ( mod2dense *m, /* Pointer to matrix to get element from */ int row, /* Row of element (indexed from zero) */ int col /* Column of element (indexed from zero) */ )

Stores the transpose of its first argument,void mod2dense_transpose ( mod2dense *m, /* Matrix to compute transpose of */ mod2dense *r /* Result of transpose operation */ )

Adds matricesvoid mod2dense_add ( mod2dense *m1, /* Left operand of add */ mod2dense *m2, /* Right operand of add */ mod2dense *r /* Place to store result of add */ )

Does a matrix multiplication ofvoid mod2dense_multiply ( mod2dense *m1, /* Left operand of multiply */ mod2dense *m2, /* Right operand of multiply */ mod2dense *r /* Place to store result of multiply */ )

The algorithm used runs faster if **m2** contains mostly 0s, but
it is also appropriate for matrices with many 1s.

Returns one if every element ofint mod2dense_equal ( mod2dense *m1, /* Pointers to the two matrices */ mod2dense *m2 /* to compare */ )

int mod2dense_invert ( mod2dense *m, /* Matrix to find inverse of (destroyed) */ mod2dense *r /* Place to store the inverse */ )

Inverts the first matrix passed, **m**, and stores its inverse in
the second matrix, **r**. The contents of **m** are destroyed
by this operation, though it remains a valid matrix for storing into
later. The matrix **m** must have the same number of rows as
columns. The matrix **r** must already have been allocated, and
must have the same number of rows and columns as **m**. The
two matrices passed must not be the same.

The value returned is one if the inversion was successful and zero if the matrix turned out to be singular (in which case the contents of both the original matrix and the result matrix will be garbage).

The algorithm used is based on inverting M by transforming the equation MI = M to the equation MR = I using column operations, at which point R is the inverse of M. The representation of matrices used allows easy swapping of columns as needed by fiddling pointers.

int mod2dense_forcibly_invert ( mod2dense *m, /* Matrix to find inverse of (destroyed) */ mod2dense *r, /* Place to store the inverse */ int *a_row, /* Place to store row indexes of altered elements */ int *a_col /* Place to store column indexes of altered elements */ )

Inverts the first matrix passed, **m**, and stores its inverse
in the second matrix, **r**, proceeding with the inversion even if
**m** is singular, by changing some elements as necessary. The
contents of **m** are destroyed by this operation, though it
remains a valid matrix for storing into later. The matrix **m**
must have the same number of rows as columns. The matrix **r**
must already have been allocated, and must have the same number of
rows and columns as **m**. The two matrices passed must not be the
same.

The value returned is the number of elements of **m** that had
to be changed to make inversion possible (zero, if the original matrix
was non-singular). The row and column indexes of the elements of the
original matrix that were changed are stored in the arrays passed as
the last two elements. These arrays must have as many elements as the
dimension of the matrix. (This is so even if it is known that fewer
elements than this will be changed, as these arrays are also used as
temporary storage by this routine.)

See `mod2dense_invert` for the algorithm used.

int mod2dense_invert_selected ( mod2dense *m, /* Matrix from which a submatrix is inverted (destroyed) */ mod2dense *r, /* Place to store the inverse */ int *rows, /* Place to store indexes of rows used and not used */ int *cols /* Place to store indexes of columns used and not used */ )

Inverts a matrix obtained by selecting certain columns from the
first matrix passed, **m**, which must have at least as many
columns as rows. The second matrix passed, **r**, must already
exist, and must have the same number of rows and columns as **m**.
The result of inverting the sub-matrix of **m** is stored in the
corresponding columns of **r**, with the other columns being set to
garbage (or zero, see below). Normally, one would extract just the
relevant columns afterwards using `mod2dense_copycols`.) The contents of
**m** are destroyed (though it remains a valid matrix for storing
into later. The two matrices passed must not be the same.

The indexes of the columns selected are stored, in order, in the last
argument, **cols**, followed by the columns not selected (in
arbitrary order). The argument **rows** is set to the indexes of
the rows used, which will be simply the indexes from zero up if the
matrix is invertible, and will otherwise give an ordering that allows
the inversion to proceed as far as possible.

The value returned is zero if an invertible matrix was found, and
is otherwise the number of columns/rows that are redundant (ie, the
amount by which matrix falls short of being of full rank). If
inversion fails, partial results are stored in the columns and rows of
**r** identified by the initial portions of **cols** and
**rows**, such that if these rows and columns were extracted in
their new order, they would constitute the inverse of the
corresponding re-ordered submatrix of **m**. The remaining portion
of **cols** up to the number of rows in **m** will contain
indexes of columns of **r** that are selected arbitrarily; these
columns will, however, be set to contain all zeros.

Note that when the first matrix is square, and non-singular, the result is NOT in general the same as that obtained by calling mod2dense_invert, since that procedure orders the columns of the inverse so that it applies to the original ordering of the columns of the first matrix.

See `mod2dense_invert` for the algorithm used.

Back to index for LDPC software