Difference between revisions of "ApCoCoA-1:Slinalg.SGEF"
| Line 8: | Line 8: | ||
<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. | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
'''Structured Gaussian Elimination:''' Structured Gaussian Elimination has the following four steps: | '''Structured Gaussian Elimination:''' Structured Gaussian Elimination has the following four steps: | ||
| − | (1) | + | (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. | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
Revision as of 11:31, 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: 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.
@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
