Slug #777
SLUG: elimination
Description
The following elim
is very slow... why?
use QQ[x,y]; d := 12; a:=1000; f1:=x^d-(a*x-1)^2; f2 := x^(d/2)*y^(d/2) - (y-x^(d/4))^2; J := elim([x],ideal(f1,f2)); ---> takes way too long... why? f := gens(J)[1]; RR := RealRoots(f);
Related issues
History
#1 Updated by John Abbott over 8 years ago
I'm not sure how long the elim took (perhaps 20-30mins?)
The input is simple, the output not even that large (deg=72); why is it so slow?
The same elim
modulo p is tolerably fast (perhaps 0.1 sec per prime?), and only a few primes would be needed to get the answer via CRT...
#2 Updated by John Abbott about 7 years ago
- Status changed from New to In Progress
- % Done changed from 0 to 10
I happened upon the file for the example, and tried it with SetVerbosityLevel(1999)
.
It seems that much of the time is spent in myFinalizeGBasis
.
It would be nice to make elimination faster.
#3 Updated by John Abbott about 7 years ago
The same example computed using MinPolyQuot
is much faster: about 0.2s :-)
Maybe elim
can be programmed to use MinPolyQuot
when possible?
#4 Updated by Anna Maria Bigatti about 7 years ago
Apart from the improvements we can do for elim
(and are about to do ;-)
I think myFinalizeGBasis
can be improved: this step is done to compute the reduced GBasis (in case of non-homogeneous input).
Now it reduces each element in myGB
against myTrueReductors
.
I have the feeling that there are elements in myGB
whose LT is reducible, then those are surely to be removed (without wasting time in reducing them).
Extreme case: is 1 is in GB then myFinalizeGBasis
should be instant.
I'll investigate.
#5 Updated by Anna Maria Bigatti over 4 years ago
- Related to Design #1326: Modify function myElim so that it returns ideal? (not quite) added
#6 Updated by Anna Maria Bigatti over 4 years ago
- Related to Slug #1270: RationalSolve: use MinPolyQuot instead of elim added
#7 Updated by Anna Maria Bigatti over 4 years ago
- Target version changed from CoCoALib-1.0 to CoCoALib-0.99800
#8 Updated by John Abbott about 3 years ago
Has there been any progress on this issue?
In the case of elimination perhaps the "final clean up" could be limited to just those elems in the GB whose LTs contain only "keep" indets?
There would seem to be no point in "cleaning" GB elems which are anyway going to be discarded.
Could this be possible?
#9 Updated by John Abbott over 2 years ago
- Target version changed from CoCoALib-0.99800 to CoCoALib-0.99850
#10 Updated by John Abbott about 1 month ago
- Related to Slug #1394: Oddly slow GBasis computation (slow final cleanup) added
#11 Updated by Anna Maria Bigatti 11 days ago
- Related to Slug #1796: myFinalizeGBasis ("Final clean up") should be more flexible added
#12 Updated by Anna Maria Bigatti 7 days ago
- Assignee set to Anna Maria Bigatti
Anna Maria Bigatti wrote:
Apart from the improvements we can do for
elim
(and are about to do ;-)
I wonder if we made them...
I think
myFinalizeGBasis
can be improved: this step is done to compute the reduced GBasis (in case of non-homogeneous input).Now it reduces each element in
myGB
againstmyTrueReductors
.
I have the feeling that there are elements inmyGB
whose LT is reducible, then those are surely to be removed (without wasting time in reducing them).
Now I did it (a bit of chasing around and implementation of FindReducer(GPoly, TrueRed)). All tests passing.
Extreme case: is 1 is in GB then
myFinalizeGBasis
should be instant.
I'll investigate.
This has been done
(in myUpdateBasisAndPairs(const GPoly& inPoly) Revision 1.99 2018/03/08)
#13 Updated by Anna Maria Bigatti 7 days ago
Now it takes 165s (I don't know how long it was before)
#14 Updated by Anna Maria Bigatti 7 days ago
#15 Updated by Anna Maria Bigatti 7 days ago
- Target version changed from CoCoALib-0.99850 to CoCoALib-0.99880