<P><A NAME="insert"><HR><B>mod2sparse_insert</B>: Insert an entry at a given row and column.</A><BLOCKQUOTE><PRE>mod2entry *mod2sparse_insert( mod2sparse *m,  /* Matrix in which to insert an entry */  int row,        /* Row index (from 0) */  int col         /* Column index (from 0) */)</PRE></BLOCKQUOTE>Adds a new entry (representing an element with value 1) at the givenrow and column position in the matrix <B>m</B>.  If such an entryalready exists, nothing is done (this is not considered to be anerror).  The new (or existing) entry is returned as the value ofthis procedure.<P>The search strategy is to first look at the end of the row for anexisting entry or for the place where the new entry belongs.  If thisfails, the row is searched from the beginning.  If an existing entryis found, it is returned.  Otherwise, a new entry is created, it isinserted in its correct place in the row, and it is inserted in itscorrect place in its column, once again by first looking at the end,and then if required searching from the beginning.  <P>The effect of this strategy is that a sparse matrix can be efficientlycreated by either adding entries in increasing order by row and column or indecreasing order by row and column.<P><A NAME="delete"><HR><B>mod2sparse_delete</B>: Delete an entry from a sparse modulo-2 matrix.</A><BLOCKQUOTE><PRE>void mod2sparse_delete( mod2sparse *m,  /* Matrix in which to delete an entry */  mod2entry *e    /* Entry to delete - MUST be in m */)</PRE></BLOCKQUOTE>Deletes the entry <B>e</B> from the sparse matrix <B>m</B>, whicheffectively sets to zero the element of the matrix that this entrycorresponded to.  The entry is freed for future use in the samematrix, but not (immediately, at least) for use in other matrices, orgenerally.  The pointer to this entry should not be used again onceit is deleted.<P>The time required for this operation does not depend on how manyentries are currently in the matrix.<P><B>Warning:</B> It is an error if <B>e</B> is not an entry of<B>m</B>.  This error is not currently diagnosed, but doing this maycause serious problems, as it may lead later to entries for <B>m</B>being erroneously freed when the matrix to which <B>e</B> properlybelongs is freed.<A NAME="arith-sec"><P><HR><CENTER><BIG>Sparse Modulo-2 Matrix Arithmetic and Comparison</BIG></CENTER></A><A NAME="transpose"><HR><B>mod2sparse_transpose</B>: Compute the transpose of a sparse modulo-2 matrix.</A><BLOCKQUOTE><PRE>void mod2sparse_transpose( mod2sparse *m,  /* Matrix to compute transpose of */  mod2sparse *r   /* Result of transpose operation */)</PRE></BLOCKQUOTE>Stores the transpose of its first argument, <B>m</B>, in the matrixpointed to by its second argument, <B>r</B>, which must already havebeen allocated, and which must have as many rows as <B>m</B> hascolumns, and as many columns as <B>m</B> has rows.  The two matrices<B>m</B> and <B>r</B> must not be the same (ie, the two pointerspassed must be different).  <P>The space occupied by the previous non-zero entries of <B>r</B> isfreed for general use.<P><A NAME="add"><HR><B>mod2sparse_add</B>: Add two sparse modulo-2 matrices.</A><BLOCKQUOTE><PRE>void mod2sparse_add( mod2sparse *m1, /* Left operand of add */  mod2sparse *m2, /* Right operand of add */  mod2sparse *r   /* Place to store result of add */)</PRE></BLOCKQUOTE>Adds matrices <B>m1</B> and <B>m2</B>, storing the result in thematrix pointed to by <B>r</B>.  All three matrices must have the samenumbers of rows and columns.  It is permissible for <B>r</B> to be thesame as <B>m1</B> and/or <B>m2</B>.  Neither of the first two matrices ischanged by this procedure (unless they are the same as <B>r</B>).<P>The space occupied by the previous non-zero entries of <B>r</B> isfreed for general use.<P><A NAME="multiply"><HR><B>mod2sparse_multiply</B>: Multiply two sparse modulo-2 matrices.</A><BLOCKQUOTE><PRE>void mod2sparse_multiply ( mod2sparse *m1, /* Left operand of multiply */  mod2sparse *m2, /* Right operand of multiply */  mod2sparse *r   /* Place to store result of multiply */)</PRE></BLOCKQUOTE>Does a matrix multiplication of <B>m1</B> by <B>m2</B>, and stores theresult in the matrix pointed to by <B>r</B>.  The matrices must havecompatible numbers of rows and columns.  Neither of the first twomatrices is changed by this procedure.  The result matrix, <B>r</B>,must not be the same as either <B>m1</B> or <B>m2</B>.<P>The space occupied by the previous non-zero entries of <B>r</B> isfreed for general use.<P><A NAME="multvec"><HR><B>mod2sparse_multvec</B>: Multiply a vector by a sparse modulo-2 matrix.</A><BLOCKQUOTE><PRE>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 */)</PRE></BLOCKQUOTE>Multiplies the vector <B>u</B> on the left by the sparse modulo-2matrix <B>m</B>, storing the result in <B>v</B>.  Both <B>u</B> and<B>v</B> are modulo-2 vectors, but are stored unpacked, with one bitper char.  Any non-zero value in <B>u</B> is equivalent to '1'.  The vectors <B>u</B> and <B>v</B> must not overlap.<P><A NAME="equal"><HR><B>mod2sparse_equal</B>: Check whether two sparse modulo-2 matrices are equal.</A><BLOCKQUOTE><PRE>int mod2sparse_equal( mod2sparse *m1, /* Pointers to the two matrices */  mod2sparse *m2  /*   to compare                 */)</PRE></BLOCKQUOTE>Returns one if every element of <B>m1</B> is equal to thecorresponding element of <B>m2</B>, and otherwise returns zero.  Thetwo matrices must have the same number of rows and the same number ofcolumns.<A NAME="row-col-ops-sec"><P><HR><CENTER><BIG>Row/Column Operations on Sparse Modulo-2 Matrices</BIG></CENTER></A><A NAME="count_row"><HR><B>mod2sparse_count_row</B>: Count the number of 1s in a row of a sparse matrix.</A><BLOCKQUOTE><PRE>int mod2sparse_count_row( mod2sparse *m,  /* Pointer to matrix */  int row         /* Index of row to count (from 0) */)</PRE></BLOCKQUOTE>Returns the number of 1s in the given row of the matrix, by countingthe number of entries in that row.  <P><A NAME="count_col"><HR><B>mod2sparse_count_col</B>: Count the number of 1s in a column of a sparse matrix.</A><BLOCKQUOTE><PRE>int mod2sparse_count_col( mod2sparse *m,  /* Pointer to matrix */  int col         /* Index of column to count (from 0) */)</PRE></BLOCKQUOTE>Returns the number of 1s in the given column of the matrix, by countingthe number of entries in that column.  <P><A NAME="add_row"><HR><B>mod2sparse_add_row</B>: Add a row to a row of a sparse matrix.</A><BLOCKQUOTE><PRE>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 */)</PRE></BLOCKQUOTE>Modifies the row with index <B>row1</B> in the matrix <B>m1</B> byadding to that row the row with index <B>row2</B> in the matrix<B>m2</B>.  The matrix <B>m1</B> must have at least as many columns as<B>m2</B>.  This operation is performed by inserting entries into therow of <B>m1</B> at positions where they exist in the row of <B>m2</B>but not in the row of <B>m1</B>, and deleting entries in the row of<B>m1</B> that exist in the same position in the row of <B>m2</B>.The matrix <B>m2</B> is not modified.<P><A NAME="add_col"><HR><B>mod2sparse_add_col</B>: Add a column to a column of a sparse matrix.</A><BLOCKQUOTE><PRE>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 */)</PRE></BLOCKQUOTE>Modifies the column with index <B>col1</B> in the matrix <B>m1</B> byadding to that column the column with index <B>col2</B> in the matrix<B>m2</B>.  The matrix <B>m1</B> must have at least as many rows as<B>m2</B>.  This operation is performed by inserting entries into thecolumn of <B>m1</B> at positions where they exist in the column of<B>m2</B> but not in the column of <B>m1</B>, and deleting entries inthe column of <B>m1</B> that exist in the same position in the columnof <B>m2</B>.  The matrix <B>m2</B> is not modified.<A NAME="lu-decomp-sec"><P><HR><CENTER><BIG>LU Decomposition of Sparse Modulo-2 Matrices</BIG></CENTER></A><A NAME="decomp"><HR><B>mod2sparse_decomp</B>: Find an LU decomposition of a sparse modulo-2 (sub-)matrix.</A><BLOCKQUOTE><PRE>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 */)</PRE></BLOCKQUOTE><P>Takes as input a matrix, <B>A</B>, having <I>M</I> rows and<I>N</I> columns, and an integer <I>K</I>.  Finds an LU decompositionof a <I>K</I> by <I>K</I> sub-matrix of <B>A</B>.  The decompositionis stored in the matrix <B>L</B>, with <I>M</I> rows and <I>K</I>columns, and the matrix <B>U</B>, with <I>K</I> rows and <I>N</I>columns.  The product of <B>L</B> and <B>U</B> will be equal to the<I>K</I> by <I>K</I> submatrix of <B>A</B> obtained by taking onlyrows and columns that are given in the first <I>K</I> elements of the<B>rows</B> and <B>cols</B> arrays, which are set by this procedure,with this sub-matrix distributed over the original <I>M</I> rows and<I>N</I> columns.  Furthermore, the ordering of the row and columnindexes in these arrays will be set so that if the rows of <B>L</B>and the columns of <B>U</B> were rearranged in this order, <B>L</B>would be lower triangular, with zeros in rows past row <I>K</I>, and<B>U</B> would be upper triangular, with zeros in columns past column<I>K</I>.  The <B>rows</B> array is <I>M</I> long, and the <B>cols</B>array is <I>N</I> long.  The elements in both arrays after the first<I>K</I> contain the indexes of the rows and columns not selected tobe part of the sub-matrix of <B>A</B>, in arbitrary order.<P>The rows and columns of <B>A</B> are selected in order to try tomake the LU decomposition as sparse as possible, using the strategyidentified by the <B>strategy</B>, <B>abandon_number</B>, and<B>abandon_when</B> parameters.  The possible strategies are<TT>Mod2sparse_first</TT>, <TT>Mod2sparse_mincol</TT>, and<TT>Mod2sparse_minprod</TT>.  If <B>abandon_number</B> is greater thanzero, it is possible that the matrix will appear to have linearlydependent rows when it actually does not.  See the <AHREF="sparse-LU.html">discussion of sparse LU decompositionmethods</A> for details about these strategies.<P>If <B>A</B> is not of rank <I>K</I> or more, <B>L</B> will containsome number less than <I>K</I> of non-zero columns, and <B>U</B> willcontain an equal number of non-zero rows.  The entries in the<B>rows</B> and <B>cols</B> arrays for the extra zero rows or columnswill be arbitrary (but valid).  The number of extra zero columns isreturned as the value of this procedure (hence a return value of zeroindicates that a <I>K</I> by <I>K</I> sub-matrix of full rank wasfound).<P>The matrix <B>A</B> is not altered.  The previous contents of <B>L</B> and <B>U</B> are cleared. <P><A NAME="forward_sub"><HR><B>mod2sparse_forward_sub</B>: Solve a lower-triangular system by forward substitution.</A><BLOCKQUOTE><PRE>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 */)</PRE></BLOCKQUOTE><P>Solves the system of equations <B>Ly</B>=<B>x</B> for <B>y</B> byforward substitution, based on <B>L</B> being lower triangular afterits rows are reordered according to the given index array.  Thevectors <B>x</B> and <B>y</B> are stored unpacked, one bit percharacter.  If <B>L</B> is <I>M</I> by <I>K</I>, then <B>x</B> shouldbe <I>M</I> long, but only the <I>K</I> bits indexed by <B>rows</B>are looked at.  The solution vector, <B>y</B>, must be <I>K</I> long.Only <I>K</I> rows of <B>L</B> are used, as also determined by the<I>K</I> indexes in the <B>rows</B> argument.  If <B>rows</B> is null,the first <I>K</I> rows of <B>L</B> and the first <I>K</I> elements of<B>x</B> are used.<P>If the matrix <B>L</B> does not have 1s on its diagonal (after rowrearrangement), there may be no solution, depending on what <B>x</B>is.  If no solution exists, this procedure returns zero, otherwise itreturns one.  Any arbitrary bits in the solution are set to zero.<P><A NAME="backward_sub"><HR><B>mod2sparse_backward_sub</B>: Solve an upper-triangular system by backward substitution.</A><BLOCKQUOTE><PRE>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 */)</PRE></BLOCKQUOTE><P>Solves <B>Uz</B>=<B>y</B> for <B>z</B> by backward substitution,based on <B>U</B> being upper triangular after its columns arereordered according to the given index array.  The vectors <B>y</B>and <B>z</B> are stored unpacked, one bit per character.  If <B>U</B>is <I>K</I> by <I>N</I>, then the solution vector, <I>z</I>, should be<I>N</I> long, but only the <I>K</I> bits indexed by <B>cols</B> areset.  The vector <B>y</B> must be <I>K</I> long.  Only <I>K</I> columnsof <B>U</B> are used, as also determined by the <I>K</I> indexes inthe <B>cols</B> argument.  The other columns of <B>U</B> must be zero(this is not checked, but is necessary for the method used to work).If <B>cols</B> is null, the first <I>K</I> columns of <B>U</B> and thefirst <I>K</I> elements of <B>z</B> are used.<P>If the  matrix <B>U</B> does  not  have 1s  on its diagonal  (aftercolumn rearrangement) there  may be no  solution, depending on what  yis.  If no solution exists, this procedure  returns zero, otherwise itreturns one.  Any arbitrary bits in the solution are set to zero.<HR><A HREF="index.html">Back to index for LDPC software</A></BODY></HTML>