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

From ApCoCoAWiki
Line 3: Line 3:
 
<short_description>Computes the row echelon form of a sparse matrix over F2 using Structured Gaussian Elimination.</short_description>
 
<short_description>Computes the row echelon form of a sparse matrix over F2 using Structured Gaussian Elimination.</short_description>
 
<syntax>
 
<syntax>
Slinalg.SGEF(NRow : INT ,NCol : INT, Mat : LIST, CSteps: STRING): LIST of LIST
+
Slinalg.SGEF(NRow:INT ,NCol:INT, Mat:LIST, CSteps:STRING):LIST of LIST
 
</syntax>
 
</syntax>
 
<description>
 
<description>
 
<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/>
 
+
<em>Structured Gaussian Elimination:</em> Structured Gaussian Elimination has the following four steps:
'''Structured Gaussian Elimination:''' Structured Gaussian Elimination has the following four steps:
+
<itemize>
 
+
<item>Delete all columns that have a single non-zero coefficient and the rows in which those columns have non-zero coefficients.</item>
(1) Delete all columns that have a single non-zero coefficient and the rows in which those columns have non-zero coefficients.
+
<item>Declare some additional light columns to be heavy, chossing the heaviest ones.</item>
 
+
<item>Delete some of the rows, selecting those which have the largest number of non-zero elements in the light columns.</item>
(2) Declare some additional light columns to be heavy, chossing the heaviest ones.
+
<item>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>
(3) Delete some of the rows, selecting those which have the largest number of non-zero elements in the light columns.  
+
After performing the four steps above we apply usual Gaussian Elimination, specially on heavy part of the matrix.
 
 
(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 above four steps we apply usuall Gaussian Elimination, specially on 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>
 
 
<item>@param <em>NCol</em>: Number of Columns of the matrix.</item>
 
<item>@param <em>NCol</em>: Number of Columns of the matrix.</item>
 
<item>@param <em>Mat</em>: List of lists containing positions of non zero elements.</item>
 
<item>@param <em>Mat</em>: List of lists containing positions of non zero elements.</item>
<item>@param <em>CSteps</em>: The parameter CSetps lets you specify which steps of the sturctured Gaussian Elimination you want to use.
+
<item>@param <em>CSteps</em>: The parameter CSetps lets you specify which steps of the structured Gaussian Elimination you want to use.</item>
 +
<item>@return A list of lists containing the row echelon form of the matrix.</item>
 +
</itemize>
  
If CSteps is set to <quotes>GE</quotes> Then this function is the same as slinalg.SEF(NRow, NCol, SMat).
+
We have to distinguish the following cases:
 
+
<itemize>
If CSteps is set to <quotes>GE_v2</quotes> Then this function is the same as slinalg.SEF_v2(NRow, NCol, SMat).
+
<item>CSteps is set to <quotes>GE</quotes>: Then this function is the same as <ref>Slinalg.SEF</ref>.</item>
 
+
<item>CSteps is set to <quotes>GE_v2</quotes>: Then this function is the same as <ref>Slinalg.SEF</ref>.</item>
If CSteps is set to <quotes>SGE0</quotes> Then it performs the follwing:
+
<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>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>
loop
+
<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>
  Step 2
+
</itemize>
  Step 4
 
End
 
 
 
and at the end it perfoms usuall Gaussian Elimination.
 
 
 
If CSteps is set to <quotes>SGE1</quotes> Then it performs the follwing:
 
 
 
Step 1
 
 
 
loop
 
  Step 2
 
  Step 4
 
End
 
  
and at the end it performs usuall Gaussian Elimination.
 
 
If CSteps is set to <quotes>SGE2</quotes> Then it performs the follwing:
 
 
Step 1
 
 
loop
 
  Step 2
 
  Step 4
 
End
 
 
Step 1
 
 
Step 3
 
 
and at the end it perfoms usuall Gaussian Elimination.</item>
 
<item>@return A list of lists containing the row echelon form of the matrix.</item>
 
</itemize>
 
 
 
<example>
 
<example>
 
Use ZZ/(2)[x];
 
Use ZZ/(2)[x];

Revision as of 15:49, 14 October 2009

Slinalg.SGEF

Computes the row echelon form of a sparse matrix over F2 using Structured Gaussian Elimination.

Syntax

Slinalg.SGEF(NRow:INT ,NCol:INT, Mat:LIST, CSteps:STRING):LIST of 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.

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

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

  • Declare some additional light columns to be heavy, chossing the heaviest ones.

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

  • 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 heavy part of the matrix.

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

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

  • @param Mat: 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.

We have to distinguish the following cases:

  • CSteps is set to "GE": Then this function is the same as Slinalg.SEF.

  • CSteps is set to "GE_v2": Then this function is the same as Slinalg.SEF.

  • 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

Use ZZ/(2)[x];
NRow := 10;
NCol := 13;
CSteps:=<quotes>GE_v2</quotes>;
Mat := [[1, 2, 6, 7],
      [1, 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]];
  
  $apcocoa/slinalg.SGEF(NRow, NCol, Mat, CSteps);
  [[1, 2, 6, 7],
   [2, 3], 
   [3, 10, 11, 13],
   [4, 5, 7],
   [5, 6, 8],
   [6, 10, 12],
   [8, 9],
   [10, 11],
   [11, 13]]	
-------------------------------

Example

NRow := 10;
NCol := 13;
CSteps:=<quotes>SGE1</quotes>;
Mat := [[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]];
  
  $apcocoa/slinalg.SGEF(NRow, NCol, Mat, CSteps);
  [[2, 3],
   [3, 13],
   [10, 11],
   [11, 13]]


Example

NRow := 10;
NCol := 13;
CSteps:=<quotes>SGE2</quotes>;
Mat := [[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]];
  
  $apcocoa/slinalg.SGEF(NRow, NCol, Mat, CSteps);
   [ ]




See also

Introduction to CoCoAServer

IML.REF

LinAlg.REF