Implement indexed monoids

tscrim commented 11 years ago

Implements free (abelian) monoids whose generators are indexed by an arbitrary set. This also moves common code from CombinatorialFreeModule into a new class sage.misc.indexed_generators.IndexedGenerators. With this we can now create (noncommutative) polynomials whose generators are given by a combinatorial object.

Also implements a very crude and basic version for groups.

Depends on #15309 Depends on #15169 Depends on #16349

CC: @sagetrac-sage-combinat @nthiery @sagetrac-mshimo @simon-king-jena

Component: algebra

Keywords: days54

Author: Travis Scrimshaw

Branch: 69ec7b2

Reviewer: Nicolas M. Thiéry

Issue created by migration from https://trac.sagemath.org/ticket/15289

tscrim commented 11 years ago

comment:1

Initial version. I might add a _basis_keys attribute to CombinatorialFreeModule for backwards compatibility...

nthiery commented 11 years ago

comment:2

Hi Travis,

Thanks for working on this feature! I'll try to look at it, but that won't be immediately. I would have thought we already had a ticket about that, but I might be wrong. For the record, here is a link to a discussion we had (a long time ago) about such features:

https://groups.google.com/forum/#!searchin/sage-combinat-devel/CombinatorialFreeModule$20free$20monoid/sage-combinat-devel/EH8M6bWPylk/a-FG4uFQm7AJ

Thanks again!

Cheers, Nicolas

tscrim commented 11 years ago

comment:3

Hey Nicolas,

I believe there is a ticket about making free abelian groups as ZZ-modules, and another one about converting between additive and multiplicative groups. However they currently don't apply to CombinatorialFreeModule, and none of the tickets on CombinatorialFreeModule would apply here as far as I remember.

Here's a new version which gives a groups version so we can do Laurent polynomials. This is not are fancy as the discussion would like, but it serves my purposes for now.

Best,

Travis

tscrim commented 11 years ago

Description changed:

--- 
+++ 
@@ -1 +1,3 @@
 Implements free (abelian) monoids whose generators are indexed by an arbitrary set. This also moves common code from `CombinatorialFreeModule` into a new class `sage.misc.indexed_generators.IndexedGenerators`. With this we can now create (noncommutative) polynomials whose generators are given by a combinatorial object.
+
+Also implements a very crude and basic version for groups.

tscrim commented 11 years ago

comment:4

Here's with some more functionality additions. I did make one major change and made the iterator return (generator, exp), as opposed to (index, exp) and similar to how FreeMonoid works.

Frequently I'm finding myself calling _sorted_items(), but I'm needing to manipulate the indices of the generators. I'm wondering if we should make it into a public method (perhaps with a better name since there is no true sorting occurring when it is not free).

tscrim commented 10 years ago

Dependencies: #15309

tscrim commented 10 years ago

comment:5

Rebased to 5.13.beta2.

tscrim commented 10 years ago

Attachment: trac_15289-indexed_monoids-ts.patch.gz

tscrim commented 10 years ago

Changed dependencies from #15309 to #15309 #15169

tscrim commented 10 years ago

comment:7

Added git version.

New commits:

`[c1b5afe](https://github.com/sagemath/sagetrac-mirror/commit/c1b5afe)`	`#15289: Implemented indexed monoids and groups.`
`[6fd33b2](https://github.com/sagemath/sagetrac-mirror/commit/6fd33b2)`	`#15169: Fix FreeAlgebra element constructor from a base field.`

tscrim commented 10 years ago

Commit: c1b5afe

tscrim commented 10 years ago

Branch: public/monoids/15289-indexed

tscrim commented 10 years ago

Changed keywords from none to days54

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from c1b5afe to 9dca526

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

`[9dca526](https://github.com/sagemath/sagetrac-mirror/commit/9dca526)`	`Added comparison operations.`
`[a493bee](https://github.com/sagemath/sagetrac-mirror/commit/a493bee)`	`Merge branch 'master' into public/monoids/15289-indexed`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

`545a8df`	`Merge branch 'develop' into public/monoids/15289-indexed`
`2975c87`	`Merge branch 'develop' into public/monoids/15289-indexed`
`4002b0d`	`Merge branch 'develop' into public/monoids/15289-indexed`
`9e9b769`	`Merge branch 'develop' into public/monoids/15289-indexed`
`a278afa`	`Added cardinality methods.`
`f681606`	`Added cardinality to free abelian monoid for consistancy.`
`3a0e50b`	`Merge branch 'develop' into public/monoids/15289-indexed`
`d4606cc`	`Added more robustness to element creation.`
`991953a`	`Merge branch 'develop' into public/monoids/15289-indexed`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 9dca526 to 991953a

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

`56703eb`	`Made Indexed* have entry points through Free*.`
`163df6e`	`Changed more _basis_keys to _indices, deprecated the former.`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 991953a to 163df6e

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

8db8e0a Changed `_an_element_` to indexed_monoid.py.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 163df6e to 8db8e0a

tscrim commented 10 years ago

comment:14

Hey Nicolas,

From your comments on #15726, I've made the appropriate changes here.

All Indexed* now goes through Free*, but as a special case, I have IndexedFreeAbelianGroup as FreeGroup(index_set=X, abelian=True). Should we do the same for FreeMonoid?
I want to leave __pow__ alone since they are more specialized for the data structures.
The __contains__, are you suggesting putting it into Parent? If so, that might be a can of worms and should be done on another ticket.
I'd like to keep IndexedFreeAbelianGroup as multiplicative since I want to use them as a basis indexing set for polynomials.
Similarly, the comparisons are using lex ordering, so it gives a nice default order on terms when modeling polynomial rings with indexed generators.

Thank you for looking at this (and #15726). As always, I appreciate your wisdom and insight.

Best,

Travis

New commits:

8db8e0a Changed `_an_element_` to indexed_monoid.py.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

`bd82ed8`	`Merge branch 'develop' into public/monoids/15289-indexed`
`760c939`	`Merge branch 'public/monoids/15289-indexed' of trac.sagemath.org:sage into public/monoids/15289-indexed`
`03057a4`	`Merge branch 'develop' into public/monoids/15289-indexed`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 8db8e0a to 03057a4

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

a2996e0 Merge branch 'develop' into public/monoids/15289-indexed

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 03057a4 to a2996e0

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from a2996e0 to 49068b2

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

`c1cc341`	`Merge branch 'develop' into public/monoids/15289-indexed`
`49068b2`	`Merge branch 'develop' into public/monoids/15289-indexed`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

6875cfb Merge branch 'develop' into public/monoids/15289-indexed

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 49068b2 to 6875cfb

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

1818a3e Merge branch 'develop' into public/monoids/15289-indexed

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 6875cfb to 1818a3e

nthiery commented 10 years ago

comment:21

Replying to @tscrim:

From your comments on #15726, I've made the appropriate changes here.

Argl, two months already ... sorry for lagging behind so much. I know how painful it is to get suggestions late in the process when everything is in a clean state ...

All Indexed* now goes through Free*,

Nice! Thanks!

but as a special case, I have IndexedFreeAbelianGroup as FreeGroup(index_set=X, abelian=True). Should we do the same for FreeMonoid?

It would be nice to be consistent indeed, but I have no preference for one idiom or the other. Maybe ask on sage-devel?

By the way, for this ticket or later, I have been desiring for a long time to have some systematic idiom like:

    sage: Groups().free(index_set={...})
    sage: CommutativeAdditiveGroups().free(index_set={...})
    sage: Algebras(QQ).free(index_set={...})

Then we could remove all the Free* from the global name space.

The __contains__, are you suggesting putting it into Parent? If so, that might be a can of worms and should be done on another ticket.

I was thinking of putting it in the categories, but you are right, given the mro Parent.__contains__ will take over.

In fact do you have a specific reason to override Parent.__contains__? Granted, the policy implemented in Parent.__contains__ is unsatisfactory (it's doing too much stuff to my taste, in particular stuff that can potentially be costly). And fixing it could indeed be a can of worm. On the other hand, having many parents define their own containment policy is unsatisfactory as well.

I'd like to keep IndexedFreeAbelianGroup as multiplicative since I want to use them as a basis indexing set for polynomials.

It's customary as well to index polynomials by exponent vectors in the additive group NN^n. Actually I would tend to prefer it. But that's probably something to ask on sage-devel.

Similarly, the comparisons are using lex ordering, so it gives a nice default order on terms when modeling polynomial rings with indexed generators.

As long as it's easy to customize it, I guess that's fine.

In term of code review, what should I look at at this point? Were some commits already reviewed, or should I just look at the diff w.r.t develop?

Cheers, Nicolas

tscrim commented 10 years ago

comment:22

Replying to @nthiery:

but as a special case, I have IndexedFreeAbelianGroup as FreeGroup(index_set=X, abelian=True). Should we do the same for FreeMonoid?

It would be nice to be consistent indeed, but I have no preference for one idiom or the other. Maybe ask on sage-devel?

I will do so.

By the way, for this ticket or later, I have been desiring for a long time to have some systematic idiom like:
    sage: Groups().free(index_set={...})
    sage: CommutativeAdditiveGroups().free(index_set={...})
    sage: Algebras(QQ).free(index_set={...})
Then we could remove all the Free* from the global name space.

I'll also ask about this on sage-devel, and will start the process here if there's no resistance.

I was thinking of putting it in the categories, but you are right, given the mro Parent.__contains__ will take over.

In fact do you have a specific reason to override Parent.__contains__? Granted, the policy implemented in Parent.__contains__ is unsatisfactory (it's doing too much stuff to my taste, in particular stuff that can potentially be costly). And fixing it could indeed be a can of worm. On the other hand, having many parents define their own containment policy is unsatisfactory as well.

I don't have a good reason (the annoyance is the self(x) calls the coercion framework and makes it so we can't register any coercions thereafter, but that's not a problem in how I'm using these), so I'm fine with scraping it.

I'd like to keep IndexedFreeAbelianGroup as multiplicative since I want to use them as a basis indexing set for polynomials.

It's customary as well to index polynomials by exponent vectors in the additive group NN^n. Actually I would tend to prefer it. But that's probably something to ask on sage-devel.

I'm not quite sure what you're suggesting here.

As long as it's easy to customize it, I guess that's fine.

Yes it is by passing a parameter (monomial_cmp, which should be renamed to generator_cmp) with a cmp function.

In term of code review, what should I look at at this point? Were some commits already reviewed, or should I just look at the diff w.r.t develop?

You're the only one who's really looked at this code, so a diff w.r.t. develop.

Thank you!

nthiery commented 10 years ago

comment:23

Replying to @tscrim:

I'd like to keep IndexedFreeAbelianGroup as multiplicative since I want to use them as a basis indexing set for polynomials.

It's customary as well to index polynomials by exponent vectors in the additive group NN^n. Actually I would tend to prefer it. But that's probably something to ask on sage-devel.

I'm not quite sure what you're suggesting here.

I guess I mean that I lean toward IndexedFreeAbelianGroup being additive. But that's definitely debatable. Opinion anyone?

Btw, for consistency with the naming of hte categories maybe a better name for the class could be IndexedFreeCommutativeGroup (or IndexedFreeCommutativeAdditiveGroup if we opt for additive).

You're the only one who's really looked at this code, so a diff w.r.t. develop.

Ok!

tscrim commented 10 years ago

comment:24

sage-devel thread: https://groups.google.com/forum/#!topic/sage-devel/yAvIvWxNgXE

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

`1c1b4eb`	`Changed monomial_cmp to generator_cmp and added free (static)method to monoids and groups category.`
`47b5be7`	Removed `__contains__` and fix monomial_cmp in indexed_monoid.py
`4097a8c`	`Merge branch 'develop' into public/monoids/15289-indexed`
`23301a8`	`Misc fixes and tweaks.`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 1818a3e to 23301a8

tscrim commented 10 years ago

comment:26

Hey Nicolas,

I've changed monomial_cmp to generator_cmp and made some other fixes I encountered along the way (after merging in 6.2.rc0). I've started adding in our idiom of Category.free for groups and monoids, the rest will be done in #16218 (along with possible deprecations). Back to ready for review.

Thanks,

Travis

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 23301a8 to 81eede4

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

81eede4 15289: Proofreading

nthiery commented 10 years ago

comment:28

Hi Travis,

Finally working on the review! Besides the little tidying I just committed here are some comments for the files I have been checking so far:

FreeGroup:

«if specified then the optional keyword abelian can be used» And not otherwise?
Rename indexed_group.py to indexed_free_group.py
Define group_generators rather than gens (or at the minimum define group_generators as an alias to gens) and use it whenever possible.

Element.pow: better use standard binary powering:

sage: pow = x.__class__.__pow__
sage: pow_generic = Monoids().element_class.__pow__
sage: pow_generic(x,1000) == pow(x,1000)
True

sage: %timeit pow(x,1)
1000000 loops, best of 3: 827 ns per loop
sage: %timeit pow_generic(x,1)
1000000 loops, best of 3: 521 ns per loop

sage: %timeit pow(x,-1)
100000 loops, best of 3: 6.45 µs per loop
sage: %timeit pow_generic(x,-1)
100000 loops, best of 3: 6.85 µs per loop

sage: %timeit pow(x,2)
100000 loops, best of 3: 11.5 µs per loop
sage: %timeit pow_generic(x,2)
100000 loops, best of 3: 6.07 µs per loop

sage: %timeit pow(x,50)
1000 loops, best of 3: 844 µs per loop
sage: %timeit pow_generic(x,50)
10000 loops, best of 3: 80.2 µs per loop

sage: %timeit pow(x,1000)
10 loops, best of 3: 181 ms per loop
sage: %timeit pow_generic(x,1000)
1000 loops, best of 3: 1.04 ms per loop

__len__, ... all the calls to sorted_items suggest that some sorting is involved when this is not the case.
order, rank, is_finite are identical in all the free (abelian) monoids/groups. Could we avoid the duplication?

FreeAbelianGroup:

Element.mul could use sage.combinat.dict_addition

More later tonight!

Cheers, Nicolas

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

7d27baa #15289: misc minor improvements to the doc

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 81eede4 to 7d27baa

nthiery commented 10 years ago

comment:30

Back to work!

I have been through the whole diff. Thanks for this big chunk of work! Some more comments:

IndexedGenerators

Move to sage/structure
Detailed description of what the options do: this is probably best done in the EXAMPLES section, with illustrations.
Avoid the duplication in the documentation for the print options, (in CombinatorialFreeModule and IndexedGenerators). I probably would put it in IndexedGenerators.
Side note: since the cmp function is phased out by Python 3, we will have to start thinking about what would be the most natural way to specify a total order in the context of Python 3.

FreeAbelianMonoid / FreeMonoid:

Now or later: for consistency, could we use a class with UniqueRepresentation and __classcall__ instead of a factory function?

If you decide for later, please open a ticket. Same for the items below.
Now or later: __repr__ -> _repr_, __call__ -> _element_constructor_. The custom __contains__ might not be needed.
Now or later: initialize the category
is_FreeAbelianMonoid will return False for an IndexedFreeAbelianMonoid. Do we care?
cardinality should be 1 for n=0. Same for all the following cardinality methods later in the diff
TODO: same docstring changes as in my commit (e.g. for the description of 'abelian')

IndexedMonoid:

The description is useful; I now see the point of sorted_items. We should search for a better name though. In particular the description "Return the items (i.e terms) of self, sorted for printing." is misleading, as it's not only used for printing.
Same remarks as for IndexedGroups.
cancel: shouldn't this be // ?
Special cases for converting 1 or testing equality with 1: don't bother for new monoids. That's an ugly habit in Sage and we should steer away of it.
In _elementconstructor:
- The following line is not needed; this is already taken care of by __call__:
```
if isinstance(x, IndexedFreeAbelianMonoidElement) and x.parent() is self:
   return x
```
- Construction of the generator indexed by i with F(i): I'd rather not enable this unless users come crying loud for it. F.gen(i) is fine, and it's just an endless can of worm since, as you point out later, it can be ambiguous. Besides containment testing can be expensive.

IndexedFreeAbelianMonoid:

Add an example in _element_constructor_ illustrating the construction from a dictionary.
Don't we want to always call dict on x so as to avoid a reference effect in case of a dict, throw appropriate errors if it can't be made into a dict, and accept, e.g. iterables?

nthiery commented 10 years ago

comment:31

Remaining two questions about the user interface.

Currently, the arguments passed to construct a free * are:

    def free(n=None, names='x', index_set=None, ...):

Here is a proposal for a variant:

    def free(index_set=None, names=None, prefix='x', ...)

where:

index_set=n is a short hand for index_set=[0,...,n-1] (or the equivalent IntegerRange?)
index_set='x,y,z' is a short hand for names='x,y,z'
names can either be a string like 'x,y,z' or a list or iterables of names.

Advantages:

This supports simultaneously C.free(I), C.free('x,y,z'), and C.free(3), which are the most common use cases.
This still supports F.<x,y,z> = C.free().
This is consistent with both FreeModule(QQ, 3) and CombinatorialFreeModule(QQ, I), as well as with the upcoming FreeModule(QQ,I) which will call IndexedFreeModule(QQ, I).
There is a clear distinction between the prefix and the names. Otherwise names='x' is ambiguous: a singleton list of names, or a prefix?

Second point: I am hesitant about the abelian argument. With #10963, I definitely would prefer:

    Groups().Commutative().free()

to

    Groups().free(abelian=True)

Maybe, as a more consistent temporary measure, we could use:

    Groups().free(commutative=True)

Once the above is settled, I guess this ticket is good to go!

Cheers, Nicolas

nthiery commented 10 years ago

comment:32

Btw, I am wondering whether there would be a way to obtain, with minimum duplication of code, the additive versions? After all, it's just about the names of few methods (_add_ vs _mul_, intmul vs _pow_, _neg_ vs __invert__).

rwst commented 10 years ago

comment:34

patchbot:

sage -t --long src/sage/structure/sage_object.pyx  # 1 doctest failed
sage -t --long src/sage/misc/indexed_generators.py  # 1 doctest failed

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 7d27baa to 1ff1a04

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

`6589a09`	`Merge branch 'develop' into public/monoids/15289-indexed`
`27cbf34`	`Merge branch 'develop' into public/monoids/15289-indexed`
`3f667f4`	`Merge branch 'public/monoids/15289-indexed' of trac.sagemath.org:sage into public/monoids/15289-indexed`
`90f339f`	`Doing some of the changes Nicolas requested.`
`fabaaf1`	`Merge branch 'develop' into public/monoids/15289-indexed`
`4cca67e`	`Some more fixes; still not done yet.`
`0231f73`	`Fixed the categories interface.`
`0d86682`	`Fixed all doctests except for the pickling.`
`db57ef3`	`More fixes for cardinality methods.`
`1ff1a04`	`Some whitespace fixes.`

sagemath / sage

Implement indexed monoids #15289