wjansen's profile - activity

Thanks, calling 'vector_space' on 'K' is the crucial point. BTW, I read the documents in "sage/rings/finite_rings/finite_field_constructor.py" and many others up and down looking for all occurrences of 'def ' (restricted to these since I was looking for a method definition) but did not find something related to my question. Now I did it a second time and see 'V = k.vector_space()' is an example comment in "sage/rings/finite_rings/finite_field_ntl_gf2e.py" (probably, also in some other files). My failure was to ignore comments.

Hi all,

any finite extension (say degree n) of a field K may be considered as vector space over K. In particular, the roots of any irreducible polynomial f of degree n over a finite field K constitute a basis of this vector space.

Does SageMath provide a routine to construct the vector space for given K and f?

Such a vector space seems to be used internally when constructing Kn=GF(K.order()^n,'a',modulus=f). If so then the question becomes: Is this vector space open to the public? And how can I use it?

Thanks in advance Wolfgang Jansen

I used the installation procedure according to "http://www.sagemath.org/download-linux.html", entry "Ubuntu PPA" (only the last of the three commands is relevant to find out what had been installed). The link points to version 7.6, but when I installed version 7.5.1 it was the same procedure. Well, I can try to upgrade to version 7.6 to see what happens.

Addendum 1: I did without success: "sagemath-upstream-binary" still provides version 7.5.1.

Addendum 2: Now, I installed version 7.6 from a tar.bz2 archive according to entry "Usage" in the link given above (i.e. no upgrade): the missing sources are there, hurrah! If the stripping down is really necessary to generate the PPA it may be wise to add a comment in entry "Ubuntu PPA".

That's so in your case, not in mine.

My installation contains only one subdirectory of .../sage/src, namely doc. So it may be an installation issue. What can I do to install more subdirectories? I installed the compiled SageMath, not from source code.

BTW, I searched the installation directory for file names having two asterisks: "polynomial_zmodasterisk.pyasterisk" including the "pyx" files. Unfortunately, both asterisks were deleted in the formatted question you see (and, my failure, I did not look at it).

Hello all,

I am using SageMath-7.5.1 on a Linux platform. Sometimes I am interested in the source code for studying implementation details. When asking for documentation or source code, e.g.

R.<x>=GF(61)[] ; p=x^3 + x^2 + 59*x + 60 ; p?

then the documentation may contain a line like:

~/.sage/temp/WJ1/6067/spyx/sage/rings/polynomial/polynomial_zmod/sage/rings/polynomial/polynomial_zmod_flint.pyx

But directory "~/.sage/temp/WJ1/6067" is empty! Neither does the SageMath installation directory "/usr/lib/sagemath" (recursively searched) contain a file "polynomial_zmod.py". So, where is the source code?

Thanks in advance

I would like to "accept", but I do not know how to do (I do not see a button or the like named "accept").

It is a Singular problem since I misused Singular for its availability to handle sparse polynomials (FLINT, NTL don't). The polynomial ring is created for a given prime number 'p' by PolynomialRing(GF(p),1,'x') The second argument '1' forces SageMath to switch to Singular.

I cannot tell you the output of 'type(f)' since 'f' is not generated at all. For a polynomial of smaller degree the output is <type 'sage.rings.polynomial.multi_polynomial_libsingular.mpolynomial_libsingular'="">

The "bug" is not a bug, it is a restriction implemented in Singular's official release. Unfortunately, Singular does not publish its restrictions (at least, I did not found one when reading its home page forth an back), so it appeared as a bug.

On the one hand, 16-bit exponents seem to be intentional, i.e. intended by Singular. On the other hand, there is at least one Singular version that supports larger exponents. I do not understand who this version implemented (released as Singular version or implementation within SageMath only). Anyway, the version with larger exponents is not in the recent SageMath release.

Meanwhile I made more experiments. The smallest polynomial degree forcing the error is 2^16. So I expect that the currently installed Singular version uses unsigned 16-bit words for exponents (and that the previous version had a larger representation, there I generated polynomials up to a degree of 27 bits then my computer was at the edge of its memory).

I had also a look on Singular's home page but I did not find any hint on technical restrictions or on internal data representation.

As workaround, I will try to re-install SageMath-7.3 from the Git repository. I hope the repository contains besides SageMath's core also the then actual external libraries.

Addendum (15-02-2017) :

It is a Singular problem since I misused Singular for its ability to handle sparse polynomials, also univariate ones (FLINT, NTL don't). The polynomial ring is created for a given prime number p by PolynomialRing(GF(p),1,"x"). The second argument 1 forces SageMath to switch to Singular.

The "bug" is not a bug, it is a restriction (16 bit exponents) implemented in Singular's official release. Unfortunately, Singular does not publish its restrictions (at least, I did not found one when reading its home page forth an back), so the violated restriction appeared as a bug. What about adding a comment in SageMath's documentation of PolynomialRing?

By contrast, version SageMath-7.3 included a modification of Singular where the restriction was set to 32 or 64 bit exponents, so the bug did not occur.

Today I upgraded SageMath from 7.3 to 7.5.1, then I tried to continue yesterday's work: generating a sparse univariate polynomial using Singular, the polynomial has degree beyond that of toy polynomials. Yesterday, this worked fine, today I get the error message

exponent overflow (117649)

How can this happen? And what can I do to get the previous facilities of Singular (possibly, this means the previous facilities of SageMath)?

Thanks in advance

I see that I misunderstood the words "generic" and "with_category" in type name "sage.rings.polynomial.polynomial_element_generic.PolynomialRing_field_with_category.element_class". I thought the type name means something like a common superclass to the various implementations ("generic") with a switch to the actual implementation ("with_category"). Now I see that the type name specifies a third implementation besides FLINT and NTL. I read documentation "Sage Reference Manual: Polynomials" forth and back but I did not find a hint on this meaning. Would it be possible to add a relating comment into this paper (and into the "Tutorial")? Moreover, it may be wise to add a comment into the online documentation of "PolynomialRing.__init__" stating that argument "implementation" is ignored if "sparse=True" and a third (not otherwise mentioned) implementation is used instead.

Thanks for the hint to use multivariate polynomials instead of the univariate ones. Polynomials of a degree so big that they do not fit into memory when using a dense univariate implementation do not make problems anymore. But, of course, the multivariate implementation adds some computational overhead. For my polynomials when the dense univariate implementation is on its limits (degree about 10^7, density 1.2%), the computing times for polynomial generation (most time is spent for multiplication) are coarsely related as

univariate_dense : multivariate : univariate_sparse = 1 : 500 : 1000.

So switching to multivariate polynomials does not much help. In other words, the implementation of sparse univariate polynomials by a Python dictionary is not as bad as one might think.

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

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

    INPUT: 

    "deg" target degree (natural number)

    "ch" field characteristic (prime number)

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

    OUTPUT:

    Polynomial in 'x' of degree "deg" over field "GF(ch)".
    Only about "deg^ex" (where "ex"<1) coefficients are not zero, 
    value of "ex" depends on "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(ch),'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

Thanks for the answer. I was not aware of calls like "some_polynomial.roots(Some_structure)".

Thanks for the answer. Now, I understand the error's background. I was not aware of calls like "some_polynomial.roots(Some_structure)". This way, things become really simple, in particular, since the polynomials had originally been generated in QQ['x'].

Hi all,

when I enter command

solve(symbolic_expression(x^12 - x^11 - 12*x^10 + 11*x^9 + 54*x^8 - 43*x^7 - 113*x^6 + 71*x^5 + 110*x^4 - 46*x^3 - 40*x^2 + 8*x + 1)==0, var(x), to_poly_solve=True)

I get the expected result, but when I enter command

solve(symbolic_expression(x^10 - 10*x^8 + 35*x^6 + x^5 - 50*x^4 - 5*x^3 + 25*x^2 + 5*x - 1), var(x), to_poly_solve=True)

I get the error message

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-203-6108bea90b72> in <module>()
----> 1 solve(symbolic_expression(x**Integer(10) - Integer(10)*x**Integer(8) + Integer(35)*x**Integer(6) + x**Integer(5) - Integer(50)*x**Integer(4) - Integer(5)*x**Integer(3) + Integer(25)*x**Integer(2) + Integer(5)*x - Integer(1)),var(x),to_poly_solve=True)

/usr/local/sage-6.4.1-x86_64-Linux/local/lib/python2.7/site-packages/sage/symbolic/relation.py in solve(f, *args, **kwds)
    732     from sage.symbolic.expression import is_Expression
    733     if is_Expression(f): # f is a single expression
--> 734         ans = f.solve(*args,**kwds)
    735         return ans
    736 

/usr/local/sage-6.4.1-x86_64-Linux/local/lib/python2.7/site-packages/sage/symbolic/expression.so in sage.symbolic.expression.Expression.solve (build/cythonized/sage/symbolic/expression.cpp:47061)()

/usr/local/sage-6.4.1-x86_64-Linux/local/lib/python2.7/site-packages/sage/symbolic/expression.so in sage.symbolic.expression.Expression.solve (build/cythonized/sage/symbolic/expression.cpp:46887)()

TypeError: 'sage.symbolic.expression.Expression' object does not support indexing

What happened here? The error message is totally misleading (no index in the command!) and it is not to understand why the second command fails while the first works fine.

By the way, the polynomial in question has ten simple real roots, so there should be no problem to compute the roots if symbolic evaluation is not possible.

Thanks in advance Wolfgang