Hi Nicolas,
On 2017-03-29, Nicolas M. Thiery <nicolas.thi...@u-psud.fr> 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.
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).
Examples:
sage: L1 = tuple(randint(0,49) for _ in range(1000))
sage: L2 = tuple(randint(0,49) for _ in range(1000))
sage: from sage.data_structures.bounded_integer_sequences import
BoundedIntegerSequence
sage: BL1 = BoundedIntegerSequence(50, list(L1))
sage: BL2 = BoundedIntegerSequence(50, list(L2))
sage: %timeit BL1+BL2
1000000 loops, best of 3: 312 ns per loop
sage: %timeit L1+L2
100000 loops, best of 3: 4.16 µs per loop
sage: %timeit hash(BL1)
10000000 loops, best of 3: 83.5 ns per loop
sage: %timeit hash(L1)
100000 loops, best of 3: 3.34 µs per loop
sage: CBL1 = BoundedIntegerSequence(50, list(L1))
sage: %timeit BL1==BL2
10000000 loops, best of 3: 66.8 ns per loop
sage: %timeit BL1==CBL1
10000000 loops, best of 3: 124 ns per loop
sage: CL1 = tuple(list(L1))
sage: %timeit L1==L2
10000000 loops, best of 3: 53.8 ns per loop
sage: %timeit L1==CL1
100000 loops, best of 3: 4.83 µs per loop
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.
Best regards,
Simon
--
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.
