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
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 with mod2dense_free once it is no longer in use.mod2dense *mod2dense_allocate ( int n_rows, /* Number of rows in matrix */ int n_cols /* Number of columns in matrix */ )
mod2dense_free:
Free the space occupied by a dense module-2 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 */ )
mod2dense_copy:
Copy the contents of one matrix to another.
Copies the contents of the first matrix passed, m, to the second matrix passed, r, which must already have been allocated, and must have at least as many rows and columns as the first. If r is larger than m, its elements that have row or column indexes greater than the dimension of m are set to zeros.void mod2dense_copy ( mod2dense *m /* Pointer to matrix to copy from */ mod2dense *r /* Pointer to matrix to receive data */ )
mod2dense_copyrows:
Copy selected rows from one matrix to another.
Copies selected rows of the first matrix, m, to the second matrix, r, which must already have been allocated, and which must have at least as many columns as m. The indexes of the rows to copy are given in order as an array of length the same as the number of rows in r; duplicates are allowed. Row indexes start at 0. These rows are copied to r, with the row indexed by the first entry in rows going to the first row of r, and so forth. If r has more columns than m, the extra entries in each row are set to zeros.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 */ )
mod2dense_copycols:
Copy selected columns from one matrix to another.
Copies selected columns of the first matrix, m, to the second matrix, r, which must already have been allocated, and which must have at least as many rows as m. The indexes of the columns to copy are given in order as an array of length the same as the number of columns in r; duplicates are allowed. Column indexes start at 0. These columns are copied to r, with the column indexed by the first entry in cols going to the first column of r, and so forth. If r has more rows than m, the extra entries in each column are set to zeros.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 */ )
mod2dense_write:
Write a dense modulo-2 matrix to a file in machine-readable format.
Writes a machine-readable representation the dense matrix m to the file f. The file should have been opened in binary mode (with a "b" in the mode passed to fopen). The contents written will not be text, and will not be human-readable. Other binary data may precede or follow the data for the matrix written.int 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.
mod2dense_read:
Read a dense modulo-2 matrix from a file.
Reads a dense modulo-2 matrix from the file f. This file should have been opened in binary mode (with a "b" in the mode passed to fopen). The contents of the file at the point when mod2dense_read is called should have been written by mod2dense_write. Other binary data may precede or follow this data.mod2dense *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).
mod2dense_get:
Get an element of a dense modulo-2 matrix.
Returns the value (0 or 1) of the element in the given row and column of the matrix m.int 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) */ )
mod2dense_set:
Set an element of a dense modulo-2 matrix.
Set the element in the given row and column of the matrix m to the specified value.void 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) */ )
mod2dense_flip:
Flip an element of a dense modulo-2 matrix.
Flips the value of the element in the given row and column of the matrix m, changing it to 0 if it was 1, and to 1 if it was 0. Returns the new value of this element.int 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, m, in the matrix pointed to by its second argument, r, which must already have been allocated, and which must have as many rows as m has columns, and as many columns as m has rows. The two matrices m and r must not be the same (ie, the two pointers passed must be different).void mod2dense_transpose ( mod2dense *m, /* Matrix to compute transpose of */ mod2dense *r /* Result of transpose operation */ )
mod2dense_add:
Add two dense modulo-2 matrices.
Adds matrices m1 and m2, storing the result in the matrix pointed to by r. All three matrices must have the same numbers of rows and columns. It is permissible for r to be the same as m1 and/or m2. Neither of the first two matrices is changed by this procedure (unless they are the same as r).void mod2dense_add ( mod2dense *m1, /* Left operand of add */ mod2dense *m2, /* Right operand of add */ mod2dense *r /* Place to store result of add */ )
mod2dense_multiply:
Multiply two dense modulo-2 matrices.
Does a matrix multiplication of m1 by m2, and stores the result in the matrix pointed to by r. The matrices must have compatible numbers of rows and columns. Neither of the first two matrices is changed by this procedure. The result matrix, r, must not be the same as either m1 or m2.void 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.
mod2dense_equal:
Check whether two dense modulo-2 matrices are equal.
Returns one if every element of m1 is equal to the corresponding element of m2, and otherwise returns zero. The two matrices must have the same number of rows and the same number of columns.int 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.
mod2dense_forcibly_invert:
Forcibly invert a matrix by changing bits if necessary.
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.
mod2dense_invert_selected:
Invert a matrix with columns selected from a bigger matrix.
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.