search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.31k stars 449 forks source link

cannot multiply multivariate polynomial ring and vector #27364

Open dkrenn opened 5 years ago

dkrenn commented 5 years ago 
sage: R = PolynomialRing(QQ, 't', 1); t = R.gen()
sage: (t/2) * vector([1,2])

results in a

TypeError: unsupported operand parent(s) for *: 'Multivariate Polynomial Ring in t over Rational Field' and 'Ambient free module of rank 2 over the principal ideal domain Integer Ring'

Interestingly, for a "true" univariate polynomial ring it works:

sage: R = PolynomialRing(QQ, 't'); t = R.gen()
sage: (t/2) * vector([1,2])
(1/2*t, t)

Also for a multivariate polynomial ring in more than one variable it works:

sage: sage: R = PolynomialRing(QQ, 't', 2); t = R.gen()
....: sage: (t/2) * vector([1,2])

This issue was raised by the following doctest in sage.geometry.polyhedron.base, method integrate, ticket #27365:

        Integral over a non full-dimensional polytope::

            sage: x, y = polygens(QQ, 'x, y')
            sage: P = Polyhedron(vertices=[[0,0],[1,1]])
            sage: P.integrate(x*y)    # optional - latte_int
            0
            sage: P.integrate(x*y, measure='induced')    # optional - latte_int  # not tested (see :trac:`27364`)

CC: @tscrim @yuan-zhou @kliem

Component: coercion

Author: Daniel Krenn

Branch/Commit: u/mkoeppe/poly-times-vector @ a5fd62d

Reviewer: Matthias Koeppe, ...

Issue created by migration from https://trac.sagemath.org/ticket/27364

dkrenn commented 5 years ago

Description changed:

--- 
+++ 
@@ -12,6 +12,7 @@
 Interestingly, for a "true" univariate polynomial ring it works:

+sage: R = PolynomialRing(QQ, 't'); t = R.gen() sage: (t/2) vector([1,2]) (1/2t, t)

dkrenn commented 5 years ago

Description changed:

--- 
+++ 
@@ -16,4 +16,9 @@
 sage: (t/2) * vector([1,2])
 (1/2*t, t)

+Also for a multivariate polynomial ring in more than one variable it works:

+ +sage: sage: R = PolynomialRing(QQ, 't', 2); t = R.gen() +....: sage: (t/2) * vector([1,2]) +

dkrenn commented 5 years ago

Description changed:

--- 
+++ 
@@ -22,3 +22,16 @@
 sage: sage: R = PolynomialRing(QQ, 't', 2); t = R.gen()
 ....: sage: (t/2) * vector([1,2])

+ +This issue was raised by the following doctest in sage.geometry.polyhedron.base, method integrate, ticket #27365: + +```

dkrenn commented 5 years ago

Branch: u/dkrenn/poly-times-vector

dkrenn commented 5 years ago
comment:5

Current fix indeed fixes the problem but introduces new problems:

sage: R = PolynomialRing(ZZ, 'x', 500)
sage: S = PolynomialRing(GF(5), 'x', 200)
sage: R.gen(0) + S.gen(0)

The last line takes a second or so without patch, but ages (I've interrupted after two minutes) with the change above. RunSnakeRun says that most of the time is spent in

method '_coerce_' of 'sage.structure.parent_old.Parent'

This is also not what we'd like. So what should we do now?

New commits:

54a350eTrac #27364: MPoly functor always returns MultiPolynomialRing
dkrenn commented 5 years ago

Commit: 54a350e

embray commented 5 years ago
comment:6

Ticket retargeted after milestone closed (if you don't believe this ticket is appropriate for the Sage 8.8 release please retarget manually)

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Changed commit from 54a350e to 0249494

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

2661f65Trac #27364: speedup multivariate polynomial construction
0249494Trac #27364: change doctest (due to timing)
dkrenn commented 5 years ago

Author: Daniel Krenn

dkrenn commented 5 years ago
comment:9

Replying to @dkrenn:

RunSnakeRun says that most of the time is spent in

method '_coerce_' of 'sage.structure.parent_old.Parent'

This is also not what we'd like. So what should we do now?

The current branch patches __call__ so that _coerce_ is not called that often. #25558 might change everything, but this seems somehow more out of reach.

videlec commented 5 years ago
comment:10
+            #from sage.structure.element import parent
+            #print(self, '__call__')
+            #print('    ', x, parent(x))
videlec commented 5 years ago
comment:11

As far as I understand, zero and one are already cached from sage/rings/rings.py

sage: R = QQ['x','y']
sage: R.zero() is R.zero()
True
sage: R.one() is R.one()
True
embray commented 5 years ago
comment:13

Tickets still needing working or clarification should be moved to the next release milestone at the soonest (please feel free to revert if you think the ticket is close to being resolved).

embray commented 4 years ago
comment:14

Ticket retargeted after milestone closed

mkoeppe commented 4 years ago
comment:15

Batch modifying tickets that will likely not be ready for 9.1, based on a review of the ticket title, branch/review status, and last modification date.

mkoeppe commented 4 years ago

Dependencies: #25558

mkoeppe commented 3 years ago
comment:17

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

mkoeppe commented 3 years ago

Changed branch from u/dkrenn/poly-times-vector to u/mkoeppe/poly-times-vector

mkoeppe commented 3 years ago
comment:20

Clean merge with current develop

New commits:

ec7977bMerge tag '9.3.rc3' into t/27364/poly-times-vector
mkoeppe commented 3 years ago

Changed commit from 0249494 to ec7977b

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from ec7977b to a5fd62d

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

a5fd62dsrc/sage/rings/polynomial/multi_polynomial_ring.py: Remove commented-out code
mkoeppe commented 3 years ago
comment:22

Replying to @videlec:

As far as I understand, zero and one are already cached from sage/rings/rings.py

sage: R = QQ['x','y']
sage: R.zero() is R.zero()
True
sage: R.one() is R.one()
True

Nevertheless, this code for caching 0 and 1 does make things a bit faster. On my machine, %time R.gen(0) + S.gen(0) gives 9.6 s, but taking out the caching it's 12.6 s.

mkoeppe commented 3 years ago

Changed dependencies from #25558 to none

mkoeppe commented 3 years ago

Reviewer: Matthias Koeppe, ...

videlec commented 3 years ago
comment:25

There are several doctest failures. Among them we see that the pushout wrongly changes some Univariate to Multivariate.

File "src/sage/categories/pushout.py", line 3772, in sage.categories.pushout.pushout
Failed example:
    pushout(ZZ['x,y,z'], Frac(ZZ['x'])['y'])
Expected:
    Multivariate Polynomial Ring in y, z over Fraction Field of Univariate Polynomial Ring in x over Integer Ring
Got:
    Multivariate Polynomial Ring in y, z over Fraction Field of Multivariate Polynomial Ring in x over Integer Ring

Above the action of ZZ[x,y,z] on ZZ(x)[y] is ZZ(x)[y,z] in both situations. However, I think that the ZZ(x) must not change. It would be good to test this pushout with ZZ(x) in different forms

In this second example it is unclear what is best.

File "src/sage/categories/pushout.py", line 3778, in sage.categories.pushout.pushout
Failed example:
    pushout(QQ['x,y'], ZZ[['x']])
Expected:
    Univariate Polynomial Ring in y over Power Series Ring in x over Rational Field
Got:
    Multivariate Polynomial Ring in y over Power Series Ring in x over Rational Field

The action of QQ[x,y] on ZZ[[x]] does correctly produce QQ[y][[x]] in both situations. Since QQ[x,y] -> QQ[y] drops a variable it is unclear to me if there is a best answer.

videlec commented 3 years ago
comment:26

Related: it is desirable that the string representation of multivariate polynomial rings make visible the implementation. Currently we have

sage: PolynomialRing(ZZ, ['x', 'y'], 2, implementation='generic')
Multivariate Polynomial Ring in x, y over Integer Ring
sage: PolynomialRing(ZZ, ['x', 'y'], 2, implementation='singular')
Multivariate Polynomial Ring in x, y over Integer Ring

But it would be better as

sage: PolynomialRing(ZZ, ['x', 'y'], 2, implementation='generic')
Multivariate Polynomial Ring in x, y over Integer Ring (using generic implementation)
sage: PolynomialRing(ZZ, ['x', 'y'], 2, implementation='singular')
Multivariate Polynomial Ring in x, y over Integer Ring

Ideally (as for univariate polynomials and matrices) the default implementation would show nothing.

videlec commented 3 years ago
comment:27

The construction functor should take into account the implementation. Please fix and add the doctest

sage: TT = PolynomialRing(QQ, 't', 2, implementation='generic')
sage: F, R = TT.construction()
sage: F(R) is TT  # bug: returns False
True
videlec commented 3 years ago
comment:28

The construction is similarly broken on univariate polynomials

sage: T = PolynomialRing(ZZ, 'x')
sage: F, R = T.construction()
sage: F(R) is T
True
sage: T = PolynomialRing(ZZ, 'x', implementation='NTL')
sage: F, R = T.construction()
sage: F(R) is T  # bug: returns False
True
mkoeppe commented 3 years ago
comment:29

31668 is adding lots of these tests via the _test_construction method.

videlec commented 3 years ago
comment:30

Replying to @mkoeppe:

31668 is adding lots of these tests via the _test_construction method.

nice!

mkoeppe commented 3 years ago
comment:32

Setting a new milestone for this ticket based on a cursory review.

dkrenn commented 1 year ago

Bug still in 10.0. Seems that a branch has prepared on trac over two years ago and reviewing was done. What is the state of the fix?