[sage-combinat-devel] Canonical form for permutation groups
Hi, I wonder if there is a way to get a canonical form of a subgroup of a permutation group (or, even better, any group). This would be something like a method canonical_labeling for permutation groups that returns an isomorphic permutation group, and such that two groups are isomorphic if and only if their canonical labellings coincide. I don't think anything like that is currently implemented, right? A natural implementation would be to compute the multiplication table of the group, apply the canonical form algorithm from graphs (by simultaneous row and column permutations of the multiplication table), obtain a canoncial form of the multiplication table, and turn this data into a canonical form of a permutation group. @Nathann et al.: would this be doable without too much effort from the current algorithm for graphs? How far is the current implementation from the possibility to take any n*n array (or square matrix, but with no/less restrictions on the entries) and get it into a canonical form by simultaneous row and column permutations? Cheers, Christian -- You received this message because you are subscribed to the Google Groups sage-combinat-devel group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-combinat-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-combinat-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
[sage-combinat-devel] Re: Canonical form for permutation groups
Clearly there is no canonical form for arbitrary groups/subgroups since there is no algorithm to compare finitely generated groups. For finite groups there is, of course. In GAP one would just IdGroup() to get a unique label. A GPL-ed clone of the finite groups database in GAP would be nice, then we could distribute it by default... On Wednesday, April 10, 2013 1:59:49 PM UTC+1, Christian Stump wrote: Hi, I wonder if there is a way to get a canonical form of a subgroup of a permutation group (or, even better, any group). This would be something like a method canonical_labeling for permutation groups that returns an isomorphic permutation group, and such that two groups are isomorphic if and only if their canonical labellings coincide. I don't think anything like that is currently implemented, right? A natural implementation would be to compute the multiplication table of the group, apply the canonical form algorithm from graphs (by simultaneous row and column permutations of the multiplication table), obtain a canoncial form of the multiplication table, and turn this data into a canonical form of a permutation group. @Nathann et al.: would this be doable without too much effort from the current algorithm for graphs? How far is the current implementation from the possibility to take any n*n array (or square matrix, but with no/less restrictions on the entries) and get it into a canonical form by simultaneous row and column permutations? Cheers, Christian -- You received this message because you are subscribed to the Google Groups sage-combinat-devel group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-combinat-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-combinat-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
Re: [sage-combinat-devel] Free Algebra Element
I doubt this has ever worked: In fact, my message was not clear. I test if type(a*b) == sage.algebras.free_algebra_element.FreeAlgebraElement With older versions, type(a*b) == sage.algebras.free_algebra_element.FreeAlgebraElement which is not the case anymore. But your advice is good, thanks ! Matthieu De : Nicolas M. Thiery nicolas.thi...@u-psud.fr À : sage-combinat-devel@googlegroups.com Envoyé le : Mercredi 10 avril 2013 15h33 Objet : Re: [sage-combinat-devel] Free Algebra Element Bonjour Matthieu, On Wed, Apr 10, 2013 at 02:15:20PM +0100, Matthieu Deneufchatel wrote: Do I miss something or is there a bug : sage: R.a,b=FreeAlgebra(QQ,2) sage: a*b a*b sage: type(a*b) class 'sage.algebras.free_algebra_element.FreeAlgebra_generic_with_category.element_class' sage: type(a*b)==sage.algebras.free_algebra_element.FreeAlgebra_generic_with_category.element_class --- AttributeError Traceback (most recent call last) /home/deneufchatel/ipython console in module() AttributeError: 'module' object has no attribute 'FreeAlgebra_generic_with_category' The same code used to give something consistent with older versions of Sage (4.8 ?). I doubt this has ever worked: the class FreeAlgebra_generic_with_category is generated on the fly to add generic code from the categories to the code of FreeAlgebra and FreeAlgebraElement. For details, see: http://www.sagemath.org/doc/reference/categories/sage/categories/category.html On the other hand you can do something like: sage: type(a*b) == R.element_class Cheers, Nicolas -- Nicolas M. Thiéry Isil nthi...@users.sf.net http://Nicolas.Thiery.name/ -- You received this message because you are subscribed to the Google Groups sage-combinat-devel group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-combinat-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-combinat-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out. -- You received this message because you are subscribed to the Google Groups sage-combinat-devel group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-combinat-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-combinat-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
Re: [sage-combinat-devel] Free Algebra Element
On Wed, Apr 10, 2013 at 06:05:35PM +0100, Matthieu Deneufchatel wrote: I doubt this has ever worked: In fact, my message was not clear. I test if type(a*b) == sage.algebras.free_algebra_element.FreeAlgebraElement With older versions, type(a*b) == sage.algebras.free_algebra_element.FreeAlgebraElement which is not the case anymore. Ok, this makes sense! So what has changed in Sage is that FreeAlgebra now uses categories which was not the case before. Note that the following still holds: sage: isinstance(a*b, sage.algebras.free_algebra_element.FreeAlgebraElement) Cheers, Nicolas -- Nicolas M. Thiéry Isil nthi...@users.sf.net http://Nicolas.Thiery.name/ -- You received this message because you are subscribed to the Google Groups sage-combinat-devel group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-combinat-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-combinat-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
Re: [sage-combinat-devel] Canonical form for permutation groups
Le 10/04/2013 14:59, Christian Stump a écrit : Hi, I wonder if there is a way to get a canonical form of a subgroup of a permutation group (or, even better, any group). This would be something like a method canonical_labeling for permutation groups that returns an isomorphic permutation group, and such that two groups are isomorphic if and only if their canonical labellings coincide. If I would have to do it myself, I will use the following process : a strong generating system (s.g.s.) identify uniquely a permutation group. building a s.g.s. is a polynomial algorithm and allow after to have a lot of nice features for close to free (cardinality, contains tests, ...). Unfortunately, a s.g.s is not unique but exploiting the fact that the lexicographic order is a total order over permutations, you can define a minimal s.g.s for a group. Now, two permutation groups (define by whatever : generators, list of elements, ...) would be isomorphic if and only if they have the same minimal s.g.s. (for information, the symmetric group of degree n S_n have s.g.s. of size maximum among all subgroup of S_n and you need to keep in memory binomial(n,2) permutations of size n). I don't think this would be very hard to do it in sage as much of algorithm are already available in sage. To get a minimal s.g.s., you first compute a s.g.s. and the method strong_generating_system() is just wrapped from Gap inside Sage. After you can probably reduce it using from bottom to top by reducing permutations generating transversal fixing the n-first position using the (n+1)-th stabilizer group and the feature IntegerVectorModPermGroup already in Sage. Now, I do not much know about the complexity of all of that (I guess 10 seconds max until any subgroup of S_6 (98% of time will come from the fact that the Gap interface use pexpect)). This is not perfect and I am not a group expert. You really should ask on a Gap mailing list ; this proposition is just my small impression not really hard to test currently in Sage... Whit a clever algorithm I have in head (which doesn't use IntegerVectorModPermGroup), the reduction of an s.g.s. can be very very light in fact (just quadratic in the size of the s.g.s of the permutation group (i.e. (binomial(n,2)^2 in the worst case which is less than computing the non minimal s.g.s.))). So, if I don't say something wrong you can probably compute a minimal s.g.s. for any subgroup of S_15 in less than 10 seconds even the interface with Gap is not perfect. Anyway, if you want to try my option (and nobody give an objection about what I propose), you should begin to read : http://en.wikipedia.org/wiki/Schreier%E2%80%93Sims_algorithm Guys from Gap could also say my proposition is horrible for any reason I did not see yet... For general group, I think the memory needed would just be too much... Or you just keep small cardinality groups. Best regards, Nicolas B. -- You received this message because you are subscribed to the Google Groups sage-combinat-devel group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-combinat-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-combinat-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
Re: [sage-combinat-devel] Canonical form for permutation groups
Unfortunately, I think you will have to require specific conditions in order to make a canonical form possible, even when considering a minimal SGS as Nicolas suggests. The conditions are likely along the lines of requiring a reduction to a primitive, or at least transitive, group. You may also have to require that the group action be represented a specific way. For instance, with the example of S_6, one could consider the degree 6 natural action and obtain a strong generating set from a minimal base of length 5 ... or one could consider the (right) regular representation of S_6 acting on itself in degree 720 and obtain a minimal base of length 1 ... which will give a substantially different base and strong generating set. In either case, it's the same group ... but the action is defined entirely differently. Determining the underlying group can be very challenging. The first place may be in constructing a composition series for the given representation, which for permutation groups usually involves isomorphisms to a primitive group of specific degree... it is the primitive representations that are more easily classified up to a given degree. That is, more than likely, the only place where such a canonical representation has any hope in my mind. Jason On Wed, Apr 10, 2013 at 5:09 PM, Borie Nicolas pout...@gmail.com wrote: Le 10/04/2013 14:59, Christian Stump a écrit : Hi, I wonder if there is a way to get a canonical form of a subgroup of a permutation group (or, even better, any group). This would be something like a method canonical_labeling for permutation groups that returns an isomorphic permutation group, and such that two groups are isomorphic if and only if their canonical labellings coincide. If I would have to do it myself, I will use the following process : a strong generating system (s.g.s.) identify uniquely a permutation group. building a s.g.s. is a polynomial algorithm and allow after to have a lot of nice features for close to free (cardinality, contains tests, ...). Unfortunately, a s.g.s is not unique but exploiting the fact that the lexicographic order is a total order over permutations, you can define a minimal s.g.s for a group. Now, two permutation groups (define by whatever : generators, list of elements, ...) would be isomorphic if and only if they have the same minimal s.g.s. (for information, the symmetric group of degree n S_n have s.g.s. of size maximum among all subgroup of S_n and you need to keep in memory binomial(n,2) permutations of size n). I don't think this would be very hard to do it in sage as much of algorithm are already available in sage. To get a minimal s.g.s., you first compute a s.g.s. and the method strong_generating_system() is just wrapped from Gap inside Sage. After you can probably reduce it using from bottom to top by reducing permutations generating transversal fixing the n-first position using the (n+1)-th stabilizer group and the feature IntegerVectorModPermGroup already in Sage. Now, I do not much know about the complexity of all of that (I guess 10 seconds max until any subgroup of S_6 (98% of time will come from the fact that the Gap interface use pexpect)). This is not perfect and I am not a group expert. You really should ask on a Gap mailing list ; this proposition is just my small impression not really hard to test currently in Sage... Whit a clever algorithm I have in head (which doesn't use IntegerVectorModPermGroup), the reduction of an s.g.s. can be very very light in fact (just quadratic in the size of the s.g.s of the permutation group (i.e. (binomial(n,2)^2 in the worst case which is less than computing the non minimal s.g.s.))). So, if I don't say something wrong you can probably compute a minimal s.g.s. for any subgroup of S_15 in less than 10 seconds even the interface with Gap is not perfect. Anyway, if you want to try my option (and nobody give an objection about what I propose), you should begin to read : http://en.wikipedia.org/wiki/* *Schreier%E2%80%93Sims_**algorithmhttp://en.wikipedia.org/wiki/Schreier%E2%80%93Sims_algorithm Guys from Gap could also say my proposition is horrible for any reason I did not see yet... For general group, I think the memory needed would just be too much... Or you just keep small cardinality groups. Best regards, Nicolas B. -- You received this message because you are subscribed to the Google Groups sage-combinat-devel group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-combinat-devel+**unsubscr...@googlegroups.comsage-combinat-devel%2bunsubscr...@googlegroups.com . To post to this group, send email to sage-combinat-devel@** googlegroups.com sage-combinat-devel@googlegroups.com. Visit this group at http://groups.google.com/** group/sage-combinat-devel?hl=**enhttp://groups.google.com/group/sage-combinat-devel?hl=en . For more options, visit
Re: [sage-combinat-devel] Canonical form for permutation groups
On Thu, Apr 11, 2013 at 01:09:59AM +0200, Borie Nicolas wrote:
I wonder if there is a way to get a canonical form of a subgroup of a
permutation group (or, even better, any group). This would be
something like a method canonical_labeling for permutation groups
that returns an isomorphic permutation group, and such that two groups
are isomorphic if and only if their canonical labellings coincide.
If I would have to do it myself, I will use the following process :
a strong generating system (s.g.s.) identify uniquely a permutation
group. building a s.g.s. is a polynomial algorithm and allow after
to have a lot of nice features for close to free (cardinality,
contains tests, ...). Unfortunately, a s.g.s is not unique but
exploiting the fact that the lexicographic order is a total order
over permutations, you can define a minimal s.g.s for a group. Now,
two permutation groups (define by whatever : generators, list of
elements, ...) would be isomorphic if and only if they have the same
minimal s.g.s. (for information, the symmetric group of degree n S_n
have s.g.s. of size maximum among all subgroup of S_n and you need
to keep in memory binomial(n,2) permutations of size n).
If I understood Christian's question right, he does not only want to
test if the two groups are equals as sets of permutations, but if they
are isomorphic as groups. So for him the following groups generated by
permutations would all be the same:
- (1,2)
- (2,3)
- (1,2)(3,4)
- the multiplicative group ({-1,1}, *).
Cheers,
Nicolas
--
Nicolas M. Thiéry Isil nthi...@users.sf.net
http://Nicolas.Thiery.name/
--
You received this message because you are subscribed to the Google Groups
sage-combinat-devel group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-combinat-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-combinat-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
[sage-combinat-devel] The reading tableau of a partition
Good Morning! I have been distracted from sage for quite some time but this morning I started playing again and I came across the *reading_tableau *method of a partition. The documentation for this method reads: Return the reading tableau of the reading word under the Robinson-Schensted correspondence of the (standard) tableau `T` labeled down (in English convention) each column to the shape of ``self``. For an example of the tableau `T`, consider the partition `\lambda = (3,2,1)`, then we have:: 1 4 6 2 5 3 For more, see :func:`~sage.combinat.rsk.RSK()`. EXAMPLES:: sage: Partition([3,2,1]).reading_tableau() [[1, 3, 6], [2, 5], [4]] The example in the text and the example that is doc-test appear to disagree. My guess is that the example in the text is what is expected. Is this right? [In 5.8 the behaviour is as in the doc-test.] I suspect that this may have changed when partitions were made to play nicely with categories as I think that the order in which the partitions are generated may have changed then. All this aside, if some one can confirm that this is a bug then I will file a ticket, and probably even a patch. Andrew -- You received this message because you are subscribed to the Google Groups sage-combinat-devel group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-combinat-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-combinat-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
Re: [sage-combinat-devel] Canonical form for permutation groups
In GAP one would just IdGroup() to get a unique label.
Is this given for any finite group in GAP, or is this depending on
http://www.gap-system.org/Packages/sgl.html ? It looks like there is
not much to do beyond these IdGroup in Sage since I guess they would
have gone beyond n=22 in Gap otherwise). On sage-devel, John Cremona
was basically suggesting the same as a unique labelling for small
groups.
- (1,2)
- (2,3)
- (1,2)(3,4)
- the multiplicative group ({-1,1}, *).
That is right, these should all result in the same group... and yes, I
forgot to add the action on the entries of the multiplication table.
So some canonical generating system on a particular subgroup of a
finite permutation group would not be enough.
Cheers, Christian
--
You received this message because you are subscribed to the Google Groups
sage-combinat-devel group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-combinat-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-combinat-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
[sage-combinat-devel] Re: Canonical form for permutation groups
On Wednesday, 10 April 2013 20:59:49 UTC+8, Christian Stump wrote: Hi, I wonder if there is a way to get a canonical form of a subgroup of a permutation group (or, even better, any group). This would be something like a method canonical_labeling for permutation groups that returns an isomorphic permutation group, and such that two groups are isomorphic if and only if their canonical labellings coincide. I don't think anything like that is currently implemented, right? A natural implementation would be to compute the multiplication table of the group, apply the canonical form algorithm from graphs (by simultaneous row and column permutations of the multiplication table), obtain a canoncial form of the multiplication table, and turn this data into a canonical form of a permutation group. no, no, that's not what you want to do, certainly. A much more efficient way is to compute a strong generating set w.r.t. a canonical minimal base. (A base of a permutation group is a tuple of points (s_1,...,s_t) s.t. each group element g is uniquely defined by (g(s_1),...,g(s_t))). @Nathann et al.: would this be doable without too much effort from the current algorithm for graphs? How far is the current implementation from the possibility to take any n*n array (or square matrix, but with no/less restrictions on the entries) and get it into a canonical form by simultaneous row and column permutations? Cheers, Christian -- You received this message because you are subscribed to the Google Groups sage-combinat-devel group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-combinat-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-combinat-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
Re: [sage-devel] Re: matrix multiplication weird coercion
I've dealt with similar nice things at #8335 indeed. IIRC, at some point I had to enable coercion into ZZ(1) to make thing work, but then I thought this was really pointless and got similar doctests failure concerning matrix multiplication, so I forbid somewhere in the corecion model to quotient a ring by (1). I also changed the priorities of QuotientFunctor and something else to please the coercion model. Don't really remember the details though. There was already a similar blocker for quotienting by (1) in the source coude, but then IIRC a ticket about is_Field decided to let it happen at some other place and it took precedence over the previous blocker. I would have thought #8335 would fix prevent this behavior... On Wednesday, April 10, 2013 12:41:40 AM UTC+2, Ben Hutz wrote: Nope. With the three patches in #8335, I'm still getting the same behavior on sage 5.8. Could you double check me on that? If there isn't anywhere else that this is fixed in, I can open a separate bug. On Tuesday, April 9, 2013 5:54:55 PM UTC-4, David Roe wrote: I think this issue is addressed at #8335, which I haven't had time to review David On Tue, Apr 9, 2013 at 3:52 PM, Travis Scrimshaw tsc...@ucdavis.eduwrote: Hey, I'm pretty sure that's a bug since there is no coercion map between QQ and GF(7) ( which is different than calling GF(7)(1/5) ). Here's some of the other tests I tried: sage: T=matrix(GF(7),[[1,1],[0,3]]) sage: (N*T).parent() Full MatrixSpace of 2 by 2 dense matrices over Ring of integers modulo 1 sage: T=matrix(GF(2),[[1,1],[0,1]]) sage: (N*T).parent() Full MatrixSpace of 2 by 2 dense matrices over Ring of integers modulo 1 sage: T=matrix(GF(25,'a'),[[1,1],[0,3]]) sage: (N*T).parent() Full MatrixSpace of 2 by 2 dense matrices over Finite Field in a of size 5^2 sage: N*T [1 4] [0 3] So this is something tied to only field of size p. 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+...@googlegroups.com. To post to this group, send email to sage-...@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out. -- 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 http://groups.google.com/group/sage-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
[sage-devel] Re: matrix multiplication weird coercion
The problem may be this: sage: S=Rationals() sage: R=GF(7) sage: from sage.categories.pushout import * sage: pushout(R,S) Ring of integers modulo 1 sage: R_tower = construction_tower(R) sage: S_tower = construction_tower(S) sage: R_tower [(None, Finite Field of size 7), (QuotientFunctor, Integer Ring)] sage: S_tower [(None, Rational Field), (FractionField, Integer Ring)] sage: R_tower[1][0].rank 7 sage: S_tower[1][0].rank 5 These ranks mean that FractionField is applied before the QuotientFunctor, which is obviously not such a great idea: After taking the fraction field there are not many ideals left to quotient out by: sage: R_tower[1][0](S_tower[1][0](ZZ)) Ring of integers modulo 1 The other composition would arrive at a desirable pushout: sage: S_tower[1][0](R_tower[1][0](ZZ)) Finite Field of size 7 Larger finite fields don't participate in this game: sage: construction_tower(GF(7^2,'a')) [(None, Finite Field in a of size 7^2)] so there the code relies on the coercion that exists from ZZ to GF, which somehow extends (partially) to QQ. I would think this example illustrates that FractionField should have a higher rank than QuotientFunctor. Doing that ends up with sage: L.parent() Full MatrixSpace of 2 by 2 dense matrices over Ring of integers modulo 7 sage: T.parent() Full MatrixSpace of 2 by 2 dense matrices over Finite Field of size 7 so it didn't quite produce the right parent, although sage: pushout(QQ,GF(7)) Finite Field of size 7 -- 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 http://groups.google.com/group/sage-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
[sage-devel] Re: matrix multiplication weird coercion
On Wednesday, April 10, 2013 10:28:51 AM UTC+2, Nils Bruin wrote: The problem may be this: sage: S=Rationals() sage: R=GF(7) sage: from sage.categories.pushout import * sage: pushout(R,S) Ring of integers modulo 1 sage: R_tower = construction_tower(R) sage: S_tower = construction_tower(S) sage: R_tower [(None, Finite Field of size 7), (QuotientFunctor, Integer Ring)] sage: S_tower [(None, Rational Field), (FractionField, Integer Ring)] sage: R_tower[1][0].rank 7 sage: S_tower[1][0].rank 5 These ranks mean that FractionField is applied before the QuotientFunctor, which is obviously not such a great idea: After This should be changed in #8335, see the top of the third patch to apply. taking the fraction field there are not many ideals left to quotient out by: sage: R_tower[1][0](S_tower[1][0](ZZ)) Ring of integers modulo 1 The other composition would arrive at a desirable pushout: sage: S_tower[1][0](R_tower[1][0](ZZ)) Finite Field of size 7 Larger finite fields don't participate in this game: sage: construction_tower(GF(7^2,'a')) [(None, Finite Field in a of size 7^2)] so there the code relies on the coercion that exists from ZZ to GF, which somehow extends (partially) to QQ. I would think this example illustrates that FractionField should have a higher rank than QuotientFunctor. Doing that ends up with sage: L.parent() Full MatrixSpace of 2 by 2 dense matrices over Ring of integers modulo 7 sage: T.parent() Full MatrixSpace of 2 by 2 dense matrices over Finite Field of size 7 so it didn't quite produce the right parent, although sage: pushout(QQ,GF(7)) Finite Field of size 7 -- 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 http://groups.google.com/group/sage-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
[sage-devel] Re: matrix multiplication weird coercion
I've just built 5.8 + #8335 and this is indeed fixed, are you sure you rebuilt the Sage library after applying the patches? -- 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 http://groups.google.com/group/sage-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
[sage-devel] Canonical form for permutation groups
Hi, I wonder if there is a way to get a canonical form of a subgroup of a permutation group (or, even better, any group). This would be something like a method canonical_labeling for permutation groups that returns an isomorphic permutation group, and such that two groups are isomorphic if and only if their canonical labellings coincide. I don't think anything like that is currently implemented, right? A natural implementation would be to compute the multiplication table of the group, apply the canonical form algorithm from graphs (by simultaneous row and column permutations of the multiplication table), obtain a canoncial form of the multiplication table, and turn this data into a canonical form of a permutation group. @Nathann et al.: would this be doable without too much effort from the current algorithm for graphs? How far is the current implementation from the possibility to take any n*n array (or square matrix, but with no/less restrictions on the entries) and get it into a canonical form by simultaneous row and column permutations? Cheers, Christian -- 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 http://groups.google.com/group/sage-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
[sage-devel] Re: Canonical form for permutation groups
Clearly there is no canonical form for arbitrary groups/subgroups since there is no algorithm to compare finitely generated groups. For finite groups there is, of course. In GAP one would just IdGroup() to get a unique label. A GPL-ed clone of the finite groups database in GAP would be nice, then we could distribute it by default... On Wednesday, April 10, 2013 1:59:49 PM UTC+1, Christian Stump wrote: Hi, I wonder if there is a way to get a canonical form of a subgroup of a permutation group (or, even better, any group). This would be something like a method canonical_labeling for permutation groups that returns an isomorphic permutation group, and such that two groups are isomorphic if and only if their canonical labellings coincide. I don't think anything like that is currently implemented, right? A natural implementation would be to compute the multiplication table of the group, apply the canonical form algorithm from graphs (by simultaneous row and column permutations of the multiplication table), obtain a canoncial form of the multiplication table, and turn this data into a canonical form of a permutation group. @Nathann et al.: would this be doable without too much effort from the current algorithm for graphs? How far is the current implementation from the possibility to take any n*n array (or square matrix, but with no/less restrictions on the entries) and get it into a canonical form by simultaneous row and column permutations? Cheers, Christian -- 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 http://groups.google.com/group/sage-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
[sage-devel] Re: [sage-combinat-devel] Canonical form for permutation groups
Hi Christian, On Wed, Apr 10, 2013 at 07:59:49AM -0500, Christian Stump wrote: I wonder if there is a way to get a canonical form of a subgroup of a permutation group (or, even better, any group). This would be something like a method canonical_labeling for permutation groups that returns an isomorphic permutation group, and such that two groups are isomorphic if and only if their canonical labellings coincide. I don't think anything like that is currently implemented, right? Not that I know of. I would suggest to ask on the GAP mailing list if something like this is implemented in GAP. A natural implementation would be to compute the multiplication table of the group, apply the canonical form algorithm from graphs (by simultaneous row and column permutations of the multiplication table), obtain a canoncial form of the multiplication table, and turn this data into a canonical form of a permutation group. You need to act not only on rows and columns but also on the values in the table, don't you? That being said, it should indeed be possible to handle this problem by encoding the product as a ternary relation (a,b,ab), and encoding the ternary relation itself using a graph. Something like: Vertices: elements a of G, and pairs (a,b) of elements of G Edges: a - (a,b) with edge label left b - (a,b) with edge label right (a,b) - ab with edge label result Loops: (a,b) - (a,b) The loops are just here to distinguish the two kinds of vertices; one could instead specify a vertex bipartition to the canonical labeling function. Note that the above would work for any semigroup or even magma. But one could hope for something vastly more efficient for groups. Cheers, Nicolas -- Nicolas M. Thiéry Isil nthi...@users.sf.net http://Nicolas.Thiery.name/ -- 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 http://groups.google.com/group/sage-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
Re: [sage-devel] Re: [sage-combinat-devel] Canonical form for permutation groups
It may be relevant to look at the canonical labelling used for Galois grousp (see for example http://www.lmfdb.org/GaloisGroup/ and click on the word label). John On 10 April 2013 14:19, Nicolas M. Thiery nicolas.thi...@u-psud.fr wrote: Hi Christian, On Wed, Apr 10, 2013 at 07:59:49AM -0500, Christian Stump wrote: I wonder if there is a way to get a canonical form of a subgroup of a permutation group (or, even better, any group). This would be something like a method canonical_labeling for permutation groups that returns an isomorphic permutation group, and such that two groups are isomorphic if and only if their canonical labellings coincide. I don't think anything like that is currently implemented, right? Not that I know of. I would suggest to ask on the GAP mailing list if something like this is implemented in GAP. A natural implementation would be to compute the multiplication table of the group, apply the canonical form algorithm from graphs (by simultaneous row and column permutations of the multiplication table), obtain a canoncial form of the multiplication table, and turn this data into a canonical form of a permutation group. You need to act not only on rows and columns but also on the values in the table, don't you? That being said, it should indeed be possible to handle this problem by encoding the product as a ternary relation (a,b,ab), and encoding the ternary relation itself using a graph. Something like: Vertices: elements a of G, and pairs (a,b) of elements of G Edges: a - (a,b) with edge label left b - (a,b) with edge label right (a,b) - ab with edge label result Loops: (a,b) - (a,b) The loops are just here to distinguish the two kinds of vertices; one could instead specify a vertex bipartition to the canonical labeling function. Note that the above would work for any semigroup or even magma. But one could hope for something vastly more efficient for groups. Cheers, Nicolas -- Nicolas M. Thiéry Isil nthi...@users.sf.net http://Nicolas.Thiery.name/ -- 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 http://groups.google.com/group/sage-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out. -- 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 http://groups.google.com/group/sage-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
[sage-devel] Re: matrix multiplication weird coercion
On Apr 10, 2:19 am, Jean-Pierre Flori jpfl...@gmail.com wrote: I've just built 5.8 + #8335 and this is indeed fixed, are you sure you rebuilt the Sage library after applying the patches? Yes, I see. That patch changes the unique rank = 7 to rank = 4.5 in the relevant file, so that should do the trick. Did you observe getting the right parent (i.e., finite field of size 7 rather than ZZ modulo 7)? I can see how we end up with that: a generic QuotientFunctor doesn't necessarily produce a field, and QuotientByMaximalIdeal is not functorial. However, I observed pushout(QQ,GF(7)) giving GF(7) but on the level of matrices I was still getting just ZZ modulo 7. The code suggests I should end up with the same thing. -- 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 http://groups.google.com/group/sage-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
[sage-devel] Re: matrix multiplication weird coercion
On Wednesday, April 10, 2013 5:49:20 PM UTC+2, Nils Bruin wrote: On Apr 10, 2:19 am, Jean-Pierre Flori jpfl...@gmail.com wrote: I've just built 5.8 + #8335 and this is indeed fixed, are you sure you rebuilt the Sage library after applying the patches? Yes, I see. That patch changes the unique rank = 7 to rank = 4.5 in the relevant file, so that should do the trick. Did you observe getting the right parent (i.e., finite field of size 7 rather than ZZ modulo 7)? I can see how we end up with that: a generic QuotientFunctor doesn't necessarily produce a field, and QuotientByMaximalIdeal is not functorial. However, I observed pushout(QQ,GF(7)) giving GF(7) but on the level of matrices I was still getting just ZZ modulo 7. The code suggests I should end up with the same thing. I don't really remember, but it's possible we still live i nthe quotient ring rather then the field. -- 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 http://groups.google.com/group/sage-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
[sage-devel] Re: matrix multiplication weird coercion
hmm. I just tried this again on my desktop (OSX 10.8) with sage 5.8. Here the patches fail to apply on a clean clone. for the psuedo-conway patch I get: failed to synchronize metadata for sage/rings/finite_rings/constructor.py If I forge on regardless with the other two, then I get the same metadata problem for: sage/categories/pushout.py Of course, with the patches failing to apply, then it isn't fix. I'll have to check and see if the same thing happened on my Ubuntu machine where I tried it above. On Wednesday, April 10, 2013 5:19:52 AM UTC-4, Jean-Pierre Flori wrote: I've just built 5.8 + #8335 and this is indeed fixed, are you sure you rebuilt the Sage library after applying the patches? -- 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 http://groups.google.com/group/sage-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
[sage-devel] Re: GSoC project: make the Sage build system more distribution friendly
Sorry, there were a few mails that missed the list: On 09.04.2013 09:49, Felix Salfelder wrote: Hi thanks for establishing this! i can imagine applying for that project. at least i'll have some time left in summer, as i'm on parental leave and i found a nursery... i'd like to discuss the scope and potential solutions for that problem a bit. a proper build system for sage (the library) with the usual dependency checks seems neccesary (if not sufficient) for distributions. i can think of a way to implement this (probably using autotools) and put it into a debian package. such a build system won't yet get me much closer to the project deliverable support for choosing a set of dependencies within sage without messing a lot with sage (the operating system). a build system for sage (the library) could be used to switch between system headers/libraries and stuff installed to /some/sage/prefix. in order to make use of these switches from sage (the operating system), the toplevel install script must be able process switches like --with-ntl=/usr/include to pass to the spkg compilation, which in turn means *all* spkgs must understand such flags (doesn't it?). it seems to be more work to fix sage (the operating sytstem) than to properly ship sage (the library) within an already working distribution (= properly checking for functionality/applied patches). these checks however are difficult to maintain, if upstream sage doesn't use them... to me, these problems (fixing sage vs. distributing sage library) seem independent enough to have two GSoC projects. i have a rough idea of what gentoo-prefix is doing and of Julien's pruner script, but i don't see a solution there. what is your favourite way out? regards felix -- 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 http://groups.google.com/group/sage-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
[sage-devel] Re: GSoC project: make the Sage build system more distribution friendly
On 09.04.2013 10:26, Tobias Hansen wrote: Hi Felix, On 04/09/2013 09:49 AM, Felix Salfelder wrote: a proper build system for sage (the library) with the usual dependency checks seems neccesary (if not sufficient) for distributions. i can think of a way to implement this (probably using autotools) and put it into a debian package. such a build system won't yet get me much closer to the project deliverable support for choosing a set of dependencies within sage without messing a lot with sage (the operating system). a build system for sage (the library) could be used to switch between system headers/libraries and stuff installed to /some/sage/prefix. in order to make use of these switches from sage (the operating system), the toplevel install script must be able process switches like --with-ntl=/usr/include to pass to the spkg compilation, which in turn means *all* spkgs must understand such flags (doesn't it?). No, the toplevel install script must just be able to skip the compilation of these spkg's. And tell the Sage library to use the libraries that are available and were compiled independently. it seems to be more work to fix sage (the operating sytstem) than to properly ship sage (the library) within an already working distribution (= properly checking for functionality/applied patches). these checks however are difficult to maintain, if upstream sage doesn't use them... We want to do the changes to the build system in Sage, the two Sage developers agreed to keep an eye on the progress so that we end up with something they can accept in the end. As much tests as possible would be great, but how would you check for applied patches in an universal way? Every distribution has its own way to organize patches. I think Sage already has a good test coverage and a Debian package should of course run all the tests during build. to me, these problems (fixing sage vs. distributing sage library) seem independent enough to have two GSoC projects. i have a rough idea of what gentoo-prefix is doing and of Julien's pruner script, but i don't see a solution there. what is your favourite way out? regards felix It seems to me that you understood that Sage should build all spkg's in any case and just install them somewhere else. I think that means the step you call fix Sage the operating system is not needed right? Now that I have clarified this, any new thoughts? Cheers, Tobias -- 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 http://groups.google.com/group/sage-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
[sage-devel] Re: GSoC project: make the Sage build system more distribution friendly
On 09.04.2013 14:18, Tobias Hansen wrote: On 04/09/2013 10:26 AM, Tobias Hansen wrote: a build system for sage (the library) could be used to switch between system headers/libraries and stuff installed to /some/sage/prefix. in order to make use of these switches from sage (the operating system), the toplevel install script must be able process switches like --with-ntl=/usr/include to pass to the spkg compilation, which in turn means *all* spkgs must understand such flags (doesn't it?). No, the toplevel install script must just be able to skip the compilation of these spkg's. And tell the Sage library to use the libraries that are available and were compiled independently. I get it, you are talking about dependencies between spkg's. Yes that would require a central mechanism in Sage that provides all spkgs with the information where the other stuff is, if we really want the possibility to mix spkgs and system libraries. -- 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 http://groups.google.com/group/sage-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
[sage-devel] Re: GSoC project: make the Sage build system more distribution friendly
On 10.04.2013 17:43, Felix Salfelder wrote: Hi Tobias On Tue, Apr 09, 2013 at 10:26:30AM +0200, Tobias Hansen wrote: No, the toplevel install script must just be able to skip the compilation of these spkg's. And tell the Sage library to use the libraries that are available and were compiled independently. skipping compilation of spkgs (and the installation to /some/sage/prefix) and appending CPP/LD-FLAGS to environment variables during spkg builds seems feasible. this would require a configure script (or configure functionality)... picking the right flags for each spkg and/or fixing every single spkg to use them (correctly) is probably more work. it seems to be more work to fix sage (the operating sytstem) than to properly ship sage (the library) within an already working distribution (= properly checking for functionality/applied patches). these checks however are difficult to maintain, if upstream sage doesn't use them... i should write sage the system, what i'm referring to is the tarball that contains the spkg's and the toplevel 'installer' makefile. We want to do the changes to the build system in Sage, the two Sage developers agreed to keep an eye on the progress so that we end up with something they can accept in the end. several parts of fixing/changing/improving the sage (the system) build system is unrelated to distributing sage the library. so changes to the build system in Sage is somewhat vague. As much tests as possible would be great, but how would you check for applied patches in an universal way? i think a build system for the sage library should at least check availibility (especially optional dependencies). more checks for versions/header functionality/existing symbols are implemented within autotools. the universal way would be maintaining these checks (which is unrealistic). catching common caveats should be possible. Every distribution has its own way to organize patches. I think Sage already has a good test coverage and a Debian package should of course run all the tests during build. iirc the tests are contained within sage.spkg (where the library is), so that should be possible. other tests may come within other spkgs. It seems to me that you understood that Sage should build all spkg's in any case and just install them somewhere else. I think that means the step you call fix Sage the operating system is not needed right? Now that I have clarified this, any new thoughts? for debian or other distributions, i dont see the need for any changes to sage (the system). making sagelib distributable doesn't help skipping spkgs. so there are still two subprojects: - improve sage (the library) distributability - enhance setup.py (better switch to autotools) - get libcsage.deb and python-sage.deb packages - run the unit tests from debian/rules - (also pack other stuff) - pave the way for local spkgs (e.g. installed to ~/.sage/local) - [..] - fix sage the system - implement/incorporate top level configure script - figure out flags, pass down to spkg-compilation - build sage the upstream way skipping some spkgs - [..] in fact, the second is not needed, neither for me, nor for the debian package. the project description implies something different, which is confusing. depending on difficulties, i might be able do deal with both. but of course i want to clarify the details before i apply :) thanks felix On 10.04.2013 17:52, Felix Salfelder wrote: On Tue, Apr 09, 2013 at 02:18:06PM +0200, Tobias Hansen wrote: I get it, you are talking about dependencies between spkg's. Yes that would require a central mechanism in Sage that provides all spkgs with the information where the other stuff is, if we really want the possibility to mix spkgs and system libraries. yes. something like that. but it seems to be a lot of uneccesary/duplicate work. it's probably more adequate to just skip spkgs and cross fingers -- for that matter. regards felix -- 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 http://groups.google.com/group/sage-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
[sage-devel] Re: matrix multiplication weird coercion
The patches apply just fine on my Ubuntu system, but I'm still getting the same results N=matrix(QQ,[[1,1],[0,1]]) T=matrix(GF(7),[[1,1],[0,1]]) L=N*T L,L.parent() ([0 0] [0 0], Full MatrixSpace of 2 by 2 dense matrices over Ring of integers modulo 1) Just to be clear I applied the three apply patches: trac_8335-pseudo_conway-5.8.b0.patch trac_8335-finite_field_coerce-5.8.b0.patch trac_8335-fixes-5.8.b0.patch -- 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 http://groups.google.com/group/sage-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
[sage-devel] Re: matrix multiplication weird coercion
Never mind. Apparently, my .patch files didn't download correctly. After grabbing new versions, this *is* fixed in #8335 for me. -- 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 http://groups.google.com/group/sage-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
[sage-devel] Re: GSoC project: make the Sage build system more distribution friendly
Am 10.04.2013 17:43, schrieb Felix Salfelder: several parts of fixing/changing/improving the sage (the system) build system is unrelated to distributing sage the library. so changes to the build system in Sage is somewhat vague. i think a build system for the sage library should at least check availibility (especially optional dependencies). more checks for versions/header functionality/existing symbols are implemented within autotools. the universal way would be maintaining these checks (which is unrealistic). catching common caveats should be possible. I mostly thought about the build system of the Sage system until now and didn't think about the build process of the library. Since availability of dependencies is ensured by the Sage system, the build process of the Sage library doesn't check for dependencies, right? Your idea is to add dependency checks to the library build, and that may be a good idea, but one could also consider to let the top level build scripts keep the job of handling the dependencies and do the checks there. I'm not saying that this would be better, just that this was my idea until now. Every distribution has its own way to organize patches. I think Sage already has a good test coverage and a Debian package should of course run all the tests during build. iirc the tests are contained within sage.spkg (where the library is), so that should be possible. other tests may come within other spkgs. Remember the git transition. spkg's will go away. There will be just one tarball containing everything in the future. The sources of other projects will be better separated, so it will be easy to get a Sage tarball without sources of other projects. Taking this into account, it probably makes sense to have only one Sage Debian source package. It seems to me that you understood that Sage should build all spkg's in any case and just install them somewhere else. I think that means the step you call fix Sage the operating system is not needed right? Now that I have clarified this, any new thoughts? for debian or other distributions, i dont see the need for any changes to sage (the system). making sagelib distributable doesn't help skipping spkgs. so there are still two subprojects: - improve sage (the library) distributability - enhance setup.py (better switch to autotools) - get libcsage.deb and python-sage.deb packages - run the unit tests from debian/rules - (also pack other stuff) - pave the way for local spkgs (e.g. installed to ~/.sage/local) - [..] Switching to autotools is something we can't decide alone. What do Sage developers say? Do you mean with Sage (the library) all Sage components including notebook etc? - fix sage the system - implement/incorporate top level configure script - figure out flags, pass down to spkg-compilation - build sage the upstream way skipping some spkgs - [..] in fact, the second is not needed, neither for me, nor for the debian package. the project description implies something different, which is confusing. It would still be nice if the top level script could be used by distributions. There are still several things to build and other things to do, if external dependencies are not built, and we should not implement all this in debian/rules. One could start with the option to build all or none of the dependencies and then maybe go further to allow more combinations. But I'm also not entirely sure if combining system and bundled dependencies is needed. Maybe an alternative build script for building with system libraries would be a better idea. Are there other opinions? Cheers, Tobias -- 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 http://groups.google.com/group/sage-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
Re: [sage-devel] Re: GSoC project: make the Sage build system more distribution friendly
Hi, I'll give some answers from my point of view as one of the lead of sage-on- gentoo https://github.com/cschwan/sage-on-gentoo. Some of the problems discussed we encountered and have an opinion on. Whether some of the things we do or have done are applicable to Debian is best answered by Debian people themselves. On Thu, 11 Apr 2013 01:04:23 Tobias Hansen wrote: Am 10.04.2013 17:43, schrieb Felix Salfelder: several parts of fixing/changing/improving the sage (the system) build system is unrelated to distributing sage the library. so changes to the build system in Sage is somewhat vague. i think a build system for the sage library should at least check availibility (especially optional dependencies). more checks for versions/header functionality/existing symbols are implemented within autotools. the universal way would be maintaining these checks (which is unrealistic). catching common caveats should be possible. I mostly thought about the build system of the Sage system until now and didn't think about the build process of the library. Since availability of dependencies is ensured by the Sage system, the build process of the Sage library doesn't check for dependencies, right? Your idea is to add dependency checks to the library build, and that may be a good idea, but one could also consider to let the top level build scripts keep the job of handling the dependencies and do the checks there. I'm not saying that this would be better, just that this was my idea until now. Indeed sage is built from a top makefile and dependencies between the various spkg and sage itself are defined in spkg/standard/deps. This is used for building standard sage. For distribution purpose it is useful to separate these in two class, build time dependencies and pure run-time dependencies. For example scipy is not required at build time but will be required at run time. Sage also has some optional dependencies, some which are built time are usually checked in module_list.py (at the end). The sage package management system is invoked to check whether the package is installed. Run time optional dependencies are either checked through the sage package management system or presence of key files. From the point of view of a linux distribution, my opinion is that the package management system should be extracted. If it comes from your distro the packages and upgrades are handled by the distro mechanism, except for stuff that (can) live in the final user home directory. Every distribution has its own way to organize patches. I think Sage already has a good test coverage and a Debian package should of course run all the tests during build. iirc the tests are contained within sage.spkg (where the library is), so that should be possible. other tests may come within other spkgs. Remember the git transition. spkg's will go away. There will be just one tarball containing everything in the future. The sources of other projects will be better separated, so it will be easy to get a Sage tarball without sources of other projects. Taking this into account, it probably makes sense to have only one Sage Debian source package. Yes and no, see below. It seems to me that you understood that Sage should build all spkg's in any case and just install them somewhere else. I think that means the step you call fix Sage the operating system is not needed right? Now that I have clarified this, any new thoughts? for debian or other distributions, i dont see the need for any changes to sage (the system). making sagelib distributable doesn't help skipping spkgs. so there are still two subprojects: - improve sage (the library) distributability - enhance setup.py (better switch to autotools) - get libcsage.deb and python-sage.deb packages - run the unit tests from debian/rules - (also pack other stuff) - pave the way for local spkgs (e.g. installed to ~/.sage/local) - [..] Switching to autotools is something we can't decide alone. What do Sage developers say? Do you mean with Sage (the library) all Sage components including notebook etc? Sage itself has currently several components that are shipped separately and at least one that should be split: sage_root: which has all the elements of the basic build system and traditionally the scripts to start sage. sage_scripts: a collection of various scripts and command to run and tests sage. extcode: various bits and pieces accumulated over time. I understand it will disappear in the git migration being integrated elsewhere. sage: the python extension itself plus the c library. The c library is the element we think should be split (and we do in sage-on-gentoo). Whether to keep this structure in Debian or after the git transition is not for me to answer. But I strongly believe the c library needs to be available separately from the python library. The c library is built with scons which
Re: [sage-devel] Re: GSoC project: make the Sage build system more distribution friendly
On Wed, Apr 10, 2013 at 4:04 PM, Tobias Hansen than...@debian.org wrote: Am 10.04.2013 17:43, schrieb Felix Salfelder: several parts of fixing/changing/improving the sage (the system) build system is unrelated to distributing sage the library. so changes to the build system in Sage is somewhat vague. i think a build system for the sage library should at least check availibility (especially optional dependencies). more checks for versions/header functionality/existing symbols are implemented within autotools. the universal way would be maintaining these checks (which is unrealistic). catching common caveats should be possible. I mostly thought about the build system of the Sage system until now and didn't think about the build process of the library. Since availability of dependencies is ensured by the Sage system, the build process of the Sage library doesn't check for dependencies, right? Your idea is to add dependency checks to the library build, and that may be a good idea, but one could also consider to let the top level build scripts keep the job of handling the dependencies and do the checks there. I'm not saying that this would be better, just that this was my idea until now. Every distribution has its own way to organize patches. I think Sage already has a good test coverage and a Debian package should of course run all the tests during build. iirc the tests are contained within sage.spkg (where the library is), so that should be possible. other tests may come within other spkgs. Remember the git transition. spkg's will go away. There will be just one tarball containing everything in the future. The sources of other projects will be better separated, so it will be easy to get a Sage tarball without sources of other projects. Taking this into account, it probably makes sense to have only one Sage Debian source package. spkgs won't fully go away -- with the initial transition we are simply emulating the current spkg model. That said, there has been some work in transitioning to the ebuild format to use portage as a package manager -- but from what I understand, this is still a ways off. One thing to note with the git transition is that I made an effort to (mostly) separate the build system from the sage library (by this I mean the core components of sage: the python library, csage, documentation, scripts, ...). So hopefully this will help in determining what is needed in packaging sage. For those so inclined to browse the current status of the git transition, the repository is at https://github.com/sagemath/sage. It seems to me that you understood that Sage should build all spkg's in any case and just install them somewhere else. I think that means the step you call fix Sage the operating system is not needed right? Now that I have clarified this, any new thoughts? for debian or other distributions, i dont see the need for any changes to sage (the system). making sagelib distributable doesn't help skipping spkgs. so there are still two subprojects: - improve sage (the library) distributability - enhance setup.py (better switch to autotools) - get libcsage.deb and python-sage.deb packages - run the unit tests from debian/rules - (also pack other stuff) - pave the way for local spkgs (e.g. installed to ~/.sage/local) - [..] Switching to autotools is something we can't decide alone. What do Sage developers say? Do you mean with Sage (the library) all Sage components including notebook etc? - fix sage the system - implement/incorporate top level configure script - figure out flags, pass down to spkg-compilation - build sage the upstream way skipping some spkgs - [..] in fact, the second is not needed, neither for me, nor for the debian package. the project description implies something different, which is confusing. It would still be nice if the top level script could be used by distributions. There are still several things to build and other things to do, if external dependencies are not built, and we should not implement all this in debian/rules. One could start with the option to build all or none of the dependencies and then maybe go further to allow more combinations. But I'm also not entirely sure if combining system and bundled dependencies is needed. Maybe an alternative build script for building with system libraries would be a better idea. Are there other opinions? Cheers, Tobias -- 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 http://groups.google.com/group/sage-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out. -- Andrew -- You received this message
[sage-devel] Re: [sage-combinat-devel] Canonical form for permutation groups
In GAP one would just IdGroup() to get a unique label.
Is this given for any finite group in GAP, or is this depending on
http://www.gap-system.org/Packages/sgl.html ? It looks like there is
not much to do beyond these IdGroup in Sage since I guess they would
have gone beyond n=22 in Gap otherwise). On sage-devel, John Cremona
was basically suggesting the same as a unique labelling for small
groups.
- (1,2)
- (2,3)
- (1,2)(3,4)
- the multiplicative group ({-1,1}, *).
That is right, these should all result in the same group... and yes, I
forgot to add the action on the entries of the multiplication table.
So some canonical generating system on a particular subgroup of a
finite permutation group would not be enough.
Cheers, Christian
--
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 http://groups.google.com/group/sage-devel?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
[sage-devel] new optional (or experimental) package CSDP?
Dear all, we'd like to add CSDP, (a fast semidefinite programming solver, one of the very best around), as an optional package. https://projects.coin-or.org/Csdp/ It is a C library+headers, and I've written almost all what is needed (besides spkg-install etc) to have it seamlessly installable (using autotools) into Sage, here: https://github.com/dimpase/csdp One major customer of CSDP in Sage is Flagmatic, see http://flagmatic.org/ We are also working on a Cython interface to CSDP, and hope to have it ready soon. CSDP itself has a GPL-incompatible license imposed by the employer of the developer of CSDP, so it itself cannot become standard. I understand that we need to vote on this. (Needless to say I'm committed to support CSDP as an optional package of Sage for the coming N years). Please vote on the following options: 1) Yes to CSDP becoming an optional package 2) no to 1), but yes to CSDP becoming an experimental package. 3) no, no, just go away. Thanks, Dima -- 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 http://groups.google.com/group/sage-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
[sage-devel] Re: Mercurial refuses to access to combinat.sagemath.org
the latter command (hg --debug clone http://combinat.sagemath.org/patches/ ) works for me, I didn't try the former. On Wednesday, 10 April 2013 03:42:43 UTC+8, fhivert wrote: Dear All, I'm stuck on the following agravating problem: hg refuses to connect to combinat: popcorn-*oved/.hg/patches $ hg --debug pull -u using http://combinat.sagemath.org/patches/ sending capabilities command abort: error: Connection reset by peer or popcorn-/tmp $ hg --debug clone http://combinat.sagemath.org/patches/ using http://combinat.sagemath.org/patches/ sending capabilities command abort: error: Connection reset by peer I tried to - use sage or my distro's version of mercurial - remove my .hgrc without any changes. There is no problem accessing with my browser. At this point, I've no idea on how to get more information on what's happening. Any suggestion ? Cheers, Florent -- 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 http://groups.google.com/group/sage-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
[sage-devel] Re: Canonical form for permutation groups
On Wednesday, 10 April 2013 20:59:49 UTC+8, Christian Stump wrote: Hi, I wonder if there is a way to get a canonical form of a subgroup of a permutation group (or, even better, any group). This would be something like a method canonical_labeling for permutation groups that returns an isomorphic permutation group, and such that two groups are isomorphic if and only if their canonical labellings coincide. I don't think anything like that is currently implemented, right? A natural implementation would be to compute the multiplication table of the group, apply the canonical form algorithm from graphs (by simultaneous row and column permutations of the multiplication table), obtain a canoncial form of the multiplication table, and turn this data into a canonical form of a permutation group. no, no, that's not what you want to do, certainly. A much more efficient way is to compute a strong generating set w.r.t. a canonical minimal base. (A base of a permutation group is a tuple of points (s_1,...,s_t) s.t. each group element g is uniquely defined by (g(s_1),...,g(s_t))). @Nathann et al.: would this be doable without too much effort from the current algorithm for graphs? How far is the current implementation from the possibility to take any n*n array (or square matrix, but with no/less restrictions on the entries) and get it into a canonical form by simultaneous row and column permutations? Cheers, Christian -- 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 http://groups.google.com/group/sage-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
Re: [sage-devel] Re: Canonical form for permutation groups
no, no, that's not what you want to do, certainly. A much more efficient way is to compute a strong generating set w.r.t. a canonical minimal base. data into a canonical form of a permutation group. There is no canonical minimal base, unless one specifies the group action to such an extent that most permutation group representations are excluded. Seriously, if you need some sort of canonical form for permutation groups, you must restrict to primitive actions. In the real world, this just isn't a sensible approach. Each abstract group has infinitely many permutation group representations. ONLY the primitive representations are currently classified in any detail below a given degree, and as such those are the only canonical representations that would even be available. Jaosn -- 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 http://groups.google.com/group/sage-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
[sage-devel] Re: new optional (or experimental) package CSDP?
On Apr 10, 8:52 pm, Dima Pasechnik dimp...@gmail.com wrote: 2) yes to CSDP becoming an experimental package. Doing that requires no different work from preparing it to be an optional package, so why not do that first? Once that's done I would expect it'll be pretty smooth sailing into optional status. -- 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 http://groups.google.com/group/sage-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
Re: [sage-devel] Re: new optional (or experimental) package CSDP?
Le 11/04/2013 06:32, Nils Bruin a écrit : On Apr 10, 8:52 pm, Dima Pasechnikdimp...@gmail.com wrote: 2) yes to CSDP becoming an experimental package. Doing that requires no different work from preparing it to be an optional package, so why not do that first? Once that's done I would expect it'll be pretty smooth sailing into optional status. +1 Snark on #sagemath -- 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 http://groups.google.com/group/sage-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
