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

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: | |

− | + | <itemize> | |

− | + | <item>Delete all columns that have a single non-zero coefficient and the rows in which those columns have non-zero coefficients.</item> | |

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

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

− | + | After performing the four steps above we apply usual Gaussian Elimination, specially on heavy part of the matrix. | |

− | |||

− | |||

− | |||

− | After performing | ||

− | |||

− | |||

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

− | + | We have to distinguish the following cases: | |

− | + | <itemize> | |

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

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

− | + | </itemize> | |

− | |||

− | End | ||

− | |||

− | and at the end it | ||

− | |||

− | |||

− | |||

− | Step 1 | ||

− | |||

− | loop | ||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

<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