📄 sparse-lu.html
字号:
<HTML><HEAD><TITLE> Sparse LU Decomposition Methods </TITLE></HEAD><BODY><H1> Sparse LU Decomposition Methods </H1><P>The sparse modulo-2 matrix LU decomposition routine <AHREF="mod2sparse.html#decomp"><TT>mod2sparse_decomp</TT></A> (whichis used by the <A HREF="encoding.html#make-gen"><TT>make-gen</TT></A>program when it is asked to create a sparse generator matrix) tries tofind an sub-matrix of a matrix (for <TT>make-gen</TT>, the paritycheck matrix), and an ordering of rows and columns for thissub-matrix, that leads to the lower-triangular matrix <B>L</B> and theupper-triangular matrix <B>U</B> making up the LU decomposition beingas sparse as possible. Finding an optimal solution is too difficult,so instead a heuristic strategy is used. <P>The overall algorithm finds <B>L</B> and <B>U</B> a column at atime, from left to right (as reordered, in the case of <B>U</B>). Asthis is done, a copy, <B>B</B>, of the original matrix is modified.To create column <I>i</I> of <B>L</B> and <B>U</B>, some element withvalue 1 in <B>B</B> whose row and column indexes, after reordering,are both greater than <I>i</I> is found. The row and column of thiselement are considered to come next in the reordering, and thecontents of the column containing this element is copied to <B>L</B>and <B>U</B> (upper elements going to <B>U</B>, lower to <B>L</B>).The row containing this element is then added to some later rows so asto clear the lower part of this column to zeros.<P>At the first step of this process - selecting an element with value1 from the later rows and columns - there will often be severalpossibilities. Different choices can lead to the final result beingmore or less sparse. The possible strategies for picking an elementare identified by the constants <TT>Mod2sparse_first</TT>,<TT>Mod2sparse_mincol</TT>, and <TT>Mod2sparse_minprod</TT>. Thesestrategies operate as follows:<P><TT>Mod2sparse_first</TT><BLOCKQUOTE>Select the first element with value 1 that is encountered in a topto bottom, left to right search.</BLOCKQUOTE><P><TT>Mod2sparse_mincol</TT><BLOCKQUOTE>Select the first element with value 1 that is contained in a columnof <B>B</B> that has the smallest number of 1s of any column.</BLOCKQUOTE><P><TT>Mod2sparse_minprod</TT><BLOCKQUOTE>Select an element with value 1 for which the product of the number of1s in that row of <B>B</B> minus one times the number of 1s in thatcolumn of <B>B</B> minus one is as small as possible.</BLOCKQUOTE><P>The <B>abandon_number</B> and <B>abandon_when</B> parameters canmodify the basic strategy. If <B>abandon_number</B> is greater thanzero, then after <B>abandon_when</B> columns have been selected,<B>abandon_number</B> of the remaining columns are abandoned ascandidates for possible future selection, the abandoned columns beingthose with the greatest number of entries. Abandoning such columnssaves space and time, but may make the final result less sparse thanit would otherwise be, and can possibly result in the matrix appearingto have lower rank than it actually has.<P>The methods described here are fairly straightforward adaptationsof standard methods for sparse square matrices of reals, as described, for example, in <BLOCKQUOTE> I. S. Duff, A. M. Erisman, J. K. Reid (1986) <I>Direct Methods for Sparse Matrices</I>, Oxford: Clarendon Press.</BLOCKQUOTE>In the coding context, however, we are interested in matrices ofmodulo-2 elements, and it is enough to find a sparse LU decompositionof any square sub-matrix that can be obtained by selecting columns ofthe rectangular parity check matrix. I talked about the applicationof sparse matrix methods to encoding of LDPC codes at the 1999 IMAworkshop on Codes, Systems and Graphical Models (see the <AHREF="refs.html">references</A>).<HR><A HREF="index.html">Back to index for LDPC software</A></BODY></HTML>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -