Project

General

Profile

Slug #405

ReducedGBasis not memorized in an ideal

Added by John Abbott over 10 years ago. Updated almost 7 years ago.

Status:
Closed
Priority:
Normal
Assignee:
Anna Maria Bigatti
Category:
Incomplete function
Target version:
CoCoA-5.2.0 spring 2017
Start date:
09 Oct 2013
Due date:
% Done:

100%

Estimated time:
2.01 h
Spent time:
2.10 h

Description

Sometimes C5 seems not to memorize a computed GBasis -- or is it simply re-interreducing?
Anyway, this is an ugly slug!

Use QQ[a, b, x, y, z], Lex;
J:=Ideal( x- a^3 - b^3 - 3, y -a^5 - b^5 - 5, z - a^7 - b^7 - 7);
T := CpuTime(); GB_Lex:=ReducedGBasis(J); TimeFrom(T);
--> seems to RECOMPUTE the basis:
T := CpuTime(); GB_Lex:=ReducedGBasis(J); TimeFrom(T);

Related issues

Related to CoCoALib - Bug #114: Ideals of polynomialsIn Progress2012-03-26

Related to CoCoA-5 - Support #977: "universal denominator" (related with GroebnerFanIdeals)In Progress2016-11-17

Related to CoCoALib - Feature #957: New function: HasGBasisClosed2016-10-27

Related to CoCoALib - Feature #961: New function: ReducedGBasisClosed2016-11-03

History

#1 Updated by Anna Maria Bigatti over 10 years ago

  • Category set to Incomplete function
  • Status changed from New to In Progress
  • Target version set to CoCoA-5.1.0 Easter14
  • % Done changed from 0 to 10

This is what happens

/**/ T := CpuTime(); RGB:=ReducedGBasis(J); DecimalStr(CpuTime()-T);
69.847
/**/ T := CpuTime(); RGB:=ReducedGBasis(J); DecimalStr(CpuTime()-T);
20.480
/**/ T := CpuTime(); GB:=GBasis(J); DecimalStr(CpuTime()-T);
0.044

The GBasis is memorized, but it is not reduced. In fact it is almost reduced:
/**/ T := CpuTime(); EqSet([monic(G)|G In GB], RGB); DecimalStr(CpuTime()-T);
true
11.465

GB has coefficients with denominator 1.
GB and RGB have 119 polynomials, 20 of which with >1000 terms.

Do we want to memorize the reduced GBasis? Or should we have a flag for "tail-reduced"/"monic"?

#2 Updated by Anna Maria Bigatti over 10 years ago

ReducedGBasis is defined in package: no wonder it is slow!
I will try to implement it in CoCoALib and see how heavy the reduction actually is.

#3 Updated by John Abbott about 10 years ago

Will it be possible to have this fixed by Easter? (i.e. before I need it for the Alg Comp course)

#4 Updated by John Abbott about 10 years ago

  • Target version changed from CoCoA-5.1.0 Easter14 to CoCoA-5.1.1 Seoul14

#5 Updated by John Abbott over 9 years ago

  • Target version changed from CoCoA-5.1.1 Seoul14 to CoCoA-5.?.?

#6 Updated by John Abbott over 7 years ago

Anna now reports that GBasis actually produces an irredundant fully reduced GBasis; the only step missing for making it a reduced GBasis is scaling the polynomials so that they are monic.

#7 Updated by John Abbott over 7 years ago

  • Related to Support #977: "universal denominator" (related with GroebnerFanIdeals) added

#8 Updated by John Abbott over 7 years ago

[translated from an email written in italian]

Here is a potentially important point. For simplicity I consider the case of coeffs in QQ.
So that polynomial reduction can be computed quickly, the reducers should be primitive with integer coeffs. Similarly the polynomial to be reduced should be rescaled to become primitive with integer coeffs; at the end, the final result of the reduction should be rescaled to produce the correct "public" result. If I recall correctly, the code already does this (or most of it).

This means that the elements of the publicly visible RGB will probably be "monic copies" of reducers which are actually used during the reduction. This implies using more memory space -- probably not important in most cases.

An argument analogous to that above presumably applies whenever the coeffs are in a fraction field e.g. QQ(a,b)[x,y,z]

#9 Updated by Anna Maria Bigatti over 7 years ago

John Abbott wrote:

[translated from an email written in italian]

Here is a potentially important point. For simplicity I consider the case of coeffs in QQ.
If I recall correctly, the code already does this (or most of it).

This is what it does for the internal computation (for all Fraction fields of GCDDomain)

#10 Updated by Anna Maria Bigatti over 7 years ago

  • Status changed from In Progress to Feedback
  • Assignee set to Anna Maria Bigatti
  • Target version changed from CoCoA-5.?.? to CoCoA-5.2.0 spring 2017
  • % Done changed from 10 to 90

GBasis is now exactly ReducedGBasis.

(still an error on RingWeyl, though, where it is not interreduced)

#11 Updated by Anna Maria Bigatti over 7 years ago

#12 Updated by Anna Maria Bigatti almost 7 years ago

  • Related to Feature #961: New function: ReducedGBasis added

#13 Updated by John Abbott almost 7 years ago

  • Description updated (diff)

#14 Updated by John Abbott almost 7 years ago

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

Closing after 5 months in feedback. A quick test shows that the RGB is now correctly memorized: well, the example given in the description was instant for the second part.

#15 Updated by Anna Maria Bigatti almost 7 years ago

  • Estimated time set to 2.01 h

Also available in: Atom PDF