2 views

Skip to first unread message

Oct 1, 2010, 7:37:06 AM10/1/10

to sage-devel, sage-comb...@googlegroups.com

Hi!

My colleague Robert Müller pointed me to the fact that free algebras

in Sage seem to be highly inefficient:

sage: R.<a,b,c> = FreeAlgebra(GF(3),3)

sage: f = a^2+b

sage: timeit('g=f^12')

5 loops, best of 3: 1.14 s per loop

GAP does much better:

sage: RG = gap.FreeAlgebra(GF(3),'["a","b","c"]')

sage: fG = RG.1^2+RG.2

sage: timeit('g=fG^12')

5 loops, best of 3: 54.4 ms per loop

And LetterPlace algebra (I think in Singular since version 3-1-0, but

the example below was done with 3-1-1) is even faster. The

disadvantage: It requires a degree bound.

sage: singular.LIB("freegb.lib")

sage: R0 = singular.ring(0,'(a,b,c)','dp')

sage: RS = singular.makeLetterplaceRing(50)

sage: RS.set_ring()

sage: fS = singular('a(1)*a(2)+b(1)')

sage: fS.lpPower(2)

a(1)*a(2)*a(3)*a(4)+a(1)*a(2)*b(3)+b(1)*a(3)*a(4)+b(1)*b(3)

sage: timeit('g=fS.lpPower(12)')

25 loops, best of 3: 23.7 ms per loop

In the near future (probably at least until december) I will not have

the time to this myself, but it seems rather obvious that in addition

to FreeAlgebra_generic there should also be a FreeAlgebra_gap and a

FreeAlgebra_letterplace, wrapping the functionality provided by GAP

and Singular. The constructor "FreeAlgebra" would then choose the

appropriate implementation or let the user choose.

Does someone volunteer to implement it?

Best regards,

Simon

My colleague Robert Müller pointed me to the fact that free algebras

in Sage seem to be highly inefficient:

sage: R.<a,b,c> = FreeAlgebra(GF(3),3)

sage: f = a^2+b

sage: timeit('g=f^12')

5 loops, best of 3: 1.14 s per loop

GAP does much better:

sage: RG = gap.FreeAlgebra(GF(3),'["a","b","c"]')

sage: fG = RG.1^2+RG.2

sage: timeit('g=fG^12')

5 loops, best of 3: 54.4 ms per loop

And LetterPlace algebra (I think in Singular since version 3-1-0, but

the example below was done with 3-1-1) is even faster. The

disadvantage: It requires a degree bound.

sage: singular.LIB("freegb.lib")

sage: R0 = singular.ring(0,'(a,b,c)','dp')

sage: RS = singular.makeLetterplaceRing(50)

sage: RS.set_ring()

sage: fS = singular('a(1)*a(2)+b(1)')

sage: fS.lpPower(2)

a(1)*a(2)*a(3)*a(4)+a(1)*a(2)*b(3)+b(1)*a(3)*a(4)+b(1)*b(3)

sage: timeit('g=fS.lpPower(12)')

25 loops, best of 3: 23.7 ms per loop

In the near future (probably at least until december) I will not have

the time to this myself, but it seems rather obvious that in addition

to FreeAlgebra_generic there should also be a FreeAlgebra_gap and a

FreeAlgebra_letterplace, wrapping the functionality provided by GAP

and Singular. The constructor "FreeAlgebra" would then choose the

appropriate implementation or let the user choose.

Does someone volunteer to implement it?

Best regards,

Simon

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu