Project

General

Profile

Slug #1337

PrimaryDecomposition: a interesting/pathological example

Added by Anna Maria Bigatti over 4 years ago. Updated about 1 year ago.

Status:
In Progress
Priority:
Normal
Assignee:
Anna Maria Bigatti
Category:
Improving
Target version:
CoCoALib-0.99880
Start date:
15 Oct 2019
Due date:
% Done:

10%

Estimated time:
Spent time:
0.50 h

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

Related to CoCoALib - Slug #1105: Primary Decompositon (zero-dim) slow casesClosed2017-10-02

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 about 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 about 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 about 2 years ago

  • Target version changed from CoCoALib-0.99800 to CoCoALib-0.99850

#6 Updated by John Abbott about 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).

Also available in: Atom PDF