Opened 9 years ago

Closed 7 years ago

#9220 closed defect (fixed)

Unpredictable parent for polynomial evaluation

Reported by: nbruin Owned by: robertwb
Priority: major Milestone: sage-5.7
Component: coercion Keywords:
Cc: Merged in: sage-5.7.beta3
Authors: Nils Bruin, Robert Bradshaw Reviewers: Tom Boothby
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by tscrim)

I doubt that it is intended that the names of the variables of a polynomial ring can affect the parent of the result of evaluating such a polynomial:

sage: R=QQ['x']
sage: S=QQ['x','y']
sage: h=S.0^2
sage: parent(h(R.0,0))
Multivariate Polynomial Ring in x, y over Rational Field

sage: R=QQ['x']
sage: S=QQ['u','v']
sage: h=S.0^2
sage: parent(h(R.0,0))
Univariate Polynomial Ring in x over Rational Field 

I would expect the result of the second example in both cases.

In

http://groups.google.com/group/sage-devel/browse_thread/thread/4607f62126303ddd?pli=1

John Cremona mentions #8502 as fixing a different but similar issue.


Apply:

9220-poly-evaluation-coerce-5.4.rebase.patch trac_9220-poly_evaluation-review-ts.patch

Attachments (4)

9220-poly-evaluation-coerce.patch (5.8 KB) - added by robertwb 9 years ago.
add instead of previous
9220-poly-evaluation-coerce-5.4.rebase.patch (5.7 KB) - added by robertwb 7 years ago.
Rebased on sage-5.4.rc2, apply only this patch.
13933-doctests.patch (3.5 KB) - added by robertwb 7 years ago.
minor docstring fixes
trac_9220-poly_evaluation-review-ts.patch (1.7 KB) - added by tscrim 7 years ago.
Minor fixes to docstrings

Download all attachments as: .zip

Change History (21)

comment:1 Changed 9 years ago by robertwb

I agree, the result should only be a function of the base ring and evaluation argument parents.

comment:2 follow-up: Changed 9 years ago by nbruin

I think I've found the culprit in:

built-in method __call__ of sage.rings.polynomial.multi_polynomial_libsingular.MPolynomial_libsingular

Indeed, it tries to coerce the evaluation values into the polynomial ring. Perhaps it should try to coerce into the base ring of the parent instead?

        if l != parent._ring.N:
            raise TypeError, "number of arguments does not match number of variables in parent"

        try:
            x = [parent._coerce_c(e) for e in x]
        except TypeError:
            # give up, evaluate functional
            y = parent.base_ring()(0)
            for (m,c) in self.dict().iteritems():
                y += c*mul([ x[i]**m[i] for i in m.nonzero_positions()])
            return y

If I were to fix this code, I'd simply always do the code under the "except", but someone probably had a good reason for doing it the way it's done. Probably because singular_polynomial_call is more efficient? I see several options:

  • Ask the coercion system for a common overring of the base ring of parent and all the parents of x. If that is parent, then coerce and use singular_polynomial_call. Otherwise just multiply out manually.
  • see if the parent of all members of x is equal to parent (due to the lax coercion rules, *coercible into* isn't good enough)
  • just always evaluate by multiplying out

The first one is the "proper" one in that it uses the coercion system to figure out if a more efficient option is available. The second option should be cheap and catch the case where most speed-up should be attainable. The third option wouldn't waste any time on checking parents, but would need coercion calls for each coefficient-monomial multiplication.

comment:3 in reply to: ↑ 2 Changed 9 years ago by nbruin

Indeed the present code does seem to address real overhead:

sage: R=QQ['x']
sage: S=QQ['x','y']
sage: h=S.0^2
sage: timeit('h(R.0,0)')
625 loops, best of 3: 269 µs per loop

but

sage: R=QQ['x']
sage: S=QQ['u','v']
sage: h=S.0^2
sage: timeit('h(R.0,0)')
625 loops, best of 3: 523 µs per loop

so option one or two above is probably the proper one.

comment:4 Changed 9 years ago by nbruin

  • Authors set to Nils Bruin
  • Status changed from new to needs_review

comment:5 Changed 9 years ago by nbruin

Attached patch is efficient when evaluation point has the same parent. I guess previously some efficiency was gained when a point was in the base ring as well (the result was subsequently recognised as a constant and coerced back?) by used libsingular evaluation directly. This is lost with attached patch. This probably means that this patch solves #8502 independently as well.

To reviewer or merger: feel free to change patch. I won't be touching the code anymore.

Changed 9 years ago by robertwb

add instead of previous

comment:6 Changed 9 years ago by robertwb

I've attached a patch that returns the correct parent without sacrificing the singular efficiency (together with a utility method in the coercion model to make this kind of thing easier elsewhere).

comment:7 Changed 9 years ago by robertwb

Apply only 9220-poly-evaluation-coerce.patch

comment:8 Changed 8 years ago by boothby

  • Status changed from needs_review to positive_review

Works with 4.7.1.

comment:9 Changed 8 years ago by boothby

  • Reviewers set to boothby

comment:10 Changed 8 years ago by davidloeffler

  • Summary changed from Upredictable parent for polynomial evaluation to Unpredictable parent for polynomial evaluation

comment:11 Changed 8 years ago by jdemeyer

  • Reviewers changed from boothby to Tom Boothby
  • Status changed from positive_review to needs_work

Needs to be rebased to sage-5.0.beta11:

applying 9220-poly-evaluation-coerce.patch
patching file sage/rings/polynomial/multi_polynomial_libsingular.pyx
Hunk #2 succeeded at 4512 with fuzz 2 (offset 2764 lines).
Hunk #4 FAILED at 1785
1 out of 4 hunks FAILED -- saving rejects to file sage/rings/polynomial/multi_polynomial_libsingular.pyx.rej
patch failed, unable to continue (try -v)
patch failed, rejects left in working dir
errors during apply, please fix and refresh 9220-poly-evaluation-coerce.patch

Changed 7 years ago by robertwb

Rebased on sage-5.4.rc2, apply only this patch.

comment:12 Changed 7 years ago by robertwb

  • Authors changed from Nils Bruin to Nils Bruin, Robert Bradshaw
  • Status changed from needs_work to needs_review

comment:13 Changed 7 years ago by tscrim

Some docstring things:

  • Please use auto-trac linking :trac:`9220`
  • For common_parent(), I would recommend:
    Computes a common parent for all the inputs.
    
    This is essentially an `n`-ary canonical coercion except it
    can operate on parents rather than just elements. 
    
    INPUT: 
    
    - ``args`` -- a set of elements and/or parents
    
    OUTPUT: 
    
    A :class:`Parent` into which each input should coerce, or raises a 
    ``TypeError`` if no such :class:`Parent` can be found. 
    
    In particular, there is should not be an indent on the INPUT: and OUTPUT: blocks.

Thanks,
Travis

Last edited 7 years ago by tscrim (previous) (diff)

comment:14 Changed 7 years ago by tscrim

  • Status changed from needs_review to needs_work
  • Work issues set to docstrings

Changed 7 years ago by robertwb

minor docstring fixes

comment:15 Changed 7 years ago by robertwb

  • Status changed from needs_work to needs_review

Changed 7 years ago by tscrim

Minor fixes to docstrings

comment:16 Changed 7 years ago by tscrim

  • Description modified (diff)
  • Status changed from needs_review to positive_review
  • Work issues docstrings deleted

The rebased version worked for me. I've attached a small reviewer patch which just does the minor tweaks to the docstrings. Jeroen, I hope you don't mind me setting this back to a positive review.

Best,
Travis

For patchbot:

Apply only: 9220-poly-evaluation-coerce-5.4.rebase.patch, trac_9220-poly_evaluation-review-ts.patch

comment:17 Changed 7 years ago by jdemeyer

  • Merged in set to sage-5.7.beta3
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.