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 represented by doubly-linked lists of entries representing the elements in each row and column that are 1s, with other elements being assumed to be zero.
This is an appropriate representation when the matrices are sparse (ie, 0s are much more frequent that 1s). Matrices in which 0s and 1s are about equally likely may be better handled with the dense 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.
Representation of sparse matrices
This module represents a non-zero element of a matrix (which must have the value 1, since these are modulo-2 matrices) by a node of type mod2entry, which contains the row and column of the element, pointers to the next non-zero elements above and below in its column and to the left and the right in its row, and two double-precision floating-point numbers called pr and lr, which are of no significance to this module, but which are used by the routines for decoding LDPC codes by probability propagation.
The mod2sparse type represents a matrix. It records the number of rows and columns in the matrix, and contains arrays of pointers to the mod2entry structures for the first non-zero element in each row and the first non-zero element in each column.
Matrices must be created by the mod2sparse_allocate procedure, which returns a pointer to a mod2sparse structure. When a matrix is no longer needed, the space it occupies can be freed with mod2sparse_free. Elements within a matrix, represented by mod2entry nodes, are allocated as needed, and if deleted, they will be reused for new elements within the same matrix. The space they occupy is not reusable for other matrices or other purposes until the entire matrix is either freed, with mod2sparse_free, or cleared to all zeros, with mod2sparse_clear, or used as the result matrix for copying or arithmetic operations.
Header files required:
mod2sparse.h
mod2sparse_rows(m) /* Returns the number of rows in m */ mod2sparse_cols(m) /* Returns the number of columns in m */
The macros for finding the first or last entry in a row or column take as their arguments a pointer to the matrix (mod2sparse *) and a row or column index, starting at zero. The other macros take as their arguments a pointer to an entry (mod2entry *) within some matrix.
mod2sparse_first_in_row(m,i) /* Returns the first entry in row i of m */
mod2sparse_first_in_col(m,j) /* Returns the first entry in column j of m */
mod2sparse_last_in_row(m,i) /* Returns the last entry in row i of m */
mod2sparse_last_in_col(m,j) /* Returns the last entry in column j of m */
mod2sparse_next_in_row(e) /* Returns the entry after e in its row */
mod2sparse_next_in_col(e) /* Returns the entry after e in its column */
mod2sparse_prev_in_row(e) /* Returns the entry before e in its row */
mod2sparse_prev_in_col(e) /* Returns the entry before e in its col */
mod2sparse_row(e) /* Returns the row index of entry e */
mod2sparse_col(e) /* Returns the column index of entry e */
mod2sparse_at_end(e) /* Returns 1 if e is a special entry obtained
by moving past the end, returns 0 otherwise */
Allocates space for a matrix with the given number of rows and columns, and returns a pointer to it. The matrix will initially be all zero.mod2sparse *mod2sparse_allocate ( int n_rows, /* Number of rows in matrix */ int n_cols /* Number of columns in matrix */ )
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 mod2sparse_free once it is no longer in use.
mod2sparse_free:
Free the space occupied by a sparse module-2 matrix.
Frees the space occupied by the matrix for re-use. The pointer passed should not be used afterward. Note that space for the individual matrix elements (but not the matrix as a whole) is also freed when mod2sparse_clear is called, or the matrix is used as the destination for other operations.void mod2sparse_free ( mod2sparse *m /* Pointer to matrix to free */ )
Sets all of the elements of the matrix passed to 0. The space occupied by the previous non-zero elements is freed for use in other matrices, or other purposes. The matrix itself is not freed, however. To do that, use mod2sparse_free.void mod2sparse_clear ( mod2sparse *m /* Pointer to matrix to clear */ )
mod2sparse_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 mod2sparse_copy ( mod2sparse *m /* Pointer to matrix to copy from */ mod2sparse *r /* Pointer to matrix to receive data */ )
The space occupied by the previous non-zero entries of r is freed for general use (which may include being reused immediately for the copies of the entries in m).
mod2sparse_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 mod2sparse_copyrows ( mod2sparse *m, /* Pointer to matrix to copy rows from */ mod2sparse *r, /* Pointer to matrix in which to store data */ int *rows /* Indexes of rows, numbered from 0 */ )
The space occupied by the previous non-zero entries of r is freed for general use (which may include being reused immediately for the copies of the entries in m).
mod2sparse_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 mod2sparse_copycols ( mod2sparse *m, /* Pointer to matrix to copy columns from */ mod2sparse *r, /* Pointer to matrix in which to store data */ int *cols /* Indexes of columns, numbered from 0 */ )
The space occupied by the previous non-zero entries of r is
freed for general use (which may include being reused immediately for
the copies of the entries in m).
mod2sparse_print:
Print a sparse modulo-2 matrix in human-readable form.
The matrix is printed on standard output with one line of output per row, of the formvoid mod2sparse_print ( FILE *f, /* File to print to */ mod2sparse *m /* Pointer to matrix to print */ )
where row is the index of the row, and the col entries are the indexes of columns that are non-zero in that row. Row and column indexes start at zero. Rows with no entries are printed with no column indexes after the colon. The number of columns is not indicated in the output.row: col col col ...
mod2sparse_write:
Write a sparse modulo-2 matrix to a file in machine-readable format.
Writes a machine-readable representation the sparse 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 mod2sparse_write ( FILE *f, /* File to write data to */ mod2sparse *m /* Pointer to matrix write out */ )
The data written to the file starts with the number of rows and the number of columns. Following this are negative integers giving row indexes (starting at 1), which apply until the next row index, and positive integers giving column indexes (starting at 1) for a non-zero entry in the matrix. The data should be readable by mod2sparse_read even on a machine with a different byte-ordering.
The value returned by mod2sparse_write is one if the operation was successful, zero if an error of some sort occurred.
mod2sparse_read:
Read a sparse modulo-2 matrix from a file.
Reads a sparse 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 mod2sparse_read is called should have been written by mod2sparse_write. Other binary data may precede or follow this data.mod2sparse *mod2sparse_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 mod2sparse_read, or zero if an
error occurred (either an error reading the file, or data not in the
right format).
mod2sparse_find:
Look for an entry at a given row and column.
Looks for an entry at the given row and column in the matrix m, representing a non-zero element (ie, one with value 1). Returns a pointer to this entry if it exists, or zero (a null pointer) if it does not exist (ie, if that element of the matrix has value 0).mod2entry *mod2sparse_find ( mod2sparse *m, /* Matrix in which to look for entry */ int row, /* Row index (from 0) */ int col /* Column index (from 0) */ )
The search strategy is to first look at the end of the row and the end of the column. The entry might be found at one of these two places, or it might be determinable from these end entries that no entry exists at the given row and column. Otherwise, searches are done from the start of the row and the start of the column, in parallel, until an entry with the given row and column are found, or until it can be determined that such an entry does not exist. Searching in parallel ensures that the operation will be fast if either the row is sparse or the column is sparse.
mod2sparse_insert:
Insert an entry at a given row and column.
Adds a new entry (representing an element with value 1) at the given row and column position in the matrix m. If such an entry already exists, nothing is done (this is not considered to be an error). The new (or existing) entry is returned as the value of this procedure.mod2entry *mod2sparse_insert ( mod2sparse *m, /* Matrix in which to insert an entry */ int row, /* Row index (from 0) */ int col /* Column index (from 0) */ )
The search strategy is to first look at the end of the row for an existing entry or for the place where the new entry belongs. If this fails, the row is searched from the beginning. If an existing entry is found, it is returned. Otherwise, a new entry is created, it is inserted in its correct place in the row, and it is inserted in its correct place in its column, once again by first looking at the end, and then if required searching from the beginning.
The effect of this strategy is that a sparse matrix can be efficiently created by either adding entries in increasing order by row and column or in decreasing order by row and column.
mod2sparse_delete:
Delete an entry from a sparse modulo-2 matrix.
Deletes the entry e from the sparse matrix m, which effectively sets to zero the element of the matrix that this entry corresponded to. The entry is freed for future use in the same matrix, but not (immediately, at least) for use in other matrices, or generally. The pointer to this entry should not be used again once it is deleted.void mod2sparse_delete ( mod2sparse *m, /* Matrix in which to delete an entry */ mod2entry *e /* Entry to delete - MUST be in m */ )
The time required for this operation does not depend on how many entries are currently in the matrix.
Warning: It is an error if e is not an entry of
m. This error is not currently diagnosed, but doing this may
cause serious problems, as it may lead later to entries for m
being erroneously freed when the matrix to which e properly
belongs is freed.
mod2sparse_transpose:
Compute the transpose of a sparse modulo-2 matrix.
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 mod2sparse_transpose ( mod2sparse *m, /* Matrix to compute transpose of */ mod2sparse *r /* Result of transpose operation */ )
The space occupied by the previous non-zero entries of r is freed for general use.
mod2sparse_add:
Add two sparse 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 mod2sparse_add ( mod2sparse *m1, /* Left operand of add */ mod2sparse *m2, /* Right operand of add */ mod2sparse *r /* Place to store result of add */ )
The space occupied by the previous non-zero entries of r is freed for general use.
mod2sparse_multiply:
Multiply two sparse 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 mod2sparse_multiply ( mod2sparse *m1, /* Left operand of multiply */ mod2sparse *m2, /* Right operand of multiply */ mod2sparse *r /* Place to store result of multiply */ )
The space occupied by the previous non-zero entries of r is freed for general use.
mod2sparse_multvec:
Multiply a vector by a sparse modulo-2 matrix.
Multiplies the vector u on the left by the sparse modulo-2 matrix m, storing the result in v. Both u and v are modulo-2 vectors, but are stored unpacked, with one bit per char. Any non-zero value in u is equivalent to '1'. The vectors u and v must not overlap.void mod2sparse_multvec ( mod2sparse *m, /* Pointer to matrix to multiply by, M rows, N columns */ char *u, /* Pointer to unpacked vector to multiply, N long */ char *v /* Pointer to unpacked result vector, M long */ )
mod2sparse_equal:
Check whether two sparse 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 mod2sparse_equal ( mod2sparse *m1, /* Pointers to the two matrices */ mod2sparse *m2 /* to compare */ )
Returns the number of 1s in the given row of the matrix, by counting the number of entries in that row.int mod2sparse_count_row ( mod2sparse *m, /* Pointer to matrix */ int row /* Index of row to count (from 0) */ )
mod2sparse_count_col:
Count the number of 1s in a column of a sparse matrix.
Returns the number of 1s in the given column of the matrix, by counting the number of entries in that column.int mod2sparse_count_col ( mod2sparse *m, /* Pointer to matrix */ int col /* Index of column to count (from 0) */ )
mod2sparse_add_row:
Add a row to a row of a sparse matrix.
Modifies the row with index row1 in the matrix m1 by adding to that row the row with index row2 in the matrix m2. The matrix m1 must have at least as many columns as m2. This operation is performed by inserting entries into the row of m1 at positions where they exist in the row of m2 but not in the row of m1, and deleting entries in the row of m1 that exist in the same position in the row of m2. The matrix m2 is not modified.void mod2sparse_add_row ( mod2sparse *m1, /* Matrix containing row to add to */ int row1, /* Index in this matrix of row to add to */ mod2sparse *m2, /* Matrix containing row to add from */ int row2 /* Index in this matrix of row to add from */ )
mod2sparse_add_col:
Add a column to a column of a sparse matrix.
Modifies the column with index col1 in the matrix m1 by adding to that column the column with index col2 in the matrix m2. The matrix m1 must have at least as many rows as m2. This operation is performed by inserting entries into the column of m1 at positions where they exist in the column of m2 but not in the column of m1, and deleting entries in the column of m1 that exist in the same position in the column of m2. The matrix m2 is not modified.void mod2sparse_add_col ( mod2sparse *m1, /* Matrix containing column to add to */ int col1, /* Index in this matrix of col to add to */ mod2sparse *m2, /* Matrix containing column to add from */ int col2 /* Index in this matrix of column to add from */ )
int mod2sparse_decomp ( mod2sparse *A, /* Matrix to find LU decomposition within, M by N */ int K, /* Size of sub-matrix to find LU decomposition of */ mod2sparse *L, /* Matrix in which L is stored, M by K */ mod2sparse *U, /* Matrix in which U is stored, K by N */ int *rows, /* Array where row indexes are stored, M long */ int *cols, /* Array where column indexes are stored, N long */ mod2sparse_strategy strategy, /* Strategy to follow in picking rows/columns */ int abandon_number, /* Number of columns to abandon at some point */ int abandon_when /* When to abandon these columns */ )
Takes as input a matrix, A, having M rows and N columns, and an integer K. Finds an LU decomposition of a K by K sub-matrix of A. The decomposition is stored in the matrix L, with M rows and K columns, and the matrix U, with K rows and N columns. The product of L and U will be equal to the K by K submatrix of A obtained by taking only rows and columns that are given in the first K elements of the rows and cols arrays, which are set by this procedure, with this sub-matrix distributed over the original M rows and N columns. Furthermore, the ordering of the row and column indexes in these arrays will be set so that if the rows of L and the columns of U were rearranged in this order, L would be lower triangular, with zeros in rows past row K, and U would be upper triangular, with zeros in columns past column K. The rows array is M long, and the cols array is N long. The elements in both arrays after the first K contain the indexes of the rows and columns not selected to be part of the sub-matrix of A, in arbitrary order.
The rows and columns of A are selected in order to try to make the LU decomposition as sparse as possible, using the strategy identified by the strategy, abandon_number, and abandon_when parameters. The possible strategies are Mod2sparse_first, Mod2sparse_mincol, and Mod2sparse_minprod. If abandon_number is greater than zero, it is possible that the matrix will appear to have linearly dependent rows when it actually does not. See the discussion of sparse LU decomposition methods for details about these strategies.
If A is not of rank K or more, L will contain some number less than K of non-zero columns, and U will contain an equal number of non-zero rows. The entries in the rows and cols arrays for the extra zero rows or columns will be arbitrary (but valid). The number of extra zero columns is returned as the value of this procedure (hence a return value of zero indicates that a K by K sub-matrix of full rank was found).
The matrix A is not altered. The previous contents of L and U are cleared.
mod2sparse_forward_sub:
Solve a lower-triangular system by forward substitution.
int mod2sparse_forward_sub ( mod2sparse *L, /* Matrix that is lower triangular after reordering */ int *rows, /* Array of indexes (from 0) of rows for new order */ char *x, /* Vector on right of equation, also reordered */ char *y /* Place to store solution */ )
Solves the system of equations Ly=x for y by forward substitution, based on L being lower triangular after its rows are reordered according to the given index array. The vectors x and y are stored unpacked, one bit per character. If L is M by K, then x should be M long, but only the K bits indexed by rows are looked at. The solution vector, y, must be K long. Only K rows of L are used, as also determined by the K indexes in the rows argument. If rows is null, the first K rows of L and the first K elements of x are used.
If the matrix L does not have 1s on its diagonal (after row rearrangement), there may be no solution, depending on what x is. If no solution exists, this procedure returns zero, otherwise it returns one. Any arbitrary bits in the solution are set to zero.
mod2sparse_backward_sub:
Solve an upper-triangular system by backward substitution.
int mod2sparse_backward_sub ( mod2sparse *U, /* Matrix that is upper triangular after reordering */ int *cols, /* Array of indexes (from 0) of columns for new order */ char *y, /* Vector on right of equation */ char *z /* Place to store solution, also reordered */ )
Solves Uz=y for z by backward substitution, based on U being upper triangular after its columns are reordered according to the given index array. The vectors y and z are stored unpacked, one bit per character. If U is K by N, then the solution vector, z, should be N long, but only the K bits indexed by cols are set. The vector y must be K long. Only K columns of U are used, as also determined by the K indexes in the cols argument. The other columns of U must be zero (this is not checked, but is necessary for the method used to work). If cols is null, the first K columns of U and the first K elements of z are used.
If the matrix U does not have 1s on its diagonal (after column rearrangement) there may be no solution, depending on what y is. If no solution exists, this procedure returns zero, otherwise it returns one. Any arbitrary bits in the solution are set to zero.