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

Line 1: | Line 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>Computes the row echelon form of a sparse matrix over F2 using structured Gaussian Elimination.</short_description> |

+ | <syntax> | ||

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

+ | </syntax> | ||

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

− | + | <par/> | |

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

(1) Delete all columns that have a single non-zero coefficient and the rows in | (1) Delete all columns that have a single non-zero coefficient and the rows in | ||

Line 15: | Line 21: | ||

After performing above four steps we apply usuall Gaussian Elimination, specially on | After performing above four steps we apply usuall Gaussian Elimination, specially on | ||

− | heavy part of the matrix.</ | + | heavy part of the matrix. |

− | < | + | <par/> |

− | + | ||

− | </ | + | |

− | < | + | <par/> |

− | < | + | This function allows you to compute a (reduced) row echelon form of <tt>M</tt> over a finite field. If you want to use the first version without the parameter <tt>P</tt>, the components of the input matrix <tt>M</tt> must be of type <tt>ZMOD</tt> and your current working ring must be the same ring over which <tt>M</tt> has been defined. The second version of this function lets you compute a (reduced) row echelon form of <tt>M</tt> mod <tt>P</tt> and the components of <tt>M</tt> must be of type <tt>INT</tt>. |

+ | <par/> | ||

<itemize> | <itemize> |

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

## Slinalg.SGEF

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

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

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.

This function allows you to compute a (reduced) row echelon form of `M` over a finite field. If you want to use the first version without the parameter `P`, the components of the input matrix `M` must be of type `ZMOD` and your current working ring must be the same ring over which `M` has been defined. The second version of this function lets you compute a (reduced) row echelon form of `M` mod `P` and the components of `M` must be of type `INT`.

@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