Feature #1272
Groebner Bases over ZZ
Description
Write a basic implementation for Groebner Bases over the integers
Related issues
History
#1
Updated by Anna Maria Bigatti about 5 years ago
Updated by - Category set to CoCoA-5 function: new
As a starting point Elisa Palezzato noticed a bug in NR: it does not check the ring of coefficients is a field.
#2
Updated by Anna Maria Bigatti about 5 years ago
NR bug:
/**/ use ZZ[x,y]; /**/ NR(x^2, [2*x^2-1]); 0
very odd, very wrong
#3
Updated by Anna Maria Bigatti about 5 years ago
Very subtle: it gets to this
void RingZZImpl::myDiv(RawPtr rawlhs, ConstRawPtr rawx, ConstRawPtr rawy) const
{
CoCoA_ASSERT(!myIsZero(rawy));
mpz_divexact(import(rawlhs), import(rawx), import(rawy));
}
so 1/2 is 0, then computes x^2 - 0*(2*x^2-1), but skipping the two leading monomials.
Now, where should I put the check? and which check?
In fact, if the divisors were monic, it works fine in theory and practice.
#4
Updated by John Abbott almost 5 years ago
Updated by Florian Walsh (Passau) has an prototype implementation of GBasis over ZZ, currently as a package in CoCoA-5. He is willing to donate it to us.
#5
Updated by Elisa Palezzato almost 5 years ago
Updated by We also wrote a prototype implementation of GBasis over ZZ. In particular we focused on minimal strong GBasis. Maybe it could be useful as a comparison.
#6
Updated by Florian Walsh almost 5 years ago
Updated by - File GBasisZ.cpkg5 GBasisZ.cpkg5 added
So here is my implementation. It is based on this thesis https://kluedo.ub.uni-kl.de/files/4457/phd.pdf by A. Popescu.
So far I didn't implement any of the optimizations. Please let me know if you find bugs or have suggestions for improvement.
I also have some functions (in CoCoA 4) for computing the intersection, quotient and saturation of Ideals over ZZ.
If you are interested I can port them to CoCoA 5.
#7
Updated by Anna Maria Bigatti almost 5 years ago
Florian Walsh wrote:
So here is my implementation. It is based on this thesis https://kluedo.ub.uni-kl.de/files/4457/phd.pdf by A. Popescu.
Good!
if you and Elisa agree, you could compare/merge your code(s).
#8
Updated by Elisa Palezzato almost 5 years ago
I have to prepare the package, now it is just a collection of functions. After that for me is fine, we can do it!
Elisa
#9
Updated by Elisa Palezzato almost 5 years ago
- File GBoverZZ.cpkg5 GBoverZZ.cpkg5 added
In order to minimize the output of the GB we added the reduction via the GCD of the LCs to the computation of the minimal strong GB.
Given the following properties:
1) the ideal generated by the leading monomials of polynomials in I equals the ideal generated by the leading monomials of G;
2) the leading monomial of any polynomial in I is divisible by the leading monomial of some polynomial in G;
our output verify 1) and not 2).
Here we have an example of different results:
/**/ use ZZ[x,y,z];
/**/ G := [2*x+2*y, 3*y, x^3+3*y];
/**/ indent(GBoverZZ(G));
[
3*y,
2*x +2*y,
y^3 +6*y,
x^3 +3*y
]
/**/ indent(MinimalGBasisZ(G));
[
2*x +2*y,
3*y,
x^3 +3*y,
x*y -2*y^2,
y^3 +6*y
]
The poly x*y -2*y^2 is equal to -y*(2*x +2*y) + x*(3*y).
I attach the package below.
#10
Updated by Elisa Palezzato almost 5 years ago
- File GBoverZZ.cpkg5 GBoverZZ.cpkg5 added
We modified our package following Robbiano's examples that you can find below.
use ZZ[x,y,z];
f1 := x^2-2*y;
f2 := x*y+3*z+1;
f3 := z^2+5*x;
GBoverZZ([f1,f2,f3]);
-- [z^2 +5*x, 2*y^2 +3*x*z +x, x*y +3*z +1, x^2 - 2*y]
GBasisZ([f1,f2,f3]);
-- [x^2 - 2*y, x*y +3*z +1, z^2 +5*x, -2*y^2 -3*x*z -x]
use ZZ[x,y];
GBoverZZ([3*y - 1, 6*x - 1]);
-- [3*y - 1, - 2*x +y, x*y +y^2 - x]
GBasisZ([3*y - 1, 6*x - 1]);
-- [3*y -1, 6*x -1, - 2*x +y, x*y +y^2 -x]
To be noted:
- both packages work only on ZZ. For our package (GBoverZZ) this is due to the fact that gcd(3*y,6*x)=1 over QQ[x,y].
- Over ZZ does not exist yet the type ideal. For the moment the input of the GB must be a list.
#11
Updated by Elisa Palezzato almost 5 years ago
- File GBoverZZ.cpkg5 GBoverZZ.cpkg5 added
Few bugs fixed.
We separated GBoverZZ and MinimalGBoverZZ.
#12
Updated by Florian Walsh over 4 years ago
- File GBasisZ.cpkg5 GBasisZ.cpkg5 added
Changes to the previous version:
- some code cleanup
- fix bug in the ExtendedGBoverZZ function
- add functions IsNecessaryGcdPair and IsNecessarySPair to avoid considering unecessary pairs
- merge some functions/ideas from the other GBoverZZ implementation
#13
Updated by John Abbott about 4 years ago
- Target version changed from CoCoA-5.?.? to CoCoA-5.4.0
#14
Updated by John Abbott over 2 years ago
- Related to Feature #1635: NR for polys with coeffs in PID added
#15
Updated by John Abbott about 2 years ago
- Status changed from New to In Progress
- % Done changed from 0 to 10
What is the status of this issue?
Is the latest version of the code above more-or-less ready to be included in a release?
Thanks!
Be warned: I am about to download the code and start playing with it... I may even give it to my students!
#16
Updated by John Abbott about 2 years ago
- File GBasisZ-20220202.cpkg5 GBasisZ-20220202.cpkg5 added
I have done some cleaning in the code, and have added a SortBy to the list of pairs.
It seems to make the code run usefully faster (in some cases, anyway).
I'll try to attach the new version.
#17
Updated by John Abbott about 2 years ago
To be ale to tackle non-trivial examples, it would be very helpful to have a way of reducing polynomials modulo any constant which we happen to find.
Trying to do this while also computing quotients in NRoverZZCore could be tricky... maybe it is not so necessary there?
#18
Updated by John Abbott about 2 years ago
- % Done changed from 10 to 20
I have a first version with modulus. I think it is probably faster, but still impressively slow :-/
I'll wait a bit before uploading it.
#19
Updated by John Abbott about 2 years ago
What is the future of this package?
Florian is now rather busy with other things, so cannot in the foreseeable future do much more.
Perhaps the same applies to Elisa and Michele?
Many of the operations are actually quite "low level", so a translation into C++ would
likely produce a noticeable speed gain.
I am anticipating a work-load which will preclude me from doing anything for CoCoA for
the next 6+ months... that means I'll do nothing (not even emergency bug fixes).
All thanks to the administrators' daft rules about measuring how much work one does.
#20
Updated by John Abbott about 2 years ago
So that we do not lose what has been done....
I suggest making the existing code into an official package; we should document at least 1 function (MinimalGBoverZZ -- what name??)
I fear there is no maintainer (so it lands on my desk).
#21
Updated by John Abbott about 2 years ago
- % Done changed from 20 to 50
I have documented MinGBoverZZ but no other function. It is clearly marked as [PROTOTYPE].
The package is now called prototype-GBZZ.cpkg5.
I shall check in shortly. The hope is not to lose this code... though it is not really ready for public release.
#22
Updated by John Abbott about 2 years ago
- Assignee set to John Abbott
- % Done changed from 50 to 100
- Estimated time set to 14.99 h
I'll close this as it is now in CVS, and should be in the next release (with 1 fn documented).
It could be a good student project to convert it to C++, and make it more efficient!
I'll make a new issue about the conversion to C++.
Closing.
#23
Updated by John Abbott about 2 years ago
- Related to Feature #1667: GBasis over ZZ: port to CoCoALib added
#24
Updated by John Abbott about 2 years ago
- Status changed from In Progress to Closed