Revision history [back]

Actually, the types do say a lot, but you have to look at the type of an element in this case, not of the ring. No mention of finite field is made, so it looks like you're ending up with a generic implementation of sparse polynomials, implemented in python. If you investigate the code a bit you'll find it is indeed a sparse implementation, based on python dictionaries. The class itself is also a straight python class.

When you're working with polynomials over rings with expensive arithmetic, or when you're computing with polynomials that would not fit in memory with dense representation, this is a reasonable solution. However, when you're working with polynomials over a finite field, the dense implementations are so efficient that your polynomial has to be very sparse before this generic implementation is faster.

You could try defining your polynomial ring as a multivariate one (e.g., add a dummy second variable). Multivariate polynomials tend to be implemented sparsely to begin with, and there probably are fairly efficient implementations for multivariate polynomial rings over finite fields in sage, and they may well be used by default.

Seeing the type of an element:

sage: P=PolynomialRing(GF(7),sparse=True,name="x")
sage: x=P.0
sage: type(x)
<class 'sage.rings.polynomial.polynomial_element_generic.Polynomial_generic_sparse_field'>

Furthermore, x? and x?? give you documentation and source, and the file names in which you can look up further details.

Actually, the types do say a lot, but you have to look at the type of an element in this case, not of the ring. No mention of finite field is made, so it looks like you're ending up with a generic implementation of sparse polynomials, implemented in python. If you investigate the code a bit you'll find it is indeed a sparse implementation, based on python dictionaries. The class itself is also a straight python class.

When you're working with polynomials over rings with expensive arithmetic, or when you're computing with polynomials that would not fit in memory with dense representation, this is a reasonable solution. However, when you're working with polynomials over a finite field, the dense implementations are so efficient that your polynomial has to be very sparse before this generic implementation is faster.

You could try defining your polynomial ring as a multivariate one (e.g., add a dummy second variable). Multivariate polynomials tend to be implemented sparsely to begin with, and there probably are fairly efficient implementations for multivariate polynomial rings over finite fields in sage, and they may well be used by default.

Seeing the type of an element:

sage: P=PolynomialRing(GF(7),sparse=True,name="x")
sage: x=P.0
sage: type(x)
<class 'sage.rings.polynomial.polynomial_element_generic.Polynomial_generic_sparse_field'>

Furthermore, x? and x?? give you documentation and source, and the file names in which you can look up further details.

sage: e1=[ZZ.random_element(0,100000) for i in range(100)]
sage: e2=[ZZ.random_element(0,100000) for i in range(100)]
sage: 
sage: P.<x>=PolynomialRing(GF(7),sparse=True)
sage: f1=sum(x^e for e in e1)
sage: f2=sum(x^e for e in e2)
sage: %timeit f1*f2
100 loops, best of 3: 4.84 ms per loop
sage: 
sage: P.<x>=PolynomialRing(GF(7))
sage: f1=sum(x^e for e in e1) #this is a very bad way of initializing polynomials
sage: f2=sum(x^e for e in e2)
sage: %timeit f1*f2
10 loops, best of 3: 27.6 ms per loop
sage: 
sage: 
sage: P.<x,y>=PolynomialRing(GF(7))
sage: f1=sum(x^e for e in e1)
sage: f2=sum(x^e for e in e2)
sage: %timeit f1*f2
1000 loops, best of 3: 719 µs per loop