Opened 10 years ago

Closed 10 years ago

#13687 closed enhancement (fixed)

Parents for groups

Reported by: Volker Braun Owned by: joyner
Priority: major Milestone: sage-5.7
Component: group theory Keywords: new Parent
Cc: Miguel Marco, David Roe, David Joyner, Simon King Merged in: sage-5.7.beta2
Authors: Volker Braun Reviewers: David Roe
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by Jeroen Demeyer)

Groups are based on the deprecated ParentWithGens. This ticket is about forward-porting them to the new coercion framework.

To limit the size of the patchbomb I'm only porting the Abelian groups. The rest depends on old.Group

Various oddities needed to be cleaned up in the process:

  • make parents unique and elements immutable (often requires tuples instead of lists)
  • rename AbelianGroup_class.invariants() -> AbelianGroup_class.gens_orders() since they are not necessarily the abelian invariants (=elementary divisors).
  • rename element.list() -> element.exponents() for the exponent vector.
  • implement a AbelianGroupWithValues where you attach values to the (abstract) generators. Used in the unit group of a number field, for example.
  • lots of places return lists when they should return tuples

I haven't actually deprecated .invariants() and .list(), just changed the documentation to suggest the equivalent .gens_orders() and .exponents()` methods. But I think we should deprecate them. Though I first want to work my way through the remaining groups code.

Apply

Attachments (6)

trac_13687_Parent_for_groups.patch (200.3 KB) - added by Volker Braun 10 years ago.
Rebased patch
trac_13687_review.patch (85.6 KB) - added by Volker Braun 10 years ago.
Improved patch
trac_13687_assertions.patch (2.8 KB) - added by Volker Braun 10 years ago.
Updated patch
13687_parent_for_groups_all.patch (231.7 KB) - added by Jeroen Demeyer 10 years ago.
13687_parent_for_groups_all_vb.patch (232.2 KB) - added by Volker Braun 10 years ago.
Updated patch
13687_32bitfix.patch (1.5 KB) - added by Volker Braun 10 years ago.
Initial patch

Download all attachments as: .zip

Change History (41)

comment:1 Changed 10 years ago by Volker Braun

Description: modified (diff)

comment:2 Changed 10 years ago by Volker Braun

Status: newneeds_review

comment:3 Changed 10 years ago by Volker Braun

Description: modified (diff)

comment:4 Changed 10 years ago by Volker Braun

Authors: Volker Braun
Cc: Miguel Marco David Roe David Joyner Simon King added
Keywords: new Parent added

comment:5 Changed 10 years ago by David Roe

Reviewers: David Roe
Status: needs_reviewneeds_work

Hi Volker, I'm about halfway through this. Overall it's looking great. Here are some comments (let me know if anything is unclear):

  • in the _normalize function for AbelianGroup, perhaps the 0s should come last, since that lines up with the standard divisibility condition for invariants. Also, if gens_orders is a string of length n then it will get through your error checking.
  • _normalize should have examples.
  • In random_element, shouldn't the fact that doctesting consistently chooses a random seed mean we don't need to mark G.random_element() as # random output?
  • In the docstring for equals, the documentation for the output is wrong: should be checking whether they are the same subset.
  • In invs(), where you write raise Exception # WTF, maybe we should figure out what was intended by this function and fix it. :-)
  • In the module summary of dual_abelian_group, you can use floating point tolerance rather than just marking the output as random. In particular, shouldn't your first example be exact?
  • In module doctoring for dual_abelian_group_element, you should take out the # random marking on some doctests (using floating point tolerance instead if necessary)

I should go to sleep, but I'll try to get through more of this tomorrow. When you make changes, could you upload a separate patch?

Last edited 10 years ago by David Roe (previous) (diff)

comment:6 Changed 10 years ago by Volker Braun

  1. The 0's were prepended, I just kept that behavior. I think its more in line with the mathematical expectation of writing a group as free+torsion instead of the other way round. Also, the gens_orders are not the abelian invariants.
  1. I still haven't figured out what invs() is for, I'll just delete it ;-)

I agree with the rest. Most of it is just stuff that was already there and I didn't fix...

comment:7 Changed 10 years ago by David Roe

  1. Fair enough.
  1. Sounds good.

I know, I saw the old code. But if you're making changes this extensive you might as well fix some more stuff. :-)

comment:8 Changed 10 years ago by Volker Braun

Description: modified (diff)
Status: needs_workneeds_review

comment:9 Changed 10 years ago by David Roe

Here are some more suggestions. I'm going to leave it marked as needs review so that the patchbot will continue testing.

  1. In AbelianGroupElement.__init__, I think it's useful to allow ints in the generator_orders, rather than asserting that they all be Integers
  1. Documentation of exponents doesn't line up with __init__ method in AbelianGroupElementBase. You should give an example in the documentation of that function showing that the exponents are still integers, not elements of the base ring.
  1. In docstring for AbelianGroupWithValues, maybe you should note that values_group could be a ring or field, since Sage doesn't currently support the group of units in a ring very well.
  1. I don't think that AbelianGroupWithValuesEmbedding should inherit from CallMorphism, but rather just from Morphism.
  1. For the arithmetic operations in AbelianGroupWithValuesElement, I would keep the computation of _value lazy (check to see if both left and right values are not None). By being nonlazy you'll get more floating point drift and also you may compute unnecessary values.
  1. Your docstring for AbelianGroupWithValues_class.values_group is incomplete.
  1. Indentation problem at the end of the docstring for Group (right before def __init__)
  1. You set Element = FractionalIdealClass on SFractionalIdealClass(FractionalIdealClass). This should be done on the parent, not the element.
  1. There doesn't seem to be a failure in the test suite for ClassGroup, so you should remove the sentence about a failure caused by not having a category of additive abelian groups.
  1. In unit_group.py you use _.value() a few times; can you give UK.torsion_generator() (etc) a name and use it instead of _?
  1. You have a docstring floating that needs to be deleted where gen(self, i=0) used to be in UnitGroup

comment:10 Changed 10 years ago by Volker Braun

  1. AbelianGroup_class derives from UniqueRepresentation, so I want to enforce canonical arguments with the assertions. Its the job of the AbelianGroup factory function to canonicalize the user input.
  1. For the unit group, say, its much more expensive to do the exponentiation than non-lazy multiplication. Imagine you want to list all units. This is also what the FractionalIdealClass and friends do. If its cheap to exponentiate the values then I would agree with you, but in that case you probably don't need such an elaborate AbelianGroupWithValues.

comment:11 Changed 10 years ago by Volker Braun

The updated patch addresses all remaining issues. I've also based ClassGroup on AbelianGroupWithValues and some other improvements.

comment:12 Changed 10 years ago by David Roe

Looks good. Two more comments and then I'm happy to give a positive review:

  • In docstring for SFractionalIdealClass, your example blocks are indented. There should also only be one block rather than three.
  • There's a failure in the startup plugin. I have no problem giving a positive review even so, but I thought I'd point it out in case you wanted to change anything related to imports. :-)

comment:13 Changed 10 years ago by Volker Braun

Status: needs_reviewpositive_review

Good eyes with the indent ;-)

I noticed that startup modules changed. Fun fact: the operator Python module (for operator.mul, say) was imported as a by-product of Abelian groups. And the coercion framework assumes that it is imported in its doctests. I've moved the actual import to sage.all, as you saw. In any case, I'm planning to make everything lazy if possible, but first I should go through the rest of the groups and port them to the new parents.

comment:14 Changed 10 years ago by David Roe

Sounds good. Let me know when you need a review for the transition on the other groups. Thanks for all the changes here: fixing Groups has been a daunting task.

Changed 10 years ago by Volker Braun

Rebased patch

comment:15 Changed 10 years ago by Volker Braun

Patch rebased for sage-5.5.beta0

comment:16 Changed 10 years ago by Jeroen Demeyer

Status: positive_reviewneeds_work

Long doctests fail:

sage -t -long "devel/sage/sage/rings/number_field/number_field_ideal.py"
  ***   Warning: precision too low for generators, not given.
**********************************************************************
File "/release/merger/sage-5.5.beta1/devel/sage/sage/rings/number_field/number_field_ideal.py", line 2462:
    sage: G.gens_values()
Expected:
    (2*a^2 - 1, 2*a^2 + 2*a - 2)
Got:
    (2*a - 1, 2*a^2 + 2*a - 2)
**********************************************************************

Changed 10 years ago by Volker Braun

Attachment: trac_13687_review.patch added

Improved patch

comment:17 Changed 10 years ago by Volker Braun

Status: needs_workpositive_review

I've marked the offending doctest as # random , which is what it was before the patch.

comment:18 Changed 10 years ago by Jeroen Demeyer

This patch introduces some bad uses of assert. You should only use "assert" to check for actual bugs, not for bad user input. If there is any way at all to reproduce an AssertionError using documented public functions, that is by definition a bug.

comment:19 Changed 10 years ago by Jeroen Demeyer

Status: positive_reviewneeds_work
Work issues: bad use of assert

comment:20 Changed 10 years ago by Jeroen Demeyer

Most importantly, you must never use assert for control flow. So the following is very wrong:

try:
    ...
except AssertionError:
    ...

comment:21 Changed 10 years ago by Volker Braun

Description: modified (diff)
Status: needs_workneeds_review
Work issues: bad use of assert

Agreed, but its only "introduced" in the sense that I copied the old groups.pyx to old.pyx to support old-style parents until every group is switched over. I've cleaned up the AssertionError in the new group.pyx but not in the old.pyx.

Changed 10 years ago by Volker Braun

Attachment: trac_13687_assertions.patch added

Updated patch

comment:22 Changed 10 years ago by Miguel Marco

I can't seem to be able to apply the patch on sage-5.4.1 Is it rebased for some other version? Or maybe it conflicts with patches from #13211, #6391 or #13588?

comment:23 Changed 10 years ago by Volker Braun

I have based the patches on sage-5.5.rc0. Can you give that a try?

comment:24 Changed 10 years ago by Miguel Marco

Yes, that works. Thank you.

comment:25 Changed 10 years ago by Miguel Marco

So, Jeroen, would you be happy with a positive review now that the assertion issue is cleaned from the new code, but kept in the old one? Or should we make the full transition of groups before accepting this?

comment:26 Changed 10 years ago by Jeroen Demeyer

Description: modified (diff)

I combined and rebased the patches.

Version 0, edited 10 years ago by Jeroen Demeyer (next)

Changed 10 years ago by Jeroen Demeyer

comment:27 Changed 10 years ago by Jeroen Demeyer

It's not required to fix all of old.pyx. If the newly introduced assertions are fine, then that's sufficient.

comment:28 Changed 10 years ago by Volker Braun

Status: needs_reviewpositive_review

I'm fine with the rebasing... don't think there is anything else to review.

comment:29 Changed 10 years ago by Jeroen Demeyer

Status: positive_reviewneeds_work

This needs to rebased to sage-5.7.beta1.

Changed 10 years ago by Volker Braun

Updated patch

comment:30 Changed 10 years ago by Volker Braun

Rebased to sage-5.7.beta1

comment:31 Changed 10 years ago by Volker Braun

Status: needs_workpositive_review

I ran into a strange issue here: http://tracker.gap-system.org/issues/224. I've added a larger initial workspace size (-m 64m) which should be a workaround. In any case it has nothing to do with upgrading the group parents.

comment:32 Changed 10 years ago by Jeroen Demeyer

Status: positive_reviewneeds_work

There are 2 failures on 32-bit:

sage -t  --long -force_lib devel/sage/sage/rings/number_field/unit_group.py
**********************************************************************
File "/var/lib/buildbot/build/sage/arando-1/arando_full/build/sage-5.7.beta2/devel/sage-main/sage/rings/number_field/unit_group.py", line 138:
    sage: u.value()
Expected:
    -1/4*a^3 - 7/4*a^2 - 17/4*a - 19/4
Got:
    -1/4*a^3 + 7/4*a^2 - 17/4*a + 19/4
**********************************************************************
sage -t  --long -force_lib devel/sage/sage/rings/polynomial/polynomial_quotient_ring.py
**********************************************************************
File "/var/lib/buildbot/build/sage/arando-1/arando_full/build/sage-5.7.beta2/devel/sage-main/sage/rings/polynomial/polynomial_quotient_ring.py", line 974:
    sage: S.S_class_group([K.ideal(a)])
Expected:
    [((2, -a + 1, 1/2*xbar + 1/2, -1/2*a*xbar + 1/2*a + 1), 6, 1/2*xbar - 3/2)] 
Got:
    [((2, -a + 1, 1/2*xbar + 1/2, -1/2*a*xbar + 1/2*a + 1), 6, -1/2*xbar + 3/2)]
**********************************************************************

Changed 10 years ago by Volker Braun

Attachment: 13687_32bitfix.patch added

Initial patch

comment:33 Changed 10 years ago by Volker Braun

Description: modified (diff)
Status: needs_workpositive_review

I've added the necessary # 32-bit clauses...

comment:34 Changed 10 years ago by Jeroen Demeyer

Description: modified (diff)

comment:35 Changed 10 years ago by Jeroen Demeyer

Merged in: sage-5.7.beta2
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.