Change default implementation of FreeAlgebra

[Simon King]

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.

[Travis Scrimshaw]

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