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
