<h4>3.1 <span class="Heading">The inner workings of <strong class="pkg">Gauss</strong>
sparse matrices</span></h4>
<p>When doing any kind of computation there is a constant conflict between memory load and speed. On the one hand, memory usage is bounded by the total available memory, on the other hand, computation time should also not exceed certain proportions. Memory usage and CPU time are generally inversely proportional, because the computer needs more time to perform operations on a compactified data structure. The idea of sparse matrices mirrors exactly the need for less memory load, therefore it is natural that sparse algorithms take more time than dense ones. However, if the matrix is sufficiently large and sparse at the same time, sparse algorithms can easily be faster than dense ones while maintaining minimal memory load.</p>
<p>It should be noted that, although matrices that appear naturally in homological algebra are almost always sparse, they do not have to stay sparse under (R)REF algorithms, especially when the computation is concerned with transformation matrices. Therefore, in a perfect world there should be ways implemented to not only find out which data structure to use, but also at what point to convert from one to the other. This was, however, not the aim of the <strong class="pkg">Gauss</strong> package and is just one of many points in which this package could be optimized or extended. Take a look at this matrix <span class="SimpleMath">\(M\)</span>:</p>
<p>The matrix <span class="SimpleMath">\(M\)</span> carries the same information as the following table, if and only if you know how many rows and columns the matrix has. There is also the matter of the base ring, but this is not important for now:</p>
<p>This table relates each index tuple to its nonzero entry, all other matrix entries are defined to be zero. This only works for known dimensions of the matrix, otherwise trailing zero rows and columns could get lost (notice how the table gives no hint about the existence of a 5th column). To convert the above table into a sparse data structure, one could list the table entries in this way:</p>
<p>However, this data structure would not be very efficient. Whenever you are interested in a row <span class="SimpleMath">\(i\)</span> of <span class="SimpleMath">\(M\)</span> (this happens all the time when performing Gaussian elimination) the whole list would have to be searched for 3-tuples of the form <span class="SimpleMath">\([ i, *, * ]\)</span>. This is why I tried to manage the row index by putting the tuples into the corresponding list entry:<br /></p>
<p>As you can see, this looks fairly complicated. However, the same information can be stored in this form, which would become the final data structure for <strong class="pkg">Gauss</strong> sparse matrices:</p>
<p>Although now the number of rows is equal to the Length of both `indices' and `entries', it is still stored in the sparse matrix. Here is the full data structure (--> <code class="func">SparseMatrix</code> (<a href="chap3_mj.html#X829481DA85587996"><span class="RefLink">3.2-1</span></a>)):</p>
<p>As you can see, the matrix stores its ring to be on the safe side. This is especially important for zero matrices, as there is no way to determine the base ring from the sparse matrix structure. For further information on sparse matrix construction and converting, refer to <code class="func">SparseMatrix</code> (<a href="chap3_mj.html#X829481DA85587996"><span class="RefLink">3.2-1</span></a>).</p>
<p>Because the nonzero entries of a matrix over GF(2) are all "1", the entries of M are not stored at all. It is of course crucial that all operations and algorithms make 100% sure that all appearing zero entries are deleted from the `indices' as well as the `entries' list as they arise.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SparseMatrix</code>( <var class="Arg">mat</var>[, <var class="Arg">R</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: a sparse matrix over the ring <var class="Arg">R</var></p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SparseMatrix</code>( <var class="Arg">nrows</var>, <var class="Arg">ncols</var>, <var class="Arg">indices</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: a sparse matrix over GF(2)</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SparseMatrix</code>( <var class="Arg">nrows</var>, <var class="Arg">ncols</var>, <var class="Arg">indices</var>, <var class="Arg">entries</var>[, <var class="Arg">R</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: a sparse matrix over the ring <var class="Arg">R</var></p>
<p>The sparse matrix constructor. In the one-argument form the SparseMatrix constructor converts a <strong class="pkg">GAP</strong> matrix to a sparse matrix. If not provided the base ring <var class="Arg">R</var> is found automatically. For the multi-argument form <var class="Arg">nrows</var> and <var class="Arg">ncols</var> are the dimensions of the matrix. <var class="Arg">indices</var> must be a list of length <var class="Arg">nrows</var> containing lists of the column indices of the matrix in ascending order.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ConvertSparseMatrixToMatrix</code>( <var class="Arg">sm</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p>Returns: a <strong class="pkg">GAP</strong> matrix, [], or a list of empty lists</p>
<p>This function converts the sparse matrix <var class="Arg">sm</var> into a <strong class="pkg">GAP</strong> matrix. In case of <code class="code">nrows(sm)=0</code> or <code class="code">ncols(sm)=0</code> the return value is the empty list or a list of empty lists, respectively.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AddToEntry</code>( <var class="Arg">sm</var>, <var class="Arg">i</var>, <var class="Arg">j</var>, <var class="Arg">elm</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or a ring element</p>
<p>AddToEntry adds the element <var class="Arg">elm</var> to the sparse matrix <var class="Arg">sm</var> at the <var class="Arg">(i,j)</var>-th position. This is a Method with a side effect which returns true if you tried to add zero or the sum of <code class="code">sm[i,j]</code> and <var class="Arg">elm</var> otherwise. Please use this method whenever possible.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SparseZeroMatrix</code>( <var class="Arg">nrows</var>[, <var class="Arg">ring</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: a sparse <<var class="Arg">nrows</var> x <var class="Arg">nrows</var>> zero matrix over the ring <var class="Arg">ring</var></p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SparseZeroMatrix</code>( <var class="Arg">nrows</var>, <var class="Arg">ncols</var>[, <var class="Arg">ring</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: a sparse <<var class="Arg">nrows</var> x <var class="Arg">ncols</var>> zero matrix over the ring <var class="Arg">ring</var></p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SparseIdentityMatrix</code>( <var class="Arg">dim</var>[, <var class="Arg">ring</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: a sparse <<var class="Arg">dim</var> x <var class="Arg">dim</var>> identity matrix over the ring <var class="Arg">ring</var>. If no ring is specified (one should try to avoid this if possible) the Rationals are the default ring.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Nrows</code>( <var class="Arg">sm</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p>Returns: the number of rows of the sparse matrix <var class="Arg">sm</var>. This should be preferred to the equivalent <code class="code">sm!.nrows</code>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Ncols</code>( <var class="Arg">sm</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p>Returns: the number of columns of the sparse matrix <var class="Arg">sm</var>. This should be preferred to the equivalent <code class="code">sm!.ncols</code>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IndicesOfSparseMatrix</code>( <var class="Arg">sm</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p>Returns: the indices of the sparse matrix <var class="Arg">sm</var> as a ListList. This should be preferred to the equivalent <code class="code">sm!.indices</code>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ EntriesOfSparseMatrix</code>( <var class="Arg">sm</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p>Returns: the entries of the sparse matrix <var class="Arg">sm</var> as a ListList of ring elements. This should be preferred to the equivalent <code class="code">sm!.entries</code> and has the additional advantage of working for sparse matrices over GF(2) which do not have any entries.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RingOfDefinition</code>( <var class="Arg">sm</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p>Returns: the base ring of the sparse matrix <var class="Arg">sm</var>. This should be preferred to the equivalent <code class="code">sm!.ring</code>.</p>
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung ist noch experimentell.
