Difference between revisions of "ApCoCoA-1:Slinalg.SGEF"
| Line 10: | Line 10: | ||
<em>Structured Gaussian Elimination:</em> Structured Gaussian Elimination has the following four steps: | <em>Structured Gaussian Elimination:</em> Structured Gaussian Elimination has the following four steps: | ||
<itemize> | <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><em>Step 1:</em> 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><em>Step 2:</em> 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><em>Step 3:</em> 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> | + | <item><em>Step 4:</em> 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> | </itemize> | ||
After performing the four steps above we apply usual Gaussian Elimination, specially on heavy part of the matrix. | After performing the four steps above we apply usual Gaussian Elimination, specially on heavy part of the matrix. | ||
Revision as of 15:51, 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:
Step 1: Delete all columns that have a single non-zero coefficient and the rows in which those columns have non-zero coefficients.
Step 2: Declare some additional light columns to be heavy, chossing the heaviest ones.
Step 3: Delete some of the rows, selecting those which have the largest number of non-zero elements in the light columns.
Step 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 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
