Difference between revisions of "ApCoCoA-1:Slinalg.SGEF"

From ApCoCoAWiki
m (replaced <quotes> tag by real quotes)
 
(8 intermediate revisions by 3 users not shown)
Line 1: Line 1:
 +
{{Version|1}}
 
<command>
 
<command>
 
<title>Slinalg.SGEF</title>
 
<title>Slinalg.SGEF</title>
<short_description>Computes the row echelon form of a sparse matrix over F2 using Structured Gaussian Elimination.</short_description>
+
<short_description>Performs specified steps of structured gaussian elimination on a sparse matrix over F2.</short_description>
 
<syntax>
 
<syntax>
 
Slinalg.SGEF(NRow:INT, NCol:INT, M:LIST, CSteps:STRING):LIST
 
Slinalg.SGEF(NRow:INT, NCol:INT, M:LIST, CSteps:STRING):LIST
Line 8: Line 9:
 
<em>Please note:</em> The function(s) explained on this page is/are using the <em>ApCoCoAServer</em>. You will have to start the ApCoCoAServer in order to use it/them.
 
<em>Please note:</em> The function(s) explained on this page is/are using the <em>ApCoCoAServer</em>. You will have to start the ApCoCoAServer in order to use it/them.
 
<par/>
 
<par/>
 +
This function does some experiments on calculating row echelon form of a matrix using structured gaussian elimination. Please be careful while using this function because some columns and rows are deleted from the matrix. Some times the echelon form may not contain all the required information. The best possibility to compute echelon form is to set the parameter CSteps to "SGE1".
 +
<par/>
 
<em>Structured Gaussian Elimination:</em> Structured Gaussian Elimination has the following four steps:
 
<em>Structured Gaussian Elimination:</em> Structured Gaussian Elimination has the following four steps:
 
<itemize>
 
<itemize>
 
<item><em>Step 1:</em> Delete all columns that have a single non-zero coefficient and the rows in which those columns have non-zero coefficients.</item>
 
<item><em>Step 1:</em> Delete all columns that have a single non-zero coefficient and the rows in which those columns have non-zero coefficients.</item>
<item><em>Step 2:</em> Declare some additional light columns to be heavy, chossing the heaviest ones.</item>
+
<item><em>Step 2:</em> Declare some additional light columns to be "heavy", choosing the heaviest ones.</item>
 
<item><em>Step 3:</em> Delete some of the rows, selecting those which have the largest number of non-zero elements in the light columns.</item>
 
<item><em>Step 3:</em> Delete some of the rows, selecting those which have the largest number of non-zero elements in the light columns.</item>
 
<item><em>Step 4:</em> For any row which has only a single non-zero coefficient equal to 1 in the light column, subtract appropriate multiples of that row from all other rows that have non-zero coefficients on that column so as to make those coefficients 0.</item>
 
<item><em>Step 4:</em> For any row which has only a single non-zero coefficient equal to 1 in the light column, subtract appropriate multiples of that row from all other rows that have non-zero coefficients on that column so as to make those coefficients 0.</item>
 
</itemize>
 
</itemize>
After performing the four steps above we apply usual Gaussian Elimination, specially on heavy part of the matrix.
+
After performing the four steps above we apply usual Gaussian Elimination, specially on the heavy part of the matrix.
 
<itemize>
 
<itemize>
 
<item>@param <em>NRow</em>: Number of rows of the matrix.</item>
 
<item>@param <em>NRow</em>: Number of rows of the matrix.</item>
Line 24: Line 27:
 
</itemize>
 
</itemize>
  
We have to distinguish the following cases:
+
For the parameter <tt>CSteps</tt> we have to distinguish the following cases:
 
<itemize>
 
<itemize>
<item>CSteps is set to <quotes>GE</quotes>: Then this function is the same as <ref>Slinalg.SEF</ref>.</item>
+
<item><tt>CSteps</tt> is set to "SGE0": Then it performs the following: <tt>{loop Step 2, Step 4 End}</tt> and at the end it performs usual Gaussian Elimination.</item>
<item>CSteps is set to <quotes>GE_v2</quotes>: Then this function is the same as <ref>Slinalg.SEF</ref>.</item>
+
<item><tt>CSteps</tt> is set to "SGE1": Then it performs the following: <tt>{Step 1, {loop Step 2, Step 4 End}}</tt> and at the end it performs usual Gaussian Elimination.</item>
<item>CSteps is set to <quotes>SGE0</quotes>: Then it performs the following: <tt>{loop Step 2, Step 4 End}</tt> and at the end it performs usual Gaussian Elimination.</item>
+
<item><tt>CSteps</tt> is set to "SGE2": Then it performs the following: <tt>{Step 1, {loop Step 2, Step 4 End}, Step 1, Step 3}</tt> and at the end it performs usual Gaussian Elimination.</item>
<item>CSteps is set to <quotes>SGE1</quotes>: Then it performs the following: <tt>{Step 1, {loop Step 2, Step 4 End}}</tt> and at the end it performs usual Gaussian Elimination.</item>
 
<item>CSteps is set to <quotes>SGE2</quotes>: Then it performs the following: <tt>{Step 1, {loop Step 2, Step 4 End}, Step 1, Step 3}</tt> and at the end it performs usual Gaussian Elimination.</item>
 
 
</itemize>  
 
</itemize>  
 +
  
 
<example>
 
<example>
Use ZZ/(2)[x];
 
 
NRow := 10;
 
NRow := 10;
 
NCol := 13;
 
NCol := 13;
CSteps:=<quotes>GE_v2</quotes>;
+
CSteps:="SGE1";
 
M := [[1, 2, 6, 7],
 
M := [[1, 2, 6, 7],
       [1, 2, 4, 5, 6],  
+
       [ 2, 4, 5, 6],  
 
       [2, 3],  
 
       [2, 3],  
 
       [2, 3, 10, 11],  
 
       [2, 3, 10, 11],  
Line 50: Line 51:
 
    
 
    
 
   Slinalg.SGEF(NRow, NCol, M, CSteps);
 
   Slinalg.SGEF(NRow, NCol, M, CSteps);
   [[1, 2, 6, 7],
+
   [[2, 3],
  [2, 3],  
+
   [3, 13],
   [3, 10, 11, 13],
 
  [4, 5, 7],
 
  [5, 6, 8],
 
  [6, 10, 12],
 
  [8, 9],
 
 
   [10, 11],
 
   [10, 11],
   [11, 13]]
+
   [11, 13]]
-------------------------------
 
 
 
 
</example>
 
</example>
  
Line 66: Line 60:
 
NRow := 10;
 
NRow := 10;
 
NCol := 13;
 
NCol := 13;
CSteps:=<quotes>SGE1</quotes>;
+
CSteps:="SGE0";
 
M := [[1, 2, 6, 7],
 
M := [[1, 2, 6, 7],
 
       [ 2, 4, 5, 6],  
 
       [ 2, 4, 5, 6],  
Line 79: Line 73:
 
    
 
    
 
   Slinalg.SGEF(NRow, NCol, M, CSteps);
 
   Slinalg.SGEF(NRow, NCol, M, CSteps);
  [[2, 3],
+
[[1, 2, 6, 7],
  [3, 13],
+
[2, 4, 5, 6],
  [10, 11],
+
[3, 4, 5, 6],
  [11, 13]]
+
[4, 5, 6, 13],
 
+
[5, 7, 9, 10],
 +
[6, 7, 8, 9, 10],
 +
[7, 8, 9, 12],
 +
[8, 9],
 +
[10, 11],
 +
[11, 13]]
 
</example>
 
</example>
 
  
 
<example>
 
<example>
 
NRow := 10;
 
NRow := 10;
 
NCol := 13;
 
NCol := 13;
CSteps:=<quotes>SGE2</quotes>;
+
CSteps:="SGE2";
 
M := [[1, 2, 6, 7],
 
M := [[1, 2, 6, 7],
 
       [ 2, 4, 5, 6],  
 
       [ 2, 4, 5, 6],  
Line 104: Line 102:
 
   Slinalg.SGEF(NRow, NCol, M, CSteps);
 
   Slinalg.SGEF(NRow, NCol, M, CSteps);
 
   [ ]
 
   [ ]
 
 
</example>
 
</example>
 
 
 
  
 
</description>
 
</description>
Line 117: Line 111:
  
 
<seealso>
 
<seealso>
  <see>Introduction to CoCoAServer</see>
+
  <see>ApCoCoA-1:Introduction to CoCoAServer|Introduction to CoCoAServer</see>
  <see>IML.REF</see>
+
  <see>ApCoCoA-1:IML.REF|IML.REF</see>
   <see>LinAlg.REF</see>
+
   <see>ApCoCoA-1:LinAlg.REF|LinAlg.REF</see>
 
</seealso>
 
</seealso>
  
<key>slinalg.sef</key>
+
<key>slinalg.sgef</key>
<key>sef</key>
+
<key>sgef</key>
 
<key>sparse matrix</key>
 
<key>sparse matrix</key>
<wiki-category>Package_slinalg</wiki-category>
+
<wiki-category>ApCoCoA-1:Package_slinalg</wiki-category>
 
</command>
 
</command>

Latest revision as of 13:50, 29 October 2020

This article is about a function from ApCoCoA-1.

Slinalg.SGEF

Performs specified steps of structured gaussian elimination on a sparse matrix over F2.

Syntax

Slinalg.SGEF(NRow:INT, NCol:INT, M:LIST, CSteps:STRING):LIST

Description

Please note: The function(s) explained on this page is/are using the ApCoCoAServer. You will have to start the ApCoCoAServer in order to use it/them.

This function does some experiments on calculating row echelon form of a matrix using structured gaussian elimination. Please be careful while using this function because some columns and rows are deleted from the matrix. Some times the echelon form may not contain all the required information. The best possibility to compute echelon form is to set the parameter CSteps to "SGE1".

Structured Gaussian Elimination: Structured Gaussian Elimination has the following four steps:

  • Step 1: Delete all columns that have a single non-zero coefficient and the rows in which those columns have non-zero coefficients.

  • Step 2: Declare some additional light columns to be "heavy", choosing the heaviest ones.

  • Step 3: Delete some of the rows, selecting those which have the largest number of non-zero elements in the light columns.

  • Step 4: For any row which has only a single non-zero coefficient equal to 1 in the light column, subtract appropriate multiples of that row from all other rows that have non-zero coefficients on that column so as to make those coefficients 0.

After performing the four steps above we apply usual Gaussian Elimination, specially on the heavy part of the matrix.

  • @param NRow: Number of rows of the matrix.

  • @param NCol: Number of Columns of the matrix.

  • @param M: List of lists containing positions of non zero elements.

  • @param CSteps: The parameter CSetps lets you specify which steps of the Structured Gaussian Elimination you want to use.

  • @return A list of lists containing the row echelon form of the matrix.

For the parameter CSteps we have to distinguish the following cases:

  • CSteps is set to "SGE0": Then it performs the following: {loop Step 2, Step 4 End} and at the end it performs usual Gaussian Elimination.

  • CSteps is set to "SGE1": Then it performs the following: {Step 1, {loop Step 2, Step 4 End}} and at the end it performs usual Gaussian Elimination.

  • CSteps is set to "SGE2": Then it performs the following: {Step 1, {loop Step 2, Step 4 End}, Step 1, Step 3} and at the end it performs usual Gaussian Elimination.


Example

NRow := 10;
NCol := 13;
CSteps:="SGE1";
M := [[1, 2, 6, 7],
      [ 2, 4, 5, 6], 
      [2, 3], 
      [2, 3, 10, 11], 
      [2, 4, 6, 7, 9, 10], 
      [2, 10, 11, 13], 
      [5, 6, 8],
      [ 6, 8, 9,10,12],
      [6, 10, 12], 
      [10, 13]];
  
  Slinalg.SGEF(NRow, NCol, M, CSteps);
  [[2, 3],
   [3, 13],
   [10, 11],
   [11, 13]]

Example

NRow := 10;
NCol := 13;
CSteps:="SGE0";
M := [[1, 2, 6, 7],
      [ 2, 4, 5, 6], 
      [2, 3], 
      [2, 3, 10, 11], 
      [2, 4, 6, 7, 9, 10], 
      [2, 10, 11, 13], 
      [5, 6, 8],
      [ 6, 8, 9,10,12],
      [6, 10, 12], 
      [10, 13]];
  
  Slinalg.SGEF(NRow, NCol, M, CSteps);
[[1, 2, 6, 7],
 [2, 4, 5, 6],
 [3, 4, 5, 6],
 [4, 5, 6, 13],
 [5, 7, 9, 10],
 [6, 7, 8, 9, 10],
 [7, 8, 9, 12],
 [8, 9],
 [10, 11],
 [11, 13]]

Example

NRow := 10;
NCol := 13;
CSteps:="SGE2";
M := [[1, 2, 6, 7],
      [ 2, 4, 5, 6], 
      [2, 3], 
      [2, 3, 10, 11], 
      [2, 4, 6, 7, 9, 10], 
      [2, 10, 11, 13], 
      [5, 6, 8],
      [ 6, 8, 9,10,12],
      [6, 10, 12], 
      [10, 13]];
  
  Slinalg.SGEF(NRow, NCol, M, CSteps);
   [ ]



See also

Introduction to CoCoAServer

IML.REF

LinAlg.REF