Slug #1337
PrimaryDecomposition: a interesting/pathological example
Description
This example is very very slow because a factor of MinPolyQuot(t,I,t)
produces an ideal with a very slow GBasis.
K ::= ZZ/(101); use P ::= K[x,y,z,t]; F1 := x*y*z*t +83*y^3 +73*x^2 -85*z^2 -437*t; F2 := y^3*z*t +z -t; F3 := t^4 +z*t^2 -324*z^3 +94*x^2 +76*y; F4 := x^11*z +26*t^3 +625*y; I := ideal(F1, F2, F3, F4); R:=CpuTime(); RGB := ReducedGBasis(I); TimeFrom(R); R:=CpuTime(); PD := PrimaryDecomposition(I); TimeFrom(R);
The primary decomposition in
ZZ/(101)[t,z,y,x]
takes less than 4s on my (slow) computer.
This is just unlucky!
Can we do something clever about this?
Related issues
History
#1 Updated by Anna Maria Bigatti over 4 years ago
- Description updated (diff)
#2 Updated by Anna Maria Bigatti over 4 years ago
- Related to Slug #1105: Primary Decompositon (zero-dim) slow cases added
#3 Updated by John Abbott over 3 years ago
STATUS 2021-02-16: I confirm that the RGB took about 0.35s on my computer, while PD took 473s.
OBSERVATION: it seems that much of the time is right after the 49th elem has been added to the GB. One or more very costly reductions to zero? Number of pairs dropped from 111 to 4.
#4 Updated by John Abbott over 3 years ago
- Description updated (diff)
Since we now have GBasis with timeout, perhaps that could be used to implement a sort of "parallel" approach where the first successful branch is followed?
It would be even better if CoCoA had proper parallel primitives (but that is likely far away).
The "faster" indet ordering took about 2.2s on my GNU/Linux computer.
#5 Updated by John Abbott over 2 years ago
- Target version changed from CoCoALib-0.99800 to CoCoALib-0.99850
#6 Updated by John Abbott over 1 year ago
- Status changed from New to In Progress
- Target version changed from CoCoALib-0.99850 to CoCoALib-0.99880
- % Done changed from 0 to 10
2023-03-08 I have just run the example (on my current GNU/Linux box).
The times are: 0.33s and 499s (ouch! slower!)
Postponing to 0.99880: it works, just a bit slow (sometimes).