ApCoCoA-1:Slinalg.SGEF

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.

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

• Finds isolated solutions using total-degree start systems, multihomogeneous-degree start systems, and also user defined homotopies.
• Implements parameter continuation for families of systems, such as the inverse kinematics of six-revolute serial-link arms, or the forward kinematics of Stewart-Gough parallel-link robots.
• Adaptive multiprecision implemented for finding isolated solutions and for the numerical irreducible decomposition.
• Treats positive-dimensional solutions by computing witness sets.
• Has automatic differentiation which preserves the straightline quality of an input system.
• Uses homogenization to accurately compute solutions at infinity.
• Provides a fractional power-series endgame to accurately compute singular roots.
• Allows for subfunctions.
• Allows for witness set manipulation via both sampling and membership testing.
• Accepts square or nonsquare systems.

• @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

Introduction to CoCoAServer

IML.REF

LinAlg.REF