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

From ApCoCoAWiki
Line 18: Line 18:
  
 
(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.
 
(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.
  
  

Revision as of 12:14, 6 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:

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

(2) Declare some additional light columns to be heavy, chossing the heaviest ones.

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

(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.


  • @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.

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

Example

Use ZZ/(2)[x];
NRow:=10;
NCol:=13;
M := [[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]];

Slinalg.SEF(NRow, NCol, M);
[[1,2,6,7],
 [2,3],
 [3,4,6,7,9,10],
 [4,5,7],
 [5,6,8],
 [6,8,9,10,12],
 [8,9,11,13],
 [10,11],
 [11,13]]
	
-------------------------------




See also

Introduction to CoCoAServer

IML.REF

LinAlg.REF