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:

Status badges

Description (last modified by Travis Scrimshaw)

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.


sage: R.<x,y,z> = FreeAlgebra(Integers(2))
sage: 1 in R
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
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
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 Travis Scrimshaw

Cc: Travis Scrimshaw added
Description: modified (diff)
Type: defectenhancement

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).

Note: See TracTickets for help on using tickets.