5.1.3 bareiss

Syntax:

bareiss ( module_expression )
bareiss ( matrix_expression )
bareiss ( module_expression, int_expression, int_expression )
bareiss ( matrix_expression, int_expression, int_expression )

Type:

list of module and intvec

Purpose:

applies the sparse Gauss-Bareiss algorithm (see References, Lee and Saunders) to a module (or with type conversion to a matrix) with an 'optimal' pivot strategy. The vectors of the module are the columns of the matrix, hence elimination takes place w.r.t. rows.
With only one parameter a complete elimination is done. Result is a list: the first entry is a module with a minimal independent set of vectors (as a matrix lower triangular), the second entry an intvec with the permutation of the rows w.r.t. the original matrix, that is, a k at position l indicates that row k was carried over to the row l.
The further parameters control the algorithm. bareiss(M,i,j) does not attempt to diagonalize the last i rows in the elimination procedure and stops computing when the remaining number of vectors (columns) to reduce is at most j.

Example:

ring r=0,(x,y,z),(c,dp); module mm; // ** generation of the module mm ** int d=7; int b=2; int db=d-b; int i; for(i=d;i>0;i--){ mm[i]=3*x*gen(i); } for(i=db;i;i--){ mm[i]=mm[i]+7*y*gen(i+b); } for(i=d;i>db;i--){ mm[i]=mm[i]+7*y*gen(i-db); } for(i=d;i>b;i--){ mm[i]=mm[i]+11*z*gen(i-b); } for(i=b;i;i--){ mm[i]=mm[i]+11*z*gen(i+db); } // ** the generating matrix of mm ** print(mm); ==> 3x, 0, 11z,0, 0, 7y, 0, ==> 0, 3x, 0, 11z,0, 0, 7y, ==> 7y, 0, 3x, 0, 11z,0, 0, ==> 0, 7y, 0, 3x, 0, 11z,0, ==> 0, 0, 7y, 0, 3x, 0, 11z, ==> 11z,0, 0, 7y, 0, 3x, 0, ==> 0, 11z,0, 0, 7y, 0, 3x // complete elimination list ss=bareiss(mm); print(ss[1]); ==> 7y, 0, 0, 0, 0, 0, 0, ==> 3x, -33xz, 0, 0, 0, 0, 0, ==> 11z,-121z2,1331z3,0, 0, 0, 0, ==> 0, 0, 0, 9317yz3,0, 0, 0, ==> 0, 21xy, _[5,3],14641z4,-43923xz4,0, 0, ==> 0, 0, 0, 0, 65219y2z3,_[6,6],0, ==> 0, 49y2, _[7,3],3993xz3,_[7,5], _[7,6],_[7,7] ss[2]; ==> 2,7,5,1,4,3,6 // elimination up to 3 vectors ss=bareiss(mm,0,3); print(ss[1]); ==> 7y, 0, 0, 0, 0, 0, 0, ==> 3x, -33xz, 0, 0, 0, 0, 0, ==> 11z,-121z2,1331z3,0, 0, 0, 0, ==> 0, 0, 0, 9317yz3,0, 0, 0, ==> 0, 0, 0, 0, 27951xyz3,102487yz4,65219y2z3, ==> 0, 21xy, _[6,3],14641z4,_[6,5], _[6,6], -43923xz4, ==> 0, 49y2, _[7,3],3993xz3,_[7,5], _[7,6], _[7,7] ss[2]; ==> 2,7,5,1,3,4,6 // elimination without the last 3 rows ss=bareiss(mm,3,0); print(ss[1]); ==> 7y, 0, 0, 0, 0, 0, 0, ==> 0, 77yz,0, 0, 0, 0, 0, ==> 0, 0, 231xyz, 0, 0, 0, 0, ==> 0, 0, 0, 1617xy2z,0, 0, 0, ==> 11z,21xy,-1331z3,14641z4, _[5,5],_[5,6],_[5,7], ==> 0, 0, 539y2z, _[6,4], _[6,5],_[6,6],-3773y3z, ==> 3x, 49y2,-363xz2,3993xz3, _[7,5],_[7,6],_[7,7] ss[2]; ==> 2,3,4,1