Dear Forum, Dear Daniel Blazewicz,
> I was executing GaloisType method for several irreducible polynomials of the
> form x^12+ax+b to find solvable examples. And my loop "hung" at
> x^12+63*x-450. After 2 days I decided to break the execution. FYI, I use 4
> years old laptop with ~2GHz CPU. Do you know if it is expected that
> GaloisType method can take days (weeks?) for polynomials of 12th degree?
Yes and No.
Why No:
In your case there actually is a minor bug (a routine for approximating a root
iterates between two approximations without stopping). This will be fixed in
the next release. Thank you very much for reporting it. (I append the (pathetic
-- it shows my lack of knowledge of numerical analysis) routine if you want an
immediate patch.)
What I would recommend for a search like yours is to call
ProbabilityShapes
on the polynomial first. If it returns S_n (or A_n) as only possibilities --
and this will happen in most cases -- the result is correct and you presumably
can eliminate the polynomial.
Why Yes:
If you happen upon a polynomial whose Galois group is M_{12} the certificate
for distinguishing it from A_{12} is very expensive. Such a calculation will
possibly take weeks. (ProbabilityShapes should be done always quickly, but does
not guarantee that a Galois group cannot be larger.)
Best wishes,
Alexander Hulpke
-- Colorado State University, Department of Mathematics,
Weber Building, 1874 Campus Delivery, Fort Collins, CO 80523-1874, USA
email: hul...@math.colostate.edu, Phone: ++1-970-4914288
http://www.math.colostate.edu/~hulpke
BindGlobal("ApproximateRoot",function(arg)
local r,e,f,x,nf,lf,c,store,letzt;
r:=arg[1];
e:=arg[2];
store:= e<=10 and IsInt(r) and 0<=r and r<=100;
if store and IsBound(APPROXROOTS[e]) and IsBound(APPROXROOTS[e][r+1])
then return APPROXROOTS[e][r+1];
fi;
if Length(arg)>2 then
f:=arg[3];
else
f:=10;
fi;
x:=RootInt(NumeratorRat(r),e)/RootInt(DenominatorRat(r),e);
nf:=r;
c:=0;
letzt:=[];
repeat
lf:=nf;
Add(letzt,x);
x:=ApproxRational(1/e*((e-1)*x+r/(x^(e-1))),f+6);
nf:=AbsInt(x^e-r);
if nf=0 then
c:=6;
else
if nf>lf then
lf:=nf/lf;
else
lf:=lf/nf;
fi;
if lf<2 then
c:=c+1;
else
c:=0;
fi;
fi;
# until 3 times no improvement
until c>2 or x in letzt;
if store then
if not IsBound(APPROXROOTS[e]) then
APPROXROOTS[e]:=[];
fi;
APPROXROOTS[e][r+1]:=x;
fi;
return x;
end);
_______________________________________________
Forum mailing list
Forum@mail.gap-system.org
http://mail.gap-system.org/mailman/listinfo/forum
