Slug #1556
DivAlg slower than NR
Description
Andraschko reported the following by email:
Consider the following code which computes the minimal polynomial of sqrt(2)+sqrt3(3)+sqrt5(5):
S ::= QQ[x,t1,t2,t3]; Use S; L := [x-(t1+t2+t3), t1^2-2, t2^3-3, t3^5-5]; I := ideal(S,L); J := elim([t1,t2,t3],I); f := gens(J)[1]; -- some ugly poly of deg 30 that is in I
Now let's just compute for fun NR. This should be 0 since f is in I and L is a Gröbner basis by the coprime LT criterion.
It does and it is very fast (not even a second). Now if we do the same with DivAlg, it is VERY slow - although it should normally do the same and just store some information on its way.
Why is it so slow? It took 16 minutes on my system until it was finished.
History
#1 Updated by John Abbott over 3 years ago
I verify that the problem is present in the current version on my computer.
NR
is a built-in function; DivAlg
actually calls ModElDivAlg
in hilop.cpkg5
.
While it is reasonable that DivAlg
takes longer (since it must compute the quotients too); being a factor of about 20000 slower is unreasonable!
#2 Updated by John Abbott over 3 years ago
Just for the record: NR
took about 0.063s, DivAlg
took about 1280s.
Presumably DivAlg
should also be built-in, and should use geobuckets to accumulate the factors?
#3 Updated by Anna Maria Bigatti over 3 years ago
- Assignee set to Anna Maria Bigatti
Check the code for NR and see how to make the data type for the output.
#4 Updated by Anna Maria Bigatti over 3 years ago
- % Done changed from 0 to 10
I checked: not as easy as I thought.NR
is defined in SparsePolyOps-RingElem.C
and make use of ReductionCog. This means it cannot be extended to keep track of the quotients. It has to be copied, and rewritten.