|
5.1.3 bareiss
qcindex Gauss
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
|
See
det;
matrix.
|