94 views

Skip to first unread message

Jan 24, 2013, 7:38:24 AM1/24/13

to sage-a...@googlegroups.com

Dear all,

I've juste created #13999 which deal with Ideal membership for univariate

polynomial.

sage: R.<x> = PolynomialRing(ZZ)

sage: p, q = 4 + 3*x + x^2, 1 + x^2

sage: I = R.ideal([p, q])

sage: S = R.quotient_ring(I)

sage: S(p) == S(0)

False

I can probably fix the problem when the coefficient ring is a field but I

don't know how to compute when it's a general ring (Hermite normal form,

grobner basis or no known algorithm ???). Does anyone with the necessary

mathematical and technical knowledge is willing to fix the problem, and fixing

by the way the trivial field case ?

Cheers,

Florent

I've juste created #13999 which deal with Ideal membership for univariate

polynomial.

sage: R.<x> = PolynomialRing(ZZ)

sage: p, q = 4 + 3*x + x^2, 1 + x^2

sage: I = R.ideal([p, q])

sage: S = R.quotient_ring(I)

sage: S(p) == S(0)

False

I can probably fix the problem when the coefficient ring is a field but I

don't know how to compute when it's a general ring (Hermite normal form,

grobner basis or no known algorithm ???). Does anyone with the necessary

mathematical and technical knowledge is willing to fix the problem, and fixing

by the way the trivial field case ?

Cheers,

Florent

Jan 24, 2013, 8:37:46 PM1/24/13

to sage-a...@googlegroups.com

From the theoretical side it should at least be possible to use a groebner basis to solve this problem. The only problem is that sage doesn't do groebner basis for univariate polynomial rings. It does however do groebner basis for multivariate polynomial rings (even if the multivariate polynomial ring only has 1 variable). This explains why the following gives the correct answer:

sage: R.<x> = PolynomialRing(ZZ,1)

sage: type(R)

<type 'sage.rings.polynomial.multi_polynomial_libsingular.MPolynomialRing_libsingular'>

sage: p, q = 4 + 3*x + x^2, 1 + x^2

sage: I = R.ideal([p, q])

sage: S = R.quotient_ring(I)

sage: S(p) == S(0)

True

I don't know wether something smarter then groebner basis can be done in the univariate over ZZ case. But at least this shows that the code to give the right answer is already in sage, but it's not getting called for some reason.

I don't know what you mean by the "trivial field case" but at least over fields your example seems to work:

sage: R.<x> = PolynomialRing(QQ)

sage: type(R)

<class 'sage.rings.polynomial.polynomial_ring.PolynomialRing_field_with_category'>

sage: p, q = 4 + 3*x + x^2, 1 + x^2

sage: I = R.ideal([p, q])

sage: S = R.quotient_ring(I)

sage: S(p) == S(0)

True

I guess the above works because in the above R is a euclidean domain, and hence gets dealt with differently then PolynomialRing(ZZ).

Jan 25, 2013, 4:25:44 AM1/25/13

to sage-a...@googlegroups.com

The weakness of the univariate polynomial ring implementation bugs me more often than not. IMHO we should make the default univariate polynomial ring just a libSingular polynomial ring that happens to have only one variable. In terms of end-user features and consistency with multivariate polynomial rings thats just much easier. There is definitely a place for alternate implementations (NTL, Flint, PolynomialRealDense) but anything that doesn't implement groebner_basis, say, shouldn't be presented as the default to the unsuspecting user.

Jan 25, 2013, 6:53:06 AM1/25/13

to sage-a...@googlegroups.com

We should certainly add groebner basis facility for univariate polynomials, but there are good reasons that we use NTL and/or FLINT. For example:

sage: R.<x> = ZZ[]

sage: S.<y> = PolynomialRing(ZZ,1)

sage: g1 = S.random_element(degree=5000,terms=5000)

sage: g2 = S.random_element(degree=5000,terms=5000)

sage: timeit("g = g1*g2",number=1,repeat=1)

1 loops, best of 1: 8.16 s per loop

sage: f1 = R.random_element(degree=5000)

sage: f2 = R.random_element(degree=5000)

sage: timeit("f = f1*f2")

125 loops, best of 3: 2.04 ms per loop

Davidsage: R.<x> = ZZ[]

sage: S.<y> = PolynomialRing(ZZ,1)

sage: g1 = S.random_element(degree=5000,terms=5000)

sage: g2 = S.random_element(degree=5000,terms=5000)

sage: timeit("g = g1*g2",number=1,repeat=1)

1 loops, best of 1: 8.16 s per loop

sage: f1 = R.random_element(degree=5000)

sage: f2 = R.random_element(degree=5000)

sage: timeit("f = f1*f2")

125 loops, best of 3: 2.04 ms per loop

--

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu