Opened 6 years ago
Last modified 6 years ago
#22708 new enhancement
Change default implementation of FreeAlgebra
Reported by: | Simon King | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-8.0 |
Component: | algebra | Keywords: | |
Cc: | Travis Scrimshaw | Merged in: | |
Authors: | Reviewers: | ||
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
By default, FreeAlgebra uses a rather sluggish default implementation written in Python. We have several implementations of free algebras that provide faster arithmetics: letterplace and path algebras.
Example:
sage: R.<x,y,z> = FreeAlgebra(Integers(2)) sage: 1 in R True sage: %timeit (x+y+z)*(x+y+z) 10000 loops, best of 3: 99.2 µs per loop sage: R.<x,y,z> = FreeAlgebra(Integers(2), implementation='letterplace') sage: 1 in R True sage: %timeit (x+y+z)*(x+y+z) 10000 loops, best of 3: 31.7 µs per loop sage: R = DiGraph({1:{1:['x','y','z']}}).path_semigroup().algebra(Integers(2)) sage: R.inject_variables() Defining e_1, x, y, z sage: 1 in R True sage: %timeit (x+y+z)*(x+y+z) 100000 loops, best of 3: 4.5 µs per loop
I suggest to
- add "paths" as possible value of the
implementation
keyword of FreeAlgebra. - let "paths" be the default implementation, as "generic" seems the slowest of them all.
Note that "letterplace" can not be the default, as is does not allow the creation of inhomogeneous elements. That's not a problem for path algebras, but it may be needed to add more functionality to path algebras in order to make it a true replacement for the generic implementation.
Change History (1)
comment:1 Changed 6 years ago by
Cc: | Travis Scrimshaw added |
---|---|
Description: | modified (diff) |
Type: | defect → enhancement |
Note: See
TracTickets for help on using
tickets.
I think we should focus a little bit more on speeding up the default/generic implementation. Towards that goal, #22632 will be the first step (and benefit a larger portion of Sage). The next step would be directly cythonizing the free algebra element and possibly having a better/faster index set.
I would say defect = bug, and just being the slowest would not have it fall into that category IMO (especially since it is possibly the most general).