[sage-devel] Re: Matrix groups are not uniquely represented, why?
Update: sage: S = SymmetricGroup(4) sage: S1 = S.subgroup(S.gens()[:1]) sage: S2 = S.subgroup(S.gens()[:1]) sage: S1 is S2 False Since the same is true for subgroups of permutation groups, I wonder if this is intended? The reason I am asking is that I implemented abelian groups and their automorphisms with gap sage.groups.abelian_gps.abelian_group_gap sage.groups.abelian_gps. abelian_aut using unique representations for subgroups. I did I miss something? -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Matrix groups are not uniquely represented, why?
I believe the matrix and permutation groups are quite old code, so UniqueRepresentation may not have been available at that time. The permutation group code does need updating; in particular, it is still an old-style parent: sage: S.__class__.__mro__ (, , , , , , , , , , , , ... (Side note: We also should not be importing things like PermutationGroup_generic and PermutationGroupMorphism_id into the global namespace.) I don't see a reason off-hand why these should not be UniqueRepresentation subclasses. Best, Travis -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Matrix groups are not uniquely represented, why?
On Friday, May 25, 2018 at 1:00:22 AM UTC-7, Travis Scrimshaw wrote: > > I believe the matrix and permutation groups are quite old code, so > UniqueRepresentation may not have been available at that time. The > permutation group code does need updating; in particular, it is still an > old-style parent: > > sage: S.__class__.__mro__ > ( 'sage.groups.perm_gps.permgroup_named.SymmetricGroup_with_category'>, > , > , > , > , > , > , > , > , > , > , > , > ... > > (Side note: We also should not be importing things like > PermutationGroup_generic and PermutationGroupMorphism_id into the global > namespace.) > > I don't see a reason off-hand why these should not be UniqueRepresentation > subclasses. > There is a very good reason why they should NOT'. Equality between subgroups is not uniquely determined by the construction parameters. It's part of the API of UniqueRepresentation that equality is identity on them. Also, UniqueRepresentation objects make it much harder to write predictable code: because they're global objects they really MUST be immutable. No cheating! That's often quite inconvenient. Also, the processing of the construction parameters is possibly more expensive than the construction itself, so they may degrade performance. Furthermore, they have proven time and again to be very prone to memory leaks, to the point where I'd now work on the assumption that if you change an object to UniqueRepresentation, you're introducing memory leaks various places. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Matrix groups are not uniquely represented, why?
Hi! On 2018-05-25, Nils Bruin wrote: >> I don't see a reason off-hand why these should not be UniqueRepresentation >> subclasses. >> > > There is a very good reason why they should NOT'. Equality between > subgroups is not uniquely determined by the construction parameters. It's > part of the API of UniqueRepresentation that equality is identity on them. But they could still be CachedRepresentation. Then, if the same subgroup is given by the same generators, it is identical, but if the same subgroup is given by different generators, it is just equal but not identical. Best regards, Simon -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Matrix groups are not uniquely represented, why?
On Friday, May 25, 2018 at 12:17:35 PM UTC-7, Simon King wrote: > > But they could still be CachedRepresentation. Then, if the same subgroup > is given by the same generators, it is identical, but if the same > subgroup is given by different generators, it is just equal but not > identical. > > But before doing so, you would need to show that in common scenarios it produces a benefit. It has three significant draw-backs: - you'd slow down the creation of matrix groups in general, because you're requiring the system to first go and look if there already is an object like it. - because the object you get *may* be shared with other code, you're at the mercy of that other code to not mutate it. (and you have to behave yourself too) - it would likely introduce memory leaks (because it's the CachedRepresentation part of UniqueRepresentation that makes these leaks likely). -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Matrix groups are not uniquely represented, why?
MatrixGroups are immutable and their comparison is by checking the generators (and not isomorphism), which are essentially the construction parameters (in reality, they are the corresponding GAP group). For permutation groups, the equality seems to be isomorphism. So there is no problem for MatrixGroups being UniqueRepresentation in terms of behavior. Best, Travis On Saturday, May 26, 2018 at 5:53:15 AM UTC+10, Nils Bruin wrote: > > > > On Friday, May 25, 2018 at 12:17:35 PM UTC-7, Simon King wrote: >> >> But they could still be CachedRepresentation. Then, if the same subgroup >> is given by the same generators, it is identical, but if the same >> subgroup is given by different generators, it is just equal but not >> identical. >> >> But before doing so, you would need to show that in common scenarios it > produces a benefit. It has three significant draw-backs: > - you'd slow down the creation of matrix groups in general, because > you're requiring the system to first go and look if there already is an > object like it. > - because the object you get *may* be shared with other code, you're at > the mercy of that other code to not mutate it. (and you have to behave > yourself too) > - it would likely introduce memory leaks (because it's the > CachedRepresentation part of UniqueRepresentation that makes these leaks > likely). > > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Matrix groups are not uniquely represented, why?
Hi Erik
On 2018-05-28, Erik Bray wrote:
> I think Sage could use a better way to keep
> track of and/or enforce immutability of classes (that is, instances of
> classes). For example, have some base class which can be used as a
> mix-in (or an ABC) that designates something as immutable, and
> disallow assigning any attributes to its dict that aren't also
> immutable (including of course support for all the common built-in
> types).
I don't think this could possibly work. But actually that's not a Sage
problem but a Python problem: Perhaps somewhere in the Python ecosystem
such a mix-in class exists?
However, I find your notion of immutability ("do not allow assigning
attributes and make all existing attributes immutable") far too narrow.
IIRC, immutable means that once the object is created, its equivalence
class with respect to the "==" operator will be preserved no matter what
of its (no-underscore?) methods are called.
Thus, I believe it must be allowed to assign to an attribute of object X,
as long as the behaviour of X==Y remains unchanged for all objects Y
(and of course hash(X) doesn't change either).
Best regards,
Simon
--
You received this message because you are subscribed to the Google Groups
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Matrix groups are not uniquely represented, why?
On Monday, May 28, 2018 at 7:24:31 AM UTC-7, Simon King wrote:
>
> However, I find your notion of immutability ("do not allow assigning
> attributes and make all existing attributes immutable") far too narrow.
> IIRC, immutable means that once the object is created, its equivalence
> class with respect to the "==" operator will be preserved no matter what
> of its (no-underscore?) methods are called.
>
> Thus, I believe it must be allowed to assign to an attribute of object X,
> as long as the behaviour of X==Y remains unchanged for all objects Y
> (and of course hash(X) doesn't change either).
>
That's a definition of "immutable" that suffices for using things as keys
in dictionaries. However, if the object you created might be referenced
elsewhere, in totally unrelated code (because that code happens to have
called PolynomialRing(Rationals(),names=['x','y']) as well) then you need
to be a *lot* more careful. I'm not sure that locking some objects
completely from mutation would be a feasible solution (it will be nearly
impossible to enforce in python, and we might not be able to get proper
performance with it), but if programmers don't take this very seriously
we'll end up with a code base that is very difficult to reason about.
The conflation of the two notions of immutability, and the different levels
of enforcement required for them, is what worries me about
UniqueRepresentation. Originally, the use of UniqueRepresentation was
required to ensure the system could *repeatedly* produce identical objects
automatically, based on input parameters, see
https://trac.sagemath.org/ticket/25388#comment:10 . It has the side-effect
of allowing quick equality-by-identity checking. So it may *look* like
UniqueRepresentation is a great way of speeding up "==" and "hash" for
things that are immutable, but it requires a much higher level of
immutability than required for hash.
(and in practice, the memory leaks caused by UniqueRepresentation bite us
with clockwork regularity)
--
You received this message because you are subscribed to the Google Groups
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Matrix groups are not uniquely represented, why?
As a simple-minded user I stumbled over exactly this last week. I don't understand much of what this thread is discussing, but I know what a simple-minded user wants. sage: G = GL(2,13) sage: G = G.as_matrix_group() sage: H = G.subgroup([ matrix(GF(13),[[1,0],[1,1]]) ]) sage: H2 = G.subgroup([ matrix(GF(13),[[1,1],[0,1]]) ]) sage: H3 = G.subgroup([ matrix(GF(13),[[1,0],[2,1]]) ]) I expect H == H3 to say True as they are the same subgroup. I expect H = H2 to say False, since they are not the same subgroup, even though they are isomorphic. Instead sage: H == H3 False sage: matrix(GF(13),[[1,0],[1,1]]) in H3 True sage: matrix(GF(13),[[1,0],[2,1]]) in H True sage: H.is_isomorphic(H3) True sage: H.is_isomorphic(H2) True sage: matrix(GF(13),[[1,0],[1,1]]) in H2 False I though of working around it by checking if they are the same as sets, but to my surprise: sage: Set( h for h in H ) == Set( h for h in H3 ) False sage: Set( h.matrix() for h in H ) == Set( h.matrix() for h in H3 ) True In short: I consider this a bug. No matter how this is done at the back, the user expects == to mean mathematical equality, here equality of subgroups. Otherwise the function should be called subgroups_with_given_generators. Chris -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Matrix groups are not uniquely represented, why?
On Tuesday, May 29, 2018 at 9:01:51 PM UTC+10, chris wuthrich wrote: > > > As a simple-minded user I stumbled over exactly this last week. I don't > understand much of what this thread is discussing, but I know what a > simple-minded user wants. > > sage: G = GL(2,13) > sage: G = G.as_matrix_group() > sage: H = G.subgroup([ matrix(GF(13),[[1,0],[1,1]]) ]) > sage: H2 = G.subgroup([ matrix(GF(13),[[1,1],[0,1]]) ]) > sage: H3 = G.subgroup([ matrix(GF(13),[[1,0],[2,1]]) ]) > > I expect H == H3 to say True as they are the same subgroup. > I expect H = H2 to say False, since they are not the same subgroup, even > though they are isomorphic. > Instead > > sage: H == H3 > False > sage: matrix(GF(13),[[1,0],[1,1]]) in H3 > True > sage: matrix(GF(13),[[1,0],[2,1]]) in H > True > sage: H.is_isomorphic(H3) > True > sage: H.is_isomorphic(H2) > True > sage: matrix(GF(13),[[1,0],[1,1]]) in H2 > False > > I though of working around it by checking if they are the same as sets, > but to my surprise: > > sage: Set( h for h in H ) == Set( h for h in H3 ) > False > sage: Set( h.matrix() for h in H ) == Set( h.matrix() for h in H3 ) > True > > In short: I consider this a bug. No matter how this is done at the back, > the user expects == to mean mathematical equality, here equality of > subgroups. Otherwise the function should be called > subgroups_with_given_generators. > > I think it is a bad thing in this case for == to be equality as sets. Imagine if these are two really big, equal, but differently constructed subgroups. This would be a really long and expensive check, whereas in most cases, checking the defining objects are sufficient. I believe we have other places in Sage where == is not strict mathematical equality for similar reasons. -1 on changing the == semantics here. Now I would say the equality as sets (which really comes down to equality of elements) is a bug. Two matrix group elements should compare by their matrices and not have the coercion system involved otherwise. My guess is the coercion system tries to convert the elements of H into H3 and vice versa, which is cannot do, and hence, results in a False for equality. This probably requires a reimplementation of the comparison method of matrix group elements. Best, Travis -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Matrix groups are not uniquely represented, why?
> I think it is a bad thing in this case for == to be equality as sets. > Imagine if these are two really big, equal, but differently constructed > subgroups. This would be a really long and expensive check, whereas in most > cases, checking the defining objects are sufficient. I believe we have > other places in Sage where == is not strict mathematical equality for > similar reasons. -1 on changing the == semantics here. > > I am strongly in favour of changing all the other instances of wrong ==; or, at least, that they are well documented aberations. Or that we rename things (like subgroups_with_generator) to make it mathematically correct again. If ever a user wants to check that the two subgroups were given by the same generators then he will check if .gens() are equal. Otherwise he will know that it may take time to test equality, just like with any other function. I am happy with John's example of quadratic fields. The QQ-algebras QuadraticField(2) and QuadraticField(8) are not equal in any canonical thing they are contained in as there are two isomorphisms between them. > Now I would say the equality as sets (which really comes down to equality > of elements) is a bug. Two matrix group elements should compare by their > matrices and not have the coercion system involved otherwise. My guess is > the coercion system tries to convert the elements of H into H3 and vice > versa, which is cannot do, and hence, results in a False for equality. This > probably requires a reimplementation of the comparison method of matrix > group elements. > Yes, fully agree. In fact elements should not have a "matrix" at all, since they are matrices by definition to the user. The element class, like many other group things, may want to be worked over completely. I am also often unhappy about PGL, which returns a permutation group, by the way. Chris -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Matrix groups are not uniquely represented, why?
On Wednesday, May 30, 2018 at 1:35:43 AM UTC-7, chris wuthrich wrote: > I am also often unhappy about PGL, which returns a permutation group, by > the way. > Well, that's not a matrix group in a canonical way, so there's a good reason for that (and, if you're interested in the abstract group it may well be that the permutation representation is the fastest to work with). -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Matrix groups are not uniquely represented, why?
> Well, that's not a matrix group in a canonical way, so there's a good reason for that (and, if you're interested in the abstract group it may well be that the permutation representation is the fastest to work with). Agree, but it would be nice to say G = PGL(2,13) and then G(some matrix) to get its class or backwards to represent an element by a matrix, etc. But that is a different stroy than what this tread was about. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Matrix groups are not uniquely represented, why?
Hi Simon, On 2018-06-01, Simon Brandhorst wrote: > (1) Use unique representation for "ambient" objects ( GL(n,k), O(n,k,e), > QQ^n). +1, unless you say that each set (including a subset of something) is an ambient object. > (2) Do not use unique representation for subobjects. +1, except for subobjects that can be considered "ambient" themselves (such as: The set of prime numbers in the set of integers; or GL(n,k) in MatrixSpace(k,n)) > (3) Give the .subobject(self, gens) method a (weak?) cache. +1, provided that it doesn't add memory leaks. > (4) Modify == to test equality as subobjects/subsets. -1, as I tend to think of "==" as a QUICK test. If testing equality has a potential to hit decision problems (which certainly is the case for subgroups), then "==" should give a swift "True" if the two objects are easily seen to be equal (by equality of the set of generators, say), and should return "False" otherwise. In these cases, there ought to be a special method that the user will only call if s/he really is prepared to wait for the answer for a couple of hours. Note that in a way it would be nice if "==" had a ternary logic "True/False/Unknown". But Python isn't there yet (although I do recall that there used to be a PEP for it). Best regards, Simon -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Matrix groups are not uniquely represented, why?
> > (4) Modify == to test equality as subobjects/subsets. > > -1, as I tend to think of "==" as a QUICK test. > > If testing equality has a potential to hit decision problems (which > certainly is the case for subgroups), then "==" should give a swift > "True" if the two objects are easily seen to be equal (by equality of > the set of generators, say), and should return "False" otherwise. > > In these cases, there ought to be a special method that the user will only > call if s/he really is prepared to wait for the answer for a couple of > hours. > > Note that in a way it would be nice if "==" had a ternary logic > "True/False/Unknown". But Python isn't there yet (although I do recall > that there used to be a PEP for it). > > I am also generally in favor of having == being a (generally) fast check. However, the symbolics code takes the opposite approach: it has the method is_trivial_equal() for quick checks but == fires up the proof engine. In terms of surprise, the fast == is clearly worse, but using is_trivially_equal() makes the code harder to read and maintain (often because of inconsistent use in regards to speed regressions). Best, Travis -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Matrix groups are not uniquely represented, why?
Hi Travis, On 2018-06-03, Travis Scrimshaw wrote: > I am also generally in favor of having == being a (generally) fast check. > However, the symbolics code takes the opposite approach: it has the method > is_trivial_equal() for quick checks but == fires up the proof engine. No, that's not correct. For symbolics, "==" only does trivial checks and leaves the equality unevaluated otherwise, so that you need an explicit evaluation as a bool in order to force a non-trivial computation. Such as: sage: (x+1)^2 == x^2+2*x+1 (x + 1)^2 == x^2 + 2*x + 1 sage: bool(_) True Best regards, Simon -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Matrix groups are not uniquely represented, why?
Sun 2018-06-03 11:33:16 UTC, Simon King: > > For symbolics, "==" only does trivial checks and leaves the equality > unevaluated otherwise, so that you need an explicit evaluation as a > bool in order to force a non-trivial computation. > > Such as: > > sage: (x+1)^2 == x^2+2*x+1 > (x + 1)^2 == x^2 + 2*x + 1 > sage: bool(_) > True Actually, for symbolics, "==" always creates an equation, and never tries to evaluate it! A lot of confusion stems from the fact that what "==" does depends on whether both sides are symbolic: - if neither side is symbolic, it tests equality - if either side is symbolic, it creates an equation Once an equation has been created, to evaluate whether the equation holds, one can use "bool". Compare: sage: 0 == 1 False sage: SR(0) == 1 0 == 1 sage: 0 == SR(1) 0 == 1 sage: SR(0) == SR(1) 0 == 1 -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Matrix groups are not uniquely represented, why?
On 2018-06-03, Simon King wrote: > Hi Travis, > > On 2018-06-03, Travis Scrimshaw wrote: >> I am also generally in favor of having == being a (generally) fast check. >> However, the symbolics code takes the opposite approach: it has the method >> is_trivial_equal() for quick checks but == fires up the proof engine. > > No, that's not correct. > > For symbolics, "==" only does trivial checks That's not correct either. "==" apparently always returns an equation, not a bool. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Matrix groups are not uniquely represented, why?
Travis Scrimshaw wrote: > In terms of surprise, the fast == is clearly worse, It is not that clear to me! (What I think I'd expect if I didn't know Sage would be for == to compare the representation of the objects, not their mathematical semantics, even when that semantics is unambiguous.) -- Marc -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Matrix groups are not uniquely represented, why?
On Sunday, June 3, 2018 at 9:56:01 PM UTC+10, Simon King wrote:
>
> On 2018-06-03, Simon King > wrote:
> > Hi Travis,
> >
> > On 2018-06-03, Travis Scrimshaw >
> wrote:
> >> I am also generally in favor of having == being a (generally) fast
> check.
> >> However, the symbolics code takes the opposite approach: it has the
> method
> >> is_trivial_equal() for quick checks but == fires up the proof engine.
> >
> > No, that's not correct.
> >
> > For symbolics, "==" only does trivial checks
>
> That's not correct either. "==" apparently always returns an equation,
> not a bool.
>
>
Sorry, I was thinking of in the context of evaluating a boolean statement
(such as "if x == y"). However, when checking the truth value of an
expression, it does fire up the full engine:
sage: x = var('x')
sage: f = sin(x)^2 + cos(x)^2
sage: f
cos(x)^2 + sin(x)^2
sage: %timeit bool(f == 1)
10 loops, best of 3: 22.2 ms per loop
sage: %timeit f.is_trivially_equal(1)
The slowest run took 11394.28 times longer than the fastest. This could
mean that an intermediate result is being cached.
100 loops, best of 3: 1.67 µs per loop
sage: bool(f == 1)
True
sage: f.is_trivially_equal(1)
False
If it was doing something trivial, both outputs would be the same and there
would be far less time taken to evaluate the bool.
Best,
Travis
--
You received this message because you are subscribed to the Google Groups
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Matrix groups are not uniquely represented, why?
On Sat, May 26, 2018 at 6:24 AM, Travis Scrimshaw wrote: > MatrixGroups are immutable and their comparison is by checking the > generators (and not isomorphism), which are essentially the construction > parameters (in reality, they are the corresponding GAP group). For > permutation groups, the equality seems to be isomorphism. So there is no > problem for MatrixGroups being UniqueRepresentation in terms of behavior. +1 in principle. Nils has said to me as well that UniqueRepresention (or even simply CachedRepresentation) is known for introducing memory leaks. I certainly believe that--one doesn't come to such a conclusion without hard-earned experience. But I'm skeptical that that's something inherent to its design that can't be overcome with correct use. Obviously it should not be used with classes that are not truly immutable. I think Sage could use a better way to keep track of and/or enforce immutability of classes (that is, instances of classes). For example, have some base class which can be used as a mix-in (or an ABC) that designates something as immutable, and disallow assigning any attributes to its dict that aren't also immutable (including of course support for all the common built-in types). Of course, getting something like that right is not completely trivial and would require a lot of overhaul. I'm just surprised that it isn't already something that is considered more systematically. > On Saturday, May 26, 2018 at 5:53:15 AM UTC+10, Nils Bruin wrote: >> >> >> >> On Friday, May 25, 2018 at 12:17:35 PM UTC-7, Simon King wrote: >>> >>> But they could still be CachedRepresentation. Then, if the same subgroup >>> is given by the same generators, it is identical, but if the same >>> subgroup is given by different generators, it is just equal but not >>> identical. >>> >> But before doing so, you would need to show that in common scenarios it >> produces a benefit. It has three significant draw-backs: >> - you'd slow down the creation of matrix groups in general, because >> you're requiring the system to first go and look if there already is an >> object like it. >> - because the object you get *may* be shared with other code, you're at >> the mercy of that other code to not mutate it. (and you have to behave >> yourself too) >> - it would likely introduce memory leaks (because it's the >> CachedRepresentation part of UniqueRepresentation that makes these leaks >> likely). >> > > -- > You received this message because you are subscribed to the Google Groups > "sage-devel" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to sage-devel+unsubscr...@googlegroups.com. > To post to this group, send email to sage-devel@googlegroups.com. > Visit this group at https://groups.google.com/group/sage-devel. > For more options, visit https://groups.google.com/d/optout. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Matrix groups are not uniquely represented, why?
On 29 May 2018 at 12:01, chris wuthrich wrote: > > As a simple-minded user I stumbled over exactly this last week. I don't > understand much of what this thread is discussing, but I know what a > simple-minded user wants. > > sage: G = GL(2,13) > sage: G = G.as_matrix_group() > sage: H = G.subgroup([ matrix(GF(13),[[1,0],[1,1]]) ]) > sage: H2 = G.subgroup([ matrix(GF(13),[[1,1],[0,1]]) ]) > sage: H3 = G.subgroup([ matrix(GF(13),[[1,0],[2,1]]) ]) > > I expect H == H3 to say True as they are the same subgroup. > I expect H = H2 to say False, since they are not the same subgroup, even > though they are isomorphic. > Instead > > sage: H == H3 > False > sage: matrix(GF(13),[[1,0],[1,1]]) in H3 > True > sage: matrix(GF(13),[[1,0],[2,1]]) in H > True > sage: H.is_isomorphic(H3) > True > sage: H.is_isomorphic(H2) > True > sage: matrix(GF(13),[[1,0],[1,1]]) in H2 > False > > I though of working around it by checking if they are the same as sets, > but to my surprise: > > sage: Set( h for h in H ) == Set( h for h in H3 ) > False > sage: Set( h.matrix() for h in H ) == Set( h.matrix() for h in H3 ) > True > > In short: I consider this a bug. No matter how this is done at the back, > the user expects == to mean mathematical equality, here equality of > subgroups. Otherwise the function should be called subgroups_with_given_ > generators. > This is not the only place in Sage where there is hidden structure which equality testing uses. sage: QuadraticField(2) == QuadraticField(8) False This looks wrong if you naively think that you are defining a subset of CC or RR. But number fields in Sage are all defined with a fixed generating element, i.e. they are not just QQ-algebras but QQ[X]-algebras. In the matrix subgroup case it is hard to see how H and the other subgroups are intended to be viewed if not as subsets of G. (By the way, your code raises an error for me in the assignment to H I get AttributeError: 'sage.matrix.matrix_modn_dense_float.Matrix_modn_dense_float' object has no attribute 'gap' ) > > > Chris > > -- > You received this message because you are subscribed to the Google Groups > "sage-devel" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to sage-devel+unsubscr...@googlegroups.com. > To post to this group, send email to sage-devel@googlegroups.com. > Visit this group at https://groups.google.com/group/sage-devel. > For more options, visit https://groups.google.com/d/optout. > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Matrix groups are not uniquely represented, why?
On Mon, May 28, 2018 at 4:22 PM, Simon King wrote:
> Hi Erik
>
> On 2018-05-28, Erik Bray wrote:
>> I think Sage could use a better way to keep
>> track of and/or enforce immutability of classes (that is, instances of
>> classes). For example, have some base class which can be used as a
>> mix-in (or an ABC) that designates something as immutable, and
>> disallow assigning any attributes to its dict that aren't also
>> immutable (including of course support for all the common built-in
>> types).
>
> I don't think this could possibly work. But actually that's not a Sage
> problem but a Python problem: Perhaps somewhere in the Python ecosystem
> such a mix-in class exists?
>
> However, I find your notion of immutability ("do not allow assigning
> attributes and make all existing attributes immutable") far too narrow.
> IIRC, immutable means that once the object is created, its equivalence
> class with respect to the "==" operator will be preserved no matter what
> of its (no-underscore?) methods are called.
>
> Thus, I believe it must be allowed to assign to an attribute of object X,
> as long as the behaviour of X==Y remains unchanged for all objects Y
> (and of course hash(X) doesn't change either).
To be clear, I'm not even talking about *enforcing* immutability; in
Python that is impossible. I'm just talking about bookkeeping
indicating that objects of a class should be considered immutable, and
this fact discoverable through introspection (possibly with a small
amount of intelligence where possible, but certainly not guaranteeing
protection from programmer error).
--
You received this message because you are subscribed to the Google Groups
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Matrix groups are not uniquely represented, why?
On 30 May 2018 at 07:14, Travis Scrimshaw wrote: > > > On Tuesday, May 29, 2018 at 9:01:51 PM UTC+10, chris wuthrich wrote: >> >> >> As a simple-minded user I stumbled over exactly this last week. I don't >> understand much of what this thread is discussing, but I know what a >> simple-minded user wants. >> >> sage: G = GL(2,13) >> sage: G = G.as_matrix_group() >> sage: H = G.subgroup([ matrix(GF(13),[[1,0],[1,1]]) ]) >> sage: H2 = G.subgroup([ matrix(GF(13),[[1,1],[0,1]]) ]) >> sage: H3 = G.subgroup([ matrix(GF(13),[[1,0],[2,1]]) ]) >> >> I expect H == H3 to say True as they are the same subgroup. >> I expect H = H2 to say False, since they are not the same subgroup, even >> though they are isomorphic. >> Instead >> >> sage: H == H3 >> False >> sage: matrix(GF(13),[[1,0],[1,1]]) in H3 >> True >> sage: matrix(GF(13),[[1,0],[2,1]]) in H >> True >> sage: H.is_isomorphic(H3) >> True >> sage: H.is_isomorphic(H2) >> True >> sage: matrix(GF(13),[[1,0],[1,1]]) in H2 >> False >> >> I though of working around it by checking if they are the same as sets, >> but to my surprise: >> >> sage: Set( h for h in H ) == Set( h for h in H3 ) >> False >> sage: Set( h.matrix() for h in H ) == Set( h.matrix() for h in H3 ) >> True >> >> In short: I consider this a bug. No matter how this is done at the back, >> the user expects == to mean mathematical equality, here equality of >> subgroups. Otherwise the function should be called >> subgroups_with_given_generators. >> >> I think it is a bad thing in this case for == to be equality as sets. > Imagine if these are two really big, equal, but differently constructed > subgroups. This would be a really long and expensive check, whereas in most > cases, checking the defining objects are sufficient. I believe we have > other places in Sage where == is not strict mathematical equality for > similar reasons. -1 on changing the == semantics here. > We should then admit that users will regularly be surprised. Perhaps this is similar to the situation for evaluating boolean expressions, where (I seem to remember) False is returned in case of "don't know". Any subgroup constructor (e.g. from generators) which results in a subgroup for which testing membership is impossible (or worse, silently returns False for every element of the ambient group) is surely not going to be very useful; and if there is a membership test then testing two subgroups for equality is easy (though of course possibly slow). In summary, if we implement subgroups in such a way that testing equality is not implemented then it is very misleading to return False every time. > > Now I would say the equality as sets (which really comes down to equality > of elements) is a bug. Two matrix group elements should compare by their > matrices and not have the coercion system involved otherwise. My guess is > the coercion system tries to convert the elements of H into H3 and vice > versa, which is cannot do, and hence, results in a False for equality. This > probably requires a reimplementation of the comparison method of matrix > group elements. > +1 to that. > > Best, > Travis > > -- > You received this message because you are subscribed to the Google Groups > "sage-devel" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to sage-devel+unsubscr...@googlegroups.com. > To post to this group, send email to sage-devel@googlegroups.com. > Visit this group at https://groups.google.com/group/sage-devel. > For more options, visit https://groups.google.com/d/optout. > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Matrix groups are not uniquely represented, why?
> In summary, if we implement subgroups in such a way that testing equality is not implemented then it is very misleading to return False every time. I've run into this issue before (that two subgroups of the same ambient matrix group can compare as unequal, despite having the same elements). See https://trac.sagemath.org/ticket/24301, where there is some discussion between Travis and me whether this should be considered a bug. (Of course, however one feels about that matter, there is no question that testing Set( h for h in H ) == Set( h for h in H3 ) should return True and anything else is a definite bug.) David On 30 May 2018 at 09:06, John Cremona wrote: > > > On 30 May 2018 at 07:14, Travis Scrimshaw wrote: > >> >> >> On Tuesday, May 29, 2018 at 9:01:51 PM UTC+10, chris wuthrich wrote: >>> >>> >>> As a simple-minded user I stumbled over exactly this last week. I don't >>> understand much of what this thread is discussing, but I know what a >>> simple-minded user wants. >>> >>> sage: G = GL(2,13) >>> sage: G = G.as_matrix_group() >>> sage: H = G.subgroup([ matrix(GF(13),[[1,0],[1,1]]) ]) >>> sage: H2 = G.subgroup([ matrix(GF(13),[[1,1],[0,1]]) ]) >>> sage: H3 = G.subgroup([ matrix(GF(13),[[1,0],[2,1]]) ]) >>> >>> I expect H == H3 to say True as they are the same subgroup. >>> I expect H = H2 to say False, since they are not the same subgroup, even >>> though they are isomorphic. >>> Instead >>> >>> sage: H == H3 >>> False >>> sage: matrix(GF(13),[[1,0],[1,1]]) in H3 >>> True >>> sage: matrix(GF(13),[[1,0],[2,1]]) in H >>> True >>> sage: H.is_isomorphic(H3) >>> True >>> sage: H.is_isomorphic(H2) >>> True >>> sage: matrix(GF(13),[[1,0],[1,1]]) in H2 >>> False >>> >>> I though of working around it by checking if they are the same as sets, >>> but to my surprise: >>> >>> sage: Set( h for h in H ) == Set( h for h in H3 ) >>> False >>> sage: Set( h.matrix() for h in H ) == Set( h.matrix() for h in H3 ) >>> True >>> >>> In short: I consider this a bug. No matter how this is done at the back, >>> the user expects == to mean mathematical equality, here equality of >>> subgroups. Otherwise the function should be called >>> subgroups_with_given_generators. >>> >>> I think it is a bad thing in this case for == to be equality as sets. >> Imagine if these are two really big, equal, but differently constructed >> subgroups. This would be a really long and expensive check, whereas in most >> cases, checking the defining objects are sufficient. I believe we have >> other places in Sage where == is not strict mathematical equality for >> similar reasons. -1 on changing the == semantics here. >> > > We should then admit that users will regularly be surprised. Perhaps this > is similar to the situation for evaluating boolean expressions, where (I > seem to remember) False is returned in case of "don't know". Any subgroup > constructor (e.g. from generators) which results in a subgroup for which > testing membership is impossible (or worse, silently returns False for > every element of the ambient group) is surely not going to be very useful; > and if there is a membership test then testing two subgroups for equality > is easy (though of course possibly slow). > > In summary, if we implement subgroups in such a way that testing equality > is not implemented then it is very misleading to return False every time. > > >> >> Now I would say the equality as sets (which really comes down to equality >> of elements) is a bug. Two matrix group elements should compare by their >> matrices and not have the coercion system involved otherwise. My guess is >> the coercion system tries to convert the elements of H into H3 and vice >> versa, which is cannot do, and hence, results in a False for equality. This >> probably requires a reimplementation of the comparison method of matrix >> group elements. >> > > +1 to that. > > >> >> Best, >> Travis >> >> -- >> You received this message because you are subscribed to the Google Groups >> "sage-devel" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to sage-devel+unsubscr...@googlegroups.com. >> To post to this group, send email to sage-devel@googlegroups.com. >> Visit this group at https://groups.google.com/group/sage-devel. >> For more options, visit https://groups.google.com/d/optout. >> > > -- > You received this message because you are subscribed to the Google Groups > "sage-devel" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to sage-devel+unsubscr...@googlegroups.com. > To post to this group, send email to sage-devel@googlegroups.com. > Visit this group at https://groups.google.com/group/sage-devel. > For more options, visit https://groups.google.com/d/optout. > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post
Re: [sage-devel] Re: Matrix groups are not uniquely represented, why?
On Mon, May 28, 2018 at 6:11 PM, Nils Bruin wrote:
> On Monday, May 28, 2018 at 7:24:31 AM UTC-7, Simon King wrote:
>>
>> However, I find your notion of immutability ("do not allow assigning
>> attributes and make all existing attributes immutable") far too narrow.
>> IIRC, immutable means that once the object is created, its equivalence
>> class with respect to the "==" operator will be preserved no matter what
>> of its (no-underscore?) methods are called.
>>
>> Thus, I believe it must be allowed to assign to an attribute of object X,
>> as long as the behaviour of X==Y remains unchanged for all objects Y
>> (and of course hash(X) doesn't change either).
>
>
> That's a definition of "immutable" that suffices for using things as keys in
> dictionaries. However, if the object you created might be referenced
> elsewhere, in totally unrelated code (because that code happens to have
> called PolynomialRing(Rationals(),names=['x','y']) as well) then you need to
> be a *lot* more careful. I'm not sure that locking some objects completely
> from mutation would be a feasible solution (it will be nearly impossible to
> enforce in python, and we might not be able to get proper performance with
> it), but if programmers don't take this very seriously we'll end up with a
> code base that is very difficult to reason about.
>
> The conflation of the two notions of immutability, and the different levels
> of enforcement required for them, is what worries me about
> UniqueRepresentation. Originally, the use of UniqueRepresentation was
> required to ensure the system could *repeatedly* produce identical objects
> automatically, based on input parameters, see
> https://trac.sagemath.org/ticket/25388#comment:10 . It has the side-effect
> of allowing quick equality-by-identity checking. So it may *look* like
> UniqueRepresentation is a great way of speeding up "==" and "hash" for
> things that are immutable, but it requires a much higher level of
> immutability than required for hash.
>
> (and in practice, the memory leaks caused by UniqueRepresentation bite us
> with clockwork regularity)
Could you actually point me to one of those memory leaks? I'm sure
they exist but I'm still not clear on how this happens. I suspect it
could be improved, and I would like to look into how...
--
You received this message because you are subscribed to the Google Groups
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Matrix groups are not uniquely represented, why?
On Wed, May 30, 2018 at 8:14 AM, Travis Scrimshaw wrote: > > > On Tuesday, May 29, 2018 at 9:01:51 PM UTC+10, chris wuthrich wrote: >> >> >> As a simple-minded user I stumbled over exactly this last week. I don't >> understand much of what this thread is discussing, but I know what a >> simple-minded user wants. >> >> sage: G = GL(2,13) >> sage: G = G.as_matrix_group() >> sage: H = G.subgroup([ matrix(GF(13),[[1,0],[1,1]]) ]) >> sage: H2 = G.subgroup([ matrix(GF(13),[[1,1],[0,1]]) ]) >> sage: H3 = G.subgroup([ matrix(GF(13),[[1,0],[2,1]]) ]) >> >> I expect H == H3 to say True as they are the same subgroup. >> I expect H = H2 to say False, since they are not the same subgroup, even >> though they are isomorphic. >> Instead >> >> sage: H == H3 >> False >> sage: matrix(GF(13),[[1,0],[1,1]]) in H3 >> True >> sage: matrix(GF(13),[[1,0],[2,1]]) in H >> True >> sage: H.is_isomorphic(H3) >> True >> sage: H.is_isomorphic(H2) >> True >> sage: matrix(GF(13),[[1,0],[1,1]]) in H2 >> False >> >> I though of working around it by checking if they are the same as sets, >> but to my surprise: >> >> sage: Set( h for h in H ) == Set( h for h in H3 ) >> False >> sage: Set( h.matrix() for h in H ) == Set( h.matrix() for h in H3 ) >> True >> >> In short: I consider this a bug. No matter how this is done at the back, >> the user expects == to mean mathematical equality, here equality of >> subgroups. Otherwise the function should be called >> subgroups_with_given_generators. "mathematical equality" is also a red herring being that there are many possible definitions thereof. Are we talking equality up to isomorphism? Etc... -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Matrix groups are not uniquely represented, why?
On Thursday, May 31, 2018 at 3:07:11 AM UTC-7, Erik Bray wrote: > > > "mathematical equality" is also a red herring being that there are > many possible definitions thereof. Are we talking equality up to > isomorphism? Etc... > In this case it is not: presenting a group as a matrix groups means giving the group as a subgroup of GL(n,k). you could argue over WHICH GL(n,k) because we could have many isomorphic copies of those lying around, but we don't: sage: G1=GL(2,GF(7)) sage: G2=GL(2,GF(7)) sage: G1 is G2 True so in Sage there is one copy of GL(n,k) that is canonized. After that it is completely clear what equality must mean: equality as subgroup. Of course, we can look at conjugacy and (for the GL's that have outer automorphisms) more generally isomorphism, but those are different questions. Presently, matrix groups are really just "generator lists" for their equality test: sage: H1=G1.subgroup([G1.1,G1.1^2]) sage: H2=G1.subgroup([G1.1^2,G1.1]) sage: H1 == H2 False I'm suspicious that, although defining equality like that makes it easy to do some basic algorithmic stuff with them, such as stuffing them in a set etc., it doesn't actually help with actually working with the objects. But perhaps there are convincing examples that show that having a very cheap but wrong equality test must available for infrastructure reasons. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Matrix groups are not uniquely represented, why?
On 31 May 2018 at 11:07, Erik Bray wrote: > > "mathematical equality" is also a red herring being that there are > many possible definitions thereof. Are we talking equality up to > isomorphism? Etc... In the example posted by Chris Wuthrich, all the objects invoved were, by construction, subgroups of a common ambient group (in this case G = GF(2, 13)). In this case there is one and only one notion of equality which makes sense, and that is "having the same elements". David -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Matrix groups are not uniquely represented, why?
On Thursday, May 31, 2018 at 3:05:26 AM UTC-7, Erik Bray wrote: > > > Could you actually point me to one of those memory leaks? I'm sure > they exist but I'm still not clear on how this happens. I suspect it > could be improved, and I would like to look into how... > https://trac.sagemath.org/ticket/17008#comment:13 (prediction) https://trac.sagemath.org/ticket/23851 https://trac.sagemath.org/ticket/23807#comment:14 (explanation) https://trac.sagemath.org/ticket/14549#comment:6 https://trac.sagemath.org/ticket/18426 https://trac.sagemath.org/ticket/14356 https://trac.sagemath.org/ticket/17360 https://trac.sagemath.org/ticket/18905#comment:26 The main thing that strikes me is how reasonable the code that introduces the memory leak appears. That is why I expect this is a trap people will keep falling in again and again. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Matrix groups are not uniquely represented, why?
Suggestion: (1) Use unique representation for "ambient" objects ( GL(n,k), O(n,k,e), QQ^n). (2) Do not use unique representation for subobjects. (3) Give the .subobject(self, gens) method a (weak?) cache. (4) Modify == to test equality as subobjects/subsets. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Matrix groups are not uniquely represented, why?
On 26/05/2018 06:24, Travis Scrimshaw wrote: MatrixGroups are immutable and their comparison is by checking the generators (and not isomorphism), which are essentially the construction parameters (in reality, they are the corresponding GAP group). For permutation groups, the equality seems to be isomorphism. So there is no problem for MatrixGroups being UniqueRepresentation in terms of behavior. And IMHO this is a problem: https://trac.sagemath.org/ticket/24535 -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Matrix groups are not uniquely represented, why?
On 03/06/2018 10:54, Travis Scrimshaw wrote: (4) Modify == to test equality as subobjects/subsets. -1, as I tend to think of "==" as a QUICK test. If testing equality has a potential to hit decision problems (which certainly is the case for subgroups), then "==" should give a swift "True" if the two objects are easily seen to be equal (by equality of the set of generators, say), and should return "False" otherwise. In these cases, there ought to be a special method that the user will only call if s/he really is prepared to wait for the answer for a couple of hours. Note that in a way it would be nice if "==" had a ternary logic "True/False/Unknown". But Python isn't there yet (although I do recall that there used to be a PEP for it). I am also generally in favor of having == being a (generally) fast check. However, the symbolics code takes the opposite approach: it has the method is_trivial_equal() for quick checks but == fires up the proof engine. In terms of surprise, the fast == is clearly worse, but using is_trivially_equal() makes the code harder to read and maintain (often because of inconsistent use in regards to speed regressions). It is urgent to decide clear semantics for equality *globally* in Sage. That is 1. what Python `==` means in Sage and state it clearly in the developer's guide and documentation 2. alternative function/operator for other kind of equalities Note that Python == is used in non-trivial operation such as constructing hash tables (set, dictionaries). It would be a bad design to set == to be something else than mathematical equality (ie equality of the subgroups). Note also that it is perfectly fine for "==" to raise an error such as NotImplementedError. If some algorithm is not able to decide whether H1 and H2 are equal it can just give up. Vincent -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Matrix groups are not uniquely represented, why?
On 30/05/2018 08:14, Travis Scrimshaw wrote: On Tuesday, May 29, 2018 at 9:01:51 PM UTC+10, chris wuthrich wrote: As a simple-minded user I stumbled over exactly this last week. I don't understand much of what this thread is discussing, but I know what a simple-minded user wants. sage: G = GL(2,13) sage: G = G.as_matrix_group() sage: H = G.subgroup([ matrix(GF(13),[[1,0],[1,1]]) ]) sage: H2 = G.subgroup([ matrix(GF(13),[[1,1],[0,1]]) ]) sage: H3 = G.subgroup([ matrix(GF(13),[[1,0],[2,1]]) ]) I expect H == H3 to say True as they are the same subgroup. I expect H = H2 to say False, since they are not the same subgroup, even though they are isomorphic. Instead sage: H == H3 False sage: matrix(GF(13),[[1,0],[1,1]]) in H3 True sage: matrix(GF(13),[[1,0],[2,1]]) in H True sage: H.is_isomorphic(H3) True sage: H.is_isomorphic(H2) True sage: matrix(GF(13),[[1,0],[1,1]]) in H2 False I though of working around it by checking if they are the same as sets, but to my surprise: sage: Set( h for h in H ) == Set( h for h in H3 ) False sage: Set( h.matrix() for h in H ) == Set( h.matrix() for h in H3 ) True In short: I consider this a bug. No matter how this is done at the back, the user expects == to mean mathematical equality, here equality of subgroups. Otherwise the function should be called subgroups_with_given_generators. I think it is a bad thing in this case for == to be equality as sets. Imagine if these are two really big, equal, but differently constructed subgroups. This would be a really long and expensive check, whereas in most cases, checking the defining objects are sufficient. I believe we have other places in Sage where == is not strict mathematical equality for similar reasons. -1 on changing the == semantics here. But what if you *do* want to compare the subgroups (as Chris does). When I ask "How many apples in my basket?" to Sage I don't want an answer like "red bikes are nicer than blue ones" because it is faster to do so. The problem here is definitely *not* to discuss whether equality of subgroups is decidable or fast but what "==" should be. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Matrix groups are not uniquely represented, why?
On Sunday, June 3, 2018 at 12:26:46 PM UTC+2, vdelecroix wrote: > > Note also that it is perfectly fine for "==" to raise an error such as > NotImplementedError. If some algorithm is not able to decide whether > H1 and H2 are equal it can just give up. The problem isn't that the computer will ever run out of things to try to show that two groups are isomorphic. In fact, quite the opposite: All RAM will be consumed while trying to show equality, and eventually the oomkiller will terminate the process. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Matrix groups are not uniquely represented, why?
> > I think it is a bad thing in this case for == to be equality as sets. > > Imagine if these are two really big, equal, but differently constructed > > subgroups. This would be a really long and expensive check, whereas in > most > > cases, checking the defining objects are sufficient. I believe we have > > other places in Sage where == is not strict mathematical equality for > > similar reasons. -1 on changing the == semantics here. > > But what if you *do* want to compare the subgroups (as Chris does). When > I ask "How many apples in my basket?" to Sage I don't want an answer > like "red bikes are nicer than blue ones" because it is faster to do so. > The problem here is definitely *not* to discuss whether equality of > subgroups is decidable or fast but what "==" should be. > So we have moved from bikeshedding to bikecoloring? :P However, that is not the correct analogy. I would say a better analogy with the apple basket is "are the trees these apples came from the same." IMO, these two issues are coupled (in part due to limitations of Python not allowing an Unknown return). One option on the table is to allow == to check a potential undecidable or very slow test. Best, Travis -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Matrix groups are not uniquely represented, why?
On Thursday, May 31, 2018 at 9:24:57 AM UTC-7, Nils Bruin wrote: > > > > On Thursday, May 31, 2018 at 3:05:26 AM UTC-7, Erik Bray wrote: >> >> >> Could you actually point me to one of those memory leaks? I'm sure >> they exist but I'm still not clear on how this happens. I suspect it >> could be improved, and I would like to look into how... >> > > https://trac.sagemath.org/ticket/17008#comment:13 (prediction) > https://trac.sagemath.org/ticket/23851 > https://trac.sagemath.org/ticket/23807#comment:14 (explanation) > https://trac.sagemath.org/ticket/14549#comment:6 > https://trac.sagemath.org/ticket/18426 > https://trac.sagemath.org/ticket/14356 > https://trac.sagemath.org/ticket/17360 > https://trac.sagemath.org/ticket/18905#comment:26 > > The main thing that strikes me is how reasonable the code that introduces > the memory leak appears. That is why I expect this is a trap people will > keep falling in again and again. > And to illustrate with what frequency you can expect to discover these things in our code base: https://trac.sagemath.org/ticket/25560 -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Matrix groups are not uniquely represented, why?
On 2018-05-25 10:00, Travis Scrimshaw wrote: I believe the matrix and permutation groups are quite old code, so UniqueRepresentation may not have been available at that time. The permutation group code does need updating; in particular, it is still an old-style parent: See https://trac.sagemath.org/ticket/24612 for that. It's sort-of on my radar since I did that for intervals (#24371), matrix spaces (#23719) and I'm working on multi-variate polynomials (#25558). Unfortunately, in all 3 cases above I discovered a huge mess when looking at the code. They all involved quite a bit of work to clean that up. Jeroen. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
