Hey Simon,
>
> On 2017-03-29, Nicolas M. Thiery <nicolas...@u-psud.fr <javascript:>>
> wrote:
> > It would be interesting to know specifically on which aspects the path
> > algebra is improving on the current free algebra. The data structure
> > of indices (i.e. words in the generators)? The data structure for
> > representing linear combinations? The implementation of the product?
> >
> > Maybe some of those improvements could be lifted up to FreeModule in
> > the first place, or provide an alternative generic implementation of
> > it that would work better for your use case [1].
>
> My own use case is proper path algebras with *several* vertices. So,
> FreeModule won't cover my own applications.
>
> My comment was motivated by a question on sage-support. The question
> has merely been about the fact that 1 is not recognised as an element
> of a free algebra over ZZ, and while trying to give the user some
> work-arounds, I played with different ways to create what mathematically
> is a free associative algebra.
>
> I agree that this is something that should be fixed (actually 0 is not
recognized as being in a CFM, which is a bug IMO). I would just check to
see if the element can be converted to the base ring, possibly putting
something in CFM rather than FreeAlgebra which also checks if the CFM is in
UnitalAlgebras.
> Why is it faster?
> 1. Paths are implemented as BoundedIntegerSequences, which in turn
> are implemented as bitsets. Concatenation ultimately relies on
> bitshift operations, that are quite efficiently implemented in
> MPR.
> 2. Path algebra elements are implemented as ordered chain of terms
> ("chain" as in "a term is a C struct that has a pointer to
> the next term").
>
> You can of course easily benefit from using 1. for the indices.
> If you have n generators, then your indices simply are sequences
> of integers bounded by n.
> - Multiplication is list concatenation, which is faster than for
> Python tuples and (if I recall correctly) even faster than operations
> that are based on implementing integer sequences as C "*int".
- CombinatorialFreeModule.Element is (IIRC) implemented as dictionary,
> where the indices are used as keys. BoundedIntegerSequence is
> faster than python tuples both in hash and comparison (in particular
> if the tuples have common starting sequences).
>
We definitely could do this, and I would consider having a small
intermediate layer of converting to/from the current indices (elements of a
free group) for backwards compatibility.
There is also a little bit of a question of do we still want CFM to be the
base class of FreeAlgebra since we have started to decouple the pieces of
CFM (specifically, lifting more things to the category) and FreeAlgebra
overrides a number of things. However, that is somewhat a separate issue
that can be tackled once we handle speeding up the basic operations.
>
> In fact, this is what has been done in an earlier implementation of
> path algebras. However, 2. is still faster than an implementation that
> expresses elements as dictionaries. But I guess you don't want
> an implementation of CombinatorialFreeModuleElementWithMonomialOrdering.
>
> Well, we do have a number of CFM subclasses that explicitly have a total
ordering of the indices (e.g., symmetric functions and partitions by lex
order). However, I could see this being slower than as dicts for elements
with a lot of terms when you have to, e.g., add two elements: you have to
sort the two chains (which my interpretation of your description is a chain
is a singlely linked list).
Best,
Travis
--
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 https://groups.google.com/group/sage-combinat-devel.
For more options, visit https://groups.google.com/d/optout.
