Opened 15 years ago
Closed 12 years ago
#1819 closed enhancement (fixed)
move crypto.mq.MPolynomialSystem somewhere else
Reported by: | Martin Albrecht | Owned by: | Martin Albrecht |
---|---|---|---|
Priority: | major | Milestone: | sage-4.7 |
Component: | commutative algebra | Keywords: | |
Cc: | Stanislav Bulygin, mhampton | Merged in: | sage-4.7.alpha1 |
Authors: | Martin Albrecht | Reviewers: | Volker Braun |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
mq.MPolynomialSystem
is more general than its position in the tree suggests. I should be moved to sage.rings.polynomial.multi_polynomial_sequence
and used as a special case of Sequence
if the members are all multivariate polynomials.
Depends on #10600
Attachments (2)
Change History (29)
comment:1 Changed 12 years ago by
Description: | modified (diff) |
---|---|
Report Upstream: | → N/A |
comment:2 Changed 12 years ago by
Description: | modified (diff) |
---|---|
Status: | new → needs_review |
comment:3 Changed 12 years ago by
Authors: | → Martin Albrecht |
---|
comment:4 Changed 12 years ago by
Description: | modified (diff) |
---|
comment:5 Changed 12 years ago by
comment:6 Changed 12 years ago by
The attached patch takes care of those doctest failures (except for the cmdline one which is not due to this patch)
comment:7 Changed 12 years ago by
Description: | modified (diff) |
---|
comment:8 Changed 12 years ago by
Cc: | Stanislav Bulygin mhampton added |
---|
Hi, can one of you two take a look at this patch? Cheers.
comment:9 Changed 12 years ago by
Btw. patchbot reports "Apply failed" because the patch is for 4.6.2.alpha4 instead of 4.6.1.
comment:10 follow-up: 11 Changed 12 years ago by
The whole rename looks reasonable to me.
Having said that, I don't understand why we need both MPolynomialIdeal
and PolynomialSequence
. It seems to be that both are essentially containers for polynomials in a common ring. Maybe the methods of PolynomialSequence
could just be merged with the ideal code? Do you have any thoughts about that?
comment:11 Changed 12 years ago by
Replying to vbraun:
Having said that, I don't understand why we need both
MPolynomialIdeal
andPolynomialSequence
. It seems to be that both are essentially containers for polynomials in a common ring. Maybe the methods ofPolynomialSequence
could just be merged with the ideal code? Do you have any thoughts about that?
I disagree with merging the two. Ideal are not the same as sequences of polynomials: ideals may be infinite, but our polynomial sequences are always finite. Furthermore, some methods don't make sense on ideals but do make sense for sequences of polynomials such as interreduction and weil restriction. That we have those methods on ideals now is not proper, I'd say. Another example: set operations on ideals are different from set operations on polynomial sequences.
comment:12 follow-up: 13 Changed 12 years ago by
Mathematically, they are of course not the same. But as far as the implementation goes, both are lists of polynomials with some methods attached. I don't understand your comment about finiteness, you can't generate a non-finitely generated ideal in Sage, nor could you construct the requisite infinite polynomial ring to evade Hilberts basis theorem. Moreover, I don't understand your comment about the interreduced_basis
method in the ideal class. Where else but as a method of the ideal class should we define this functionality in OOP?
comment:13 Changed 12 years ago by
Replying to vbraun:
Mathematically, they are of course not the same. But as far as the implementation goes, both are lists of polynomials with some methods attached. I don't understand your comment about finiteness, you can't generate a non-finitely generated ideal in Sage, nor could you construct the requisite infinite polynomial ring to evade Hilberts basis theorem. Moreover, I don't understand your comment about the
interreduced_basis
method in the ideal class. Where else but as a method of the ideal class should we define this functionality in OOP?
I meant infinite but finitely generated which is for example relevant for set operations on them. Another example is reduction: reduction modulo the ideal is different from reduction modulo a list of polynomials. The method interreduced_basis
assumes a particular basis for the ideal, i.e. violates the distinction between ideal and a list of polynomials. I'd say we should aim to have methods on ideals deal with ideals instead of the particular basis the user chose when constructing it.
comment:14 follow-up: 15 Changed 12 years ago by
In principle, it would be nice if the ideal class could represent some basis-free abstract notion of ideal. In practice, this is not possible as all non-trivial computations are exponential complexity due to the need for Groebner bases. Even worse, the Groebner basis computation often depends on a judiciously chosen term ordering which cannot be automated. This is why all computer algebra programs that I am aware of treat ideals as sequences of polynomials, and not as ideals in the mathematical sense. Barring any breakthrough in algebra it is not feasible to do otherwise.
comment:15 Changed 12 years ago by
I should have mentioned that the decision to treat ideals as such abstract basis-free objects was made before I joined the project, probably inherited from Magma. For example, cf. the intro of http://sagemath.org/doc/reference/sage/crypto/mq/mpolynomialsystem.html (which I admit to have written, though). Thus, many methods of the multivariate polynomial ideal class do compute a Gröbner basis behind the scenes. Btw. since ideals know their ring and rings contain the term ordering in Sage, we can compute GBs without any additionally provided information.
comment:16 follow-up: 17 Changed 12 years ago by
I don't see that anywhere in the MPolynomialIdeal
class. Correct me if I'm wrong, but the chosen generators and their order is immutable. Even when computing a Groebner basis, the generators are not replaced by this much more useful basis. On the other hand, there are methods like basis_is_groebner()
which are obviously basis-dependent. It seems to me that Sage implements ideals very much as an immutable sequence of polynomials with some methods attached. The individual methods do, of course, need Groebner bases but they never change the underlying sequence of polynomials.
I am aware that the ideals implicitly contain the term order, though I found that a somewhat mixed blessing in #10708.
comment:17 follow-up: 18 Changed 12 years ago by
Replying to vbraun:
I don't see that anywhere in the
MPolynomialIdeal
class. Correct me if I'm wrong, but the chosen generators and their order is immutable.
Yep.
Even when computing a Groebner basis, the generators are not replaced by this much more useful basis.
But the GB is cached and used for "interesting" operations.
On the other hand, there are methods like
basis_is_groebner()
which are obviously basis-dependent.
This was the compromise reached to (a) keep the notion that ideals are different objects than their generators and to (b) still allow to query some information about the basis. We should have separated stuff back then perhaps. In any case, it was this method's name which sparked the debate we're having between William and myself.
It seems to me that Sage implements ideals very much as an immutable sequence of polynomials with some methods attached.
I'd say: it attempts to present a view on ideals which abstracts away chosen bases but with varying success.
The individual methods do, of course, need Groebner bases but they never change the > underlying sequence of polynomials.
But e.g. intersection()
and reduce()
actually use the GB and not the provided basis, they are methods on the ideal and not on the generating set. Some other methods are less clear such as basis_is_groebner()
and interreduced_basis()
. These could perhaps be moved to PolynomialSequence
.
I am aware that the ideals implicitly contain the term order, though I found that a somewhat mixed blessing in #10708.
I wouldn't say this is because of the containment of term orderings but because of lack of care dealing with them?
comment:18 follow-up: 19 Changed 12 years ago by
Replying to malb: it was this method's name which sparked the debate we're having between William and myself.
We are having? Where? Or you were having at one point (and if yes, did you decide anything)?
comment:19 Changed 12 years ago by
Replying to vbraun:
Replying to malb: it was this method's name which sparked the debate we're having between William and myself.
We are having? Where? Or you were having at one point (and if yes, did you decide anything)?
Sorry, my English failed me: William and I had a debate about whether ideal class == list of polynomials a few years back (October 2006). It was essentially about the same issue which we are discussion here now (I realised while double checking that it wasn't about basis_is_groebner()
but about the return type of groebner_basis()
) The decision was: ideals are objects in their own right in Sage and not lists of polynomials.
Should we move this discussion to [sage-devel]?
comment:20 follow-up: 21 Changed 12 years ago by
Now that I see some of the bigger picture I'm happy with distinguishing ideals and polynomial sequences in the way you are implementing. I don't quite get how the multiple parts of the polynomial sequence are supposed to fit into this. The documentation should either stress that this is optional (and that, by default, there is only a unique part) or separate this functionality into a derived class.
Some other suggestions, though that could easily be postponed to followup tickets:
- Document the relationship between ideals and polynomial sequences in the ideals module.
- An alias
MPolynomialIdeal.basis
=MPolynomialIdeal.gens
- Move
MPolynomialIdeal.basis_is_groebner
toPolynomialSequence.is_groebner
- Move
MPolynomialIdeal.interreduced_basis
toPolynomialSequence.interreduce
and make it return aPolynomialSequence
instead of a list. - there shouldn't be a
PolynomialSequence.groebner_basis
- Perhaps move
MPolynomialIdeal.weil_restriction
since you say that it depends on the presentation.
comment:21 Changed 12 years ago by
Replying to vbraun:
Now that I see some of the bigger picture I'm happy with distinguishing ideals and polynomial sequences in the way you are implementing. I don't quite get how the multiple parts of the polynomial sequence are supposed to fit into this. The documentation should either stress that this is optional (and that, by default, there is only a unique part)
Good idea.
Some other suggestions, though that could easily be postponed to followup tickets:
- Document the relationship between ideals and polynomial sequences in the ideals module.
Done.
- An alias
MPolynomialIdeal.basis
=MPolynomialIdeal.gens
- Move
MPolynomialIdeal.basis_is_groebner
toPolynomialSequence.is_groebner
- Move
MPolynomialIdeal.interreduced_basis
toPolynomialSequence.interreduce
and make it return aPolynomialSequence
instead of a list.- there shouldn't be a
PolynomialSequence.groebner_basis
This is now #10856.
- Perhaps move
MPolynomialIdeal.weil_restriction
since you say that it depends on the presentation.
Thinking about it: it's about the variety and thus can stay with the ideals.
comment:22 Changed 12 years ago by
The attached updated patch clarifies "parts" and the relation between ideals and polynomial sequences.
comment:23 Changed 12 years ago by
Milestone: | sage-4.6.2 → sage-4.7 |
---|---|
Reviewers: | → Volker Braun |
Status: | needs_review → positive_review |
Ok looks good to me. Applies to Sage-4.6.2.rc1, too.
comment:24 Changed 12 years ago by
Status: | positive_review → needs_work |
---|
There is a Sphinx warning:
mnt/usb1/scratch/jdemeyer/merger/sage-4.7.alpha2/local/lib/python2.6/site-packages/sage/rings/polynomial/multi_polynomial_ideal.py:docstring of sage.rings.polynomial.multi_polynomial_ideal:206: (ERROR/3) Unknown interpreted text role "cls".
Changed 12 years ago by
Attachment: | trac_1819.patch.diff added |
---|
diff of this version of the patch and the last version
comment:25 Changed 12 years ago by
Status: | needs_work → needs_review |
---|
The updated attached patch fixes the reported issue. However, I'm not setting this to positive review myself since I fixed a few more formating issues wrt to the reference manual. I also a diff between the current and the previous version of the patch for easy reviewing of those changes.
comment:26 Changed 12 years ago by
Status: | needs_review → positive_review |
---|
Looks good. Fixes the documentation warning.
comment:27 Changed 12 years ago by
Merged in: | → sage-4.7.alpha1 |
---|---|
Resolution: | → fixed |
Status: | positive_review → closed |
There are a few minor doctest failures: