Project

General

Profile

Feature #1030

IsInRadical: case of homog ideal

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

Status:
Closed
Priority:
Normal
Assignee:
Category:
Improving
Target version:
Start date:
14 Mar 2017
Due date:
% Done:

100%

Estimated time:
Spent time:

Description

Currently IsInRadical is defined in a CPKG5, but may soon be translated to CoCoALib.

The case of a homog poly in a homog ideal is handled specially.

I wonder if we cannot improve it by simply testing each homog component of the poly for membership in the radical.


Related issues

Related to CoCoA-5 - Bug #1032: IsInRadical: fragile codeClosed2017-03-17

Related to CoCoALib - Feature #1033: Split poly into homog partsClosed2017-03-17

History

#1 Updated by John Abbott over 1 year ago

  • Subject changed from IsInRadical: case of homog poly to IsInRadical: case of homog ideal
  • Status changed from New to In Progress
  • % Done changed from 0 to 10

I think that if the ideal I is homog then IsInRadical(f,I) is the same as the logical-and of IsInRadical(f_d,I) for all homog components f_d of f. I do not know whether it is faster to compute it this way... or maybe my maths is wrong?

#2 Updated by Anna Maria Bigatti over 1 year ago

John Abbott wrote:

I think that if the ideal I is homog then IsInRadical(f,I) is the same as the logical-and of IsInRadical(f_d,I) for all homog components f_d of f. I do not know whether it is faster to compute it this way... or maybe my maths is wrong?

correct: f = f_d + .... (f_d homog of deg d = deg(f)).
f^n = (f_d)^n + ... in I implies (f_d)^n in I implies f_d is in radical(I)

#3 Updated by John Abbott over 1 year ago

  • Related to Bug #1032: IsInRadical: fragile code added

#4 Updated by John Abbott over 1 year ago

#5 Updated by John Abbott 12 months ago

  • Status changed from In Progress to Feedback
  • Assignee set to John Abbott
  • Target version changed from CoCoALib-0.99999 to CoCoALib-0.99560
  • % Done changed from 10 to 90

The CoCoA-5 package was translated into C++ by some students at Kassel.
I have cleaned up the resulting code, and checked it in: see files RadicalMembership
I have added doc and a test (but no example).
I have made the fns available via CoCoA-5; the old package is still there, but I have changed the fn names to avoid clashes. Probably the package should simply be deleted (perhaps after a bit more testing?)

I have added a couple of "heuristic tricks" to IsInRadical, as otherwise computation times can be very long (esp, when the polynomial is not in the radical). The trick is just to see if a generator (or RGB element) is not square-free; if so, add as new generator the "radical" of that generator.

Note that SqFreeFactor can be slow when coeffs are in a finite field (since GCD is still via a GBasis computation); so the trick is not applied to "big" polys.

#6 Updated by John Abbott 12 months ago

I wonder if either of the following ideas could be completed into an algorithm (with reliable output):
  1. if the ideal is not 0-dim, adjoin some random linear polys (or linear forms) to the gens possibly making the ideal 0-dim, then test for radical membership. If poly is not in radical of extended ideal, it is surely not in the radical of the original ideal; the other case is less clear.
  2. if ideal is over QQ, try a modular approach; perhaps use MinPowerInIdeal to predict power of original power which ought to be in the original ideal (and then test that power directly).

Is it true that every (polynomial) ideal I has an "exponent" exp(I) such that for any polynomial IsInRadical(f,I) iff f^exp(I) IsIn I. I'm not sure how the exponent could be computed.

#7 Updated by John Abbott 8 months ago

  • Status changed from Feedback to Closed
  • % Done changed from 90 to 100

#8 Updated by John Abbott 8 months ago

  • Description updated (diff)

Also available in: Atom PDF