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

From ApCoCoAWiki

Line 1: | Line 1: | ||

<command> | <command> | ||

− | <title>Slinalg. | + | <title>Slinalg.SGEF</title> |

− | <short_description>Computes the row echelon form of a sparse matrix over F2.</short_description> | + | <short_description>Computes the row echelon form of a sparse matrix over F2 using structured Gaussian Elimination. |

+ | 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.</short_description> | ||

<syntax> | <syntax> | ||

− | Slinalg. | + | Slinalg.SSEF(NRow : INT ,NCol : INT, Mat : LIST, CSteps: STRING): LIST of LIST |

− | |||

</syntax> | </syntax> | ||

<description> | <description> |

## Revision as of 11:11, 6 October 2009

## Slinalg.SGEF

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

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.

### Syntax

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

@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