|
#############################################################################
##
#W pcppara.gi Polycyc Bettina Eick
#W Werner Nickel
##
## Parallel versions of the non-commuatative gauss algorithm.
##
#############################################################################
##
#F UpdateCounterPara( ind, c ) . . . . . . . . . . . . small help function
##
BindGlobal( "UpdateCounterPara", function( ind, c )
local i;
i := c - 1;
while i > 0 and not IsBool(ind[i]) and LeadingExponent(ind[i]) = 1 do
i := i - 1;
od;
return i + 1;
end );
#############################################################################
##
#F AddToIgsParallel( <pcs>, <gens>, <ppcs>, <pgens> )
##
## This function adds the elements in <gens> to the induced pcs <pcs>.
## It acts simultaneously on <pcs> and <ppcs> as well as <gens> and <pgens>.
##
InstallGlobalFunction( AddToIgsParallel,
function( pcs, gens, ppcs, pgens )
local coll, rels, n, id, todo, tododo, ind, indd, g, gg, d, h, hh, k,
eg, eh, e, changed, c, i, r, sub;
if Length( gens ) = 0 then return [pcs, ppcs]; fi;
# get information
coll := Collector( gens[1] );
rels := RelativeOrders( coll );
n := NumberOfGenerators( coll );
id := gens[1]^0;
# create new list from pcs/ppcs
ind := List( [1..n], x -> false );
indd := List( [1..n], x -> false );
for i in [1..Length(pcs)] do
d := Depth( pcs[i] );
ind[d] := pcs[i];
indd[d] := ppcs[i];
od;
# set counter
c := UpdateCounterPara( ind, n+1 );
# create a to-do list from gens/pgens
sub := Filtered( [1..Length(gens)], x -> Depth(gens[x]) < c );
todo := gens{sub};
tododo:= pgens{sub};
# loop over to-do list until it is empty
while Length( todo ) > 0 and c > 1 do
g := Remove(todo);
gg := Remove(tododo);
d := Depth( g );
# shift g into ind
changed := [];
while d < c do
h := ind[d];
hh := indd[d];
if not IsBool( h ) then
# reduce g with h
eg := LeadingExponent( g );
eh := LeadingExponent( h );
e := Gcdex( eg, eh );
# adjust ind[d] by gcd
ind[d] := (g^e.coeff1) * (h^e.coeff2);
indd[d] := (gg^e.coeff1) * (hh^e.coeff2);
if e.coeff1 <> 0 then Add( changed, d ); fi;
# adjust g
g := (g^e.coeff3) * (h^e.coeff4);
gg := (gg^e.coeff3) * (hh^e.coeff4);
else
# just add g into ind
ind[d] := g;
indd[d] := gg;
g := g^0;
gg := gg^0;
Add( changed, d );
fi;
c := UpdateCounterPara( ind, c );
d := Depth( g );
od;
for d in changed do
g := ind[d];
gg := indd[d];
if d <= Length( rels ) and rels[d] > 0 then
r := RelativeOrderPcp( g );
k := g ^ r;
if Depth(k) < c then
Add( todo, k );
Add( tododo, gg^r );
fi;
fi;
for i in [1..Length(ind)] do
if not IsBool( ind[i] ) then
k := Comm( g, ind[i] );
if Depth(k) < c then
Add( todo, k );
Add( tododo, Comm( gg, indd[i] ) );
fi;
fi;
od;
od;
od;
# return resulting list
return [Filtered( ind, x -> not IsBool( x ) ),
Filtered( indd, x -> not IsBool( x ) ) ];
end );
#############################################################################
##
## IgsParallel( <gens>, <pre> )
##
InstallGlobalFunction( IgsParallel, function( gens, pre )
return AddToIgsParallel( [], gens, [], pre );
end );
#############################################################################
##
## CgsParallel( <gens>, <pre> )
##
## parallel version of Cgs. Note: this function performes an
## induced pcs computation as well.
##
InstallGlobalFunction( CgsParallel, function( gens, pre )
local can, cann, i, f, e, j, l, d, r, s;
if Length( gens ) = 0 then return []; fi;
can := IgsParallel( gens, pre );
cann := can[2];
can := can[1];
# first norm leading coefficients
for i in [1..Length(can)] do
f := NormingExponent( can[i] );
can[i] := can[i]^f;
cann[i] := cann[i]^f;
od;
# reduce entries in matrix
for i in [1..Length(can)] do
e := LeadingExponent( can[i] );
r := Depth( can[i] );
for j in [1..i-1] do
l := Exponents( can[j] )[r];
if l > 0 then
d := QuoInt( l, e );
can[j] := can[j] * can[i]^-d;
cann[j] := cann[j] * cann[i]^-d;
elif l < 0 then
d := QuoInt( -l, e );
s := RemInt( -l, e );
if s = 0 then
can[j] := can[j] * can[i]^d;
cann[j] := cann[j] * cann[i]^d;
else
can[j] := can[j] * can[i]^(d+1);
cann[j] := cann[j] * cann[i]^(d+1);
fi;
fi;
od;
od;
return[ can, cann ];
end );
[ Dauer der Verarbeitung: 0.39 Sekunden
(vorverarbeitet)
]
|
