Revision history [back]

I do some work on polynomials over finite fields. Generated polynomials of larger degree are sparse in the sense that only a few coefficients are not zero. I tried to utilize this property by defining PR=PolynomialRing(GF(7),name='x',sparse=True). Then type(PR) is <class 'sage.rings.polynomial.polynomial_ring.polynomialring_field_with_category'=""> what is not very informative. It is not clear which library is involved (FLINT, NTL, Sage's own implementation, or something else), and libraries FLINT, NTL seem not to support sparse polynomials (sparse in the sense of storing only the non-zero coefficients similar to sparse matrices). So what does "sparse=True" mean? Is there a reduction of occupied memory? Anyway, time consumption for multiplication increases tremendously (I expected a major reduction). Thanks in advance.

I do some work on polynomials over finite fields. Generated polynomials of larger degree are sparse in the sense that only a few coefficients are not zero. I tried to utilize this property by defining PR=PolynomialRing(GF(7),name='x',sparse=True). Then type(PR) is <class 'sage.rings.polynomial.polynomial_ring.polynomialring_field_with_category'=""> what is not very informative. It is not clear which library is involved (FLINT, NTL, Sage's own implementation, or something else), and libraries FLINT, NTL seem not to support sparse polynomials (sparse in the sense of storing only the non-zero coefficients similar to sparse matrices). So what does "sparse=True" mean? Is there a reduction of occupied memory? Anyway, time consumption for multiplication increases tremendously (I expected a major reduction). Thanks in advance.

INPUT: 

"deg" target degree (natural number)

"char" field characteristic and order (prime number)

"sparse" whether a sparse implementation to use (boolean)

OUTPUT:

Polynomial in 'x' of degree "deg" over field "GF(char)".
Only about "deg^ex" (where "ex"<1) coefficients are not zero, value of "ex" depends on "char".
"""
R = PolynomialRing(GF(char),'x',sparse=sparse)
i0 = 0
r0 = R(1)
s = R.gen()
if deg==0:
    return r0
i1 = 1
r1 = s+R(1)
if deg==1:
    return r1
i2 = 2
r2 = s*r1 - r0
if deg==2:
    return r2
k = 1
while i2<deg:
    if deg&k != 0:
        i3 = 2*i2 - i1
        r3 = s*r2 - r1
        i0 = i1
        r0 = r1
        i1 = i3
        r1 = r3
    else:
        i1 = i2
        r1 = r2
    k = 2*k
    s = s**2 - 2
    i2 = 2*i1 - i0
    r2 = s*r1 - r0
    if deg==i2:
        return r2
return r3

I do some work on polynomials over finite fields. Generated polynomials of larger degree are sparse in the sense that only a few coefficients are not zero. I tried to utilize this property by defining PR=PolynomialRing(GF(7),name='x',sparse=True). Then type(PR) is <class 'sage.rings.polynomial.polynomial_ring.polynomialring_field_with_category'=""> what is not very informative. It is not clear which library is involved (FLINT, NTL, Sage's own implementation, or something else), and libraries FLINT, NTL seem not to support sparse polynomials (sparse in the sense of storing only the non-zero coefficients similar to sparse matrices). So what does "sparse=True" mean? Is there a reduction of occupied memory? Anyway, time consumption for multiplication increases tremendously (I expected a major reduction). Thanks in advance.

Function "make_pol" defined below generates for any target degree "deg" a polynomial over a finite field. Only about "deg^ex" coefficients are not zero where "ex" depends on the field's order and is in interval (1/2, 1), in particular "ex" is about 3/4 for field order 7. The reason for the sparsity is not yet understood. Multiplication of polynomials over GF(7) of degrees 100043 and 100361 (and 6144 coefficients each) generated this way takes 36 milliseconds for dense implementation but 29 seconds (without "milli"!) for sparse implementation (similarly for the function call, the function uses multiplications). If you are curious about the chosen degrees: these are Sophie Germain primes, they are of special interest since the generated polynomials are irreducible.

Platform info: 64 bit, 3.3GHz, Linux, Sage 7.1 (Release Date: 2016-03-20)

Function "make_pol" defined below generates for any target degree "deg" a polynomial over a finite field. Only about "deg^ex" coefficients are not zero where "ex" depends on the field's order and is in interval (1/2, 1), in particular "ex" is about 3/4 for field order 7. The reason for the sparsity is not yet understood. Multiplication of those polynomials of degrees 100043 and 100361, resp., takes 36 milliseconds for dense implementation but 29 seconds (without "milli"!) for sparse implementation (similarly for the function call, the function uses multiplications). If you are curious about the chosen degrees: these are Sophie Germain primes, they are of special interest since the generated polynomials are irreducible.

` from sage.all import ZZ, GF, PolynomialRing

def make_pol(deg, char, sparse): """ Generate a sparse polynomial over a finite field.

INPUT: 

"deg" target degree (natural number)

"char" field characteristic and order (prime number)

"sparse" whether a sparse implementation to use (boolean)

OUTPUT:

Polynomial in 'x' of degree "deg" over field "GF(char)".
Only about "deg^ex" (where "ex"<1) coefficients are not zero, value of "ex" depends on "char".
"""
R = PolynomialRing(GF(char),'x',sparse=sparse)
i0 = 0
r0 = R(1)
s = R.gen()
if deg==0:
    return r0
i1 = 1
r1 = s+R(1)
if deg==1:
    return r1
i2 = 2
r2 = s*r1 - r0
if deg==2:
    return r2
k = 1
while i2<deg:
    if deg&k != 0:
        i3 = 2*i2 - i1
        r3 = s*r2 - r1
        i0 = i1
        r0 = r1
        i1 = i3
        r1 = r3
    else:
        i1 = i2
        r1 = r2
    k = 2*k
    s = s**2 - 2
    i2 = 2*i1 - i0
    r2 = s*r1 - r0
    if deg==i2:
        return r2
return r3

`

I do some work on polynomials over finite fields. Generated polynomials of larger degree are sparse in the sense that only a few coefficients are not zero. I tried to utilize this property by defining PR=PolynomialRing(GF(7),name='x',sparse=True). Then type(PR) is <class 'sage.rings.polynomial.polynomial_ring.polynomialring_field_with_category'=""> what is not very informative. It is not clear which library is involved (FLINT, NTL, Sage's own implementation, or something else), and libraries FLINT, NTL seem not to support sparse polynomials (sparse in the sense of storing only the non-zero coefficients similar to sparse matrices). So what does "sparse=True" mean? Is there a reduction of occupied memory? Anyway, time consumption for multiplication increases tremendously (I expected a major reduction). Thanks in advance.

Function "make_pol" defined below generates for any target degree "deg" a polynomial over a finite field. Only about "deg^ex" coefficients are not zero where "ex" depends on the field's order and is in interval (1/2, 1), in particular "ex" is about 3/4 for field order 7. The reason for the sparsity is not yet understood. Multiplication of polynomials over GF(7) of degrees 100043 and 100361 (and 6144 coefficients each) generated this way takes 36 milliseconds for dense implementation but 29 seconds (without "milli"!) for sparse implementation (similarly for the function call, the function uses multiplications). If you are curious about the chosen degrees: these are Sophie Germain primes, they are of special interest since the generated polynomials are irreducible.

Platform info: 64 bit, 3.3GHz, Linux, Sage 7.1 (Release Date: 2016-03-20)

from sage.all import ZZ, GF, PolynomialRing
 
PolynomialRing

def make_pol(deg, char, sparse):
    """
    Generate a sparse polynomial over a finite field.
 
field.

    INPUT: 

 "deg" target degree (natural number)

"char"     "ch" field characteristic and order (prime number)

 "sparse" whether a sparse implementation to use (boolean)

 OUTPUT:

 Polynomial in 'x' of degree "deg" over field "GF(char)".
"GF(ch)".
    Only about "deg^ex" (where "ex"<1) coefficients are not zero,  value of "ex" depends on "char".
"ch", e.g. "ex==3/4" for "ch==7".
    """
    if not deg in ZZ or deg<0:
        raise ValueError("First arg must be a non-negative integer.")
    if not char in ZZ or not is_prime(ch):
        raise ValueError("Second arg must be a prime number.")
    R = PolynomialRing(GF(char),'x',sparse=sparse)
PolynomialRing(GF(ch),'x',sparse=sparse)
    i0 = 0
 r0 = R(1)
 s = R.gen()
 if deg==0:
deg == 0:
        return r0
 i1 = 1
 r1 = s+R(1)
 if deg==1:
deg == 1:
        return r1
 i2 = 2
 r2 = s*r1 - r0
 if deg==2:
deg == 2:
        return r2
 k = 1
 while i2<deg:
i2 < deg:
        if deg&k deg & k != 0:
         i3 = 2*i2 - i1
2*i2-i1
            r3 = s*r2 - r1
         i0 = i1
         r0 = r1
         i1 = i3
         r1 = r3
     else:
         i1 = i2
         r1 = r2
     k = 2*k
     s = s**2 - 2
     i2 = 2*i1 - i0
     r2 = s*r1 - r0
     if deg==i2:
deg == i2:
            return r2
 return r3
  
`