ApCoCoA-1:Slinalg.SGEF

Slinalg.SGEF

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

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.

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, chossing 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 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.

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:=<quotes>SGE1</quotes>;
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:=<quotes>SGE0</quotes>;
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:=<quotes>SGE2</quotes>;
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