Project

General

Profile

Bug #1032

IsInRadical: fragile code

Added by John Abbott over 1 year ago. Updated 7 months ago.

Status:
Closed
Priority:
Normal
Assignee:
Category:
enhancing/improving
Target version:
Start date:
17 Mar 2017
Due date:
% Done:

100%

Estimated time:
1.11 h
Spent time:

Description

The current impls of IsInRadical and MinPowerInRadical are fragile: they give errors when they should/need not.


Related issues

Related to CoCoALib - Feature #1030: IsInRadical: case of homog idealClosed2017-03-14

Related to CoCoA-5 - Slug #1141: IsInRadical: for monomial idealsNew2017-12-15

History

#1 Updated by John Abbott over 1 year ago

  • Related to Feature #1030: IsInRadical: case of homog ideal added

#2 Updated by John Abbott over 1 year ago

Here are some cases where behaviour is not ideal:

use QQ[x,y,z];
TmpI := ideal(x+y);
J := elim(x,I); // ideal without generators
IsInRadical(x,J); --> ERROR: empty list or vector
IsInRadical(zero(R),J); --> ERROR: empty list or vector

I0 := ideal(zero(R));
IsInRadical(zero(R),I0); // --> non-zero ringelem required

I1 := ideal(one(R));
IsInRadical(0,I1); // --> first arg must be POLY or IDEAL
IsInRadical(1,I1); // --> first arg must be POLY or IDEAL
IsInRadical(1/2,I1); // --> first arg must be POLY or IDEAL

Since IsIn accepts the combination RAT IsIn IDEAL, then it seems reasonable that IsInRadical should also accept INT or RAT as the type for the element.

#3 Updated by John Abbott over 1 year ago

Here are some examples which suggest that it may be better to decompose a poly into its homog parts when testing membership in the radical of a homog ideal:

Ihomog := ideal(x^999);
[IsInRadical(x^k,Ihomog) | k in 1..20];
IsInRadical(x^2+x,Ihomog); // SLUG, much slower than prev line
IsInRadical(x*sum([random(-99,99)*x^k | k in 0..10]), Ihomog); // SLUG!!!

Ihomog2 := ideal(x^999,x^1000+x^999);
[IsInRadical(x^k,Ihomog2) | k in 1..20];
IsInRadical(x^2+x,Ihomog2); // SLUG, much slower than prev line
IsInRadical(x*sum([random(-99,99)*x^k | k in 0..10]), Ihomog2); // SLUG!!!

IsInRadical(J, I0); // --> OK
IsInRadical(J, I1); // --> OK

[MinPowerInIdeal(x^k, Ihomog) | k in 1..20];
MinPowerInIdeal(x^2+x, Ihomog);
MinPowerInIdeal(x*(x^10-1)/(x-1), Ihomog);

Ihomogxy := ideal(x^400,y^400);
MinPowerInIdeal((x^10-y^10)/(x-y), Ihomogxy); --> about 20s
S := support((x^10-y^10)/(x-y));
[MinPowerInIdeal(t, Ihomogxy) | t in S]; --> instant
f := x*(x^4-1)/(x-1)*y*(y^4-1)/(y-1);
S := support(f);
[MinPowerInIdeal(t, Ihomogxy) | t in S]; --> < 1 s
MinPowerInIdeal(f, Ihomogxy); --> > 200s
Ihomogxy2 := ideal(x^400+y^401,y^400);
MinPowerInIdeal((x^10-y^10)/(x-y), Ihomogxy2);
//MinPowerInIdeal(x*(x^4-1)/(x-1)*y*(y^4-1)/(y-1), Ihomogxy2);

#4 Updated by John Abbott 8 months ago

  • Status changed from New to Resolved
  • Assignee set to John Abbott
  • Target version changed from CoCoA-5.?.? to CoCoA-5.2.2
  • % Done changed from 0 to 80
  • Estimated time set to 1.11 h

Most of these problems have been resolved by porting the code to CoCoALib (thanks to Alice Moallemy, Marvin Brandenstein, Carsten Dettmar).

There remain 2 slugs:

Ihomogxy := ideal(x^400,y^400);
f := x*((x^4-1)/(x-1))*y*((y^4-1)/(y-1));
S := support(f);
[MinPowerInIdeal(t, Ihomogxy) | t in S]; --> less than 1 s
MinPowerInIdeal(f, Ihomogxy); --> about 100s
Ihomogxy2 := ideal(x^400+y^401,y^400);
MinPowerInIdeal(f, Ihomogxy2);  --> about 140s

#5 Updated by Anna Maria Bigatti 8 months ago

My guess (I do not know the code) is that there is something optimized for monomial ideals...

Anyway, just looking at the code, I think that RadicalHelpers(const vector<RingElem>& G) could use radical(G[i]), instead of calling SqFreeFactor(G[i]); etc

#6 Updated by John Abbott 7 months ago

  • Related to Slug #1141: IsInRadical: for monomial ideals added

#7 Updated by John Abbott 7 months ago

  • Status changed from Resolved to Closed
  • % Done changed from 80 to 100

Also available in: Atom PDF