{"action":"created","issue":{"url":"https://api.github.com/repos/sympy/sympy/issues/9366","labels_url":"https://api.github.com/repos/sympy/sympy/issues/9366/labels{/name}","comments_url":"https://api.github.com/repos/sympy/sympy/issues/9366/comments","events_url":"https://api.github.com/repos/sympy/sympy/issues/9366/events","html_url":"https://github.com/sympy/sympy/issues/9366","id":72683308,"number":9366,"title":"rootof: Constructing RootOfs with polys containing RootOf coefficients","user":{"login":"cswiercz","id":915840,"avatar_url":"https://avatars.githubusercontent.com/u/915840?v=3","gravatar_id":"","url":"https://api.github.com/users/cswiercz","html_url":"https://github.com/cswiercz","followers_url":"https://api.github.com/users/cswiercz/followers","following_url":"https://api.github.com/users/cswiercz/following{/other_user}","gists_url":"https://api.github.com/users/cswiercz/gists{/gist_id}","starred_url":"https://api.github.com/users/cswiercz/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/cswiercz/subscriptions","organizations_url":"https://api.github.com/users/cswiercz/orgs","repos_url":"https://api.github.com/users/cswiercz/repos","events_url":"https://api.github.com/users/cswiercz/events{/privacy}","received_events_url":"https://api.github.com/users/cswiercz/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":8,"created_at":"2015-05-02T19:02:47Z","updated_at":"2015-06-02T23:12:44Z","closed_at":null,"body":"This is a feature request to make it possible to construct `RootOf`s containing `RootOf`s like so:\r\n\r\n```python\r\nfrom sympy import Poly, RootOf\r\nfrom sympy.abc import x,y\r\n\r\naroot = RootOf(x**7 + x + 1, 0, radicals=False)\r\np = RootOf(y**2 - aroot, 0, radicals=False)\r\n```\r\n\r\nI did a little investigating of my own to see what is preventing the current implementation from supporting this. Here's what I've done so far. It's incredible naive but since I'm unfamiliar with the internals of Sympy domains it's the best I can do at the moment. I would be happy to do what I can to make this work. It would be a humungous benefit to my own project!\r\n\r\n1. When running the code above we get a `NotImplementedError` during construction of the `RootOf` object. I didn't see where in [`RootOf.__new__`](https://github.com/sympy/sympy/blob/master/sympy/polys/rootoftools.py#L54) why this is an issue so I started by commenting out [Lines 97-98](https://github.com/sympy/sympy/blob/master/sympy/polys/rootoftools.py#L97) from `rootoftools.py` just to see what would happen.\r\n\r\n  ```\r\n  if not dom.is_ZZ:                                                                                                                                              \r\n      raise NotImplementedError(\"RootOf is not supported over %s\" % dom)                                                                                         \r\n  ```\r\n\r\n2. Executing the example again brought us to a `DomainError` while trying to compute the isolating intervals of the root. In particular, [`RootOf._get_reals_sqf`](https://github.com/sympy/sympy/blob/master/sympy/polys/rootoftools.py#L152) makes a call to [`rootofisolation.dup_isolate_real_roots_sqf`](https://github.com/sympy/sympy/blob/master/sympy/polys/rootisolation.py#L490) with the following arguments:\r\n  * `f = [EX(1), EX(0), EX(-RootOf(x**7 + x + 1, 0))]`\r\n  * `K = EX`\r\n  * `eps, inf, sup = None`,\r\n  * `basis = False`\r\n  * `fast = True`\r\n\r\n  The error is raised on [Lines 503-504](https://github.com/sympy/sympy/blob/master/sympy/polys/rootisolation.py#L503) because `EX` is not `ZZ`. See [Trace 1] below for the stack trace. So, continuing this line of inquiry I commented out those lines.\r\n\r\n3. What follows next is beyond my immediate understanding. I suggest taking at look at [Trace 2] below but from what little I understand it looks like an error occurs in trying to coerce some input values to [`_mobius_to_interval`](https://github.com/sympy/sympy/blob/master/sympy/polys/rootisolation.py#L144) to the field `EX`. In this case, the inputs to this function are\r\n  * `M = (EX(0), EX(1), EX(1), EX(1))`\r\n  * `field = EX`\r\n\r\n  The error occurs when trying to execute `EX(M[0],M[2])`. A full trace is below at [Trace 2].\r\n\r\nAt this point I stopped because I don't know enough about the inner workings of domains to make any decent judgements. If anyone would like to play around I [created a branch](https://github.com/cswiercz/sympy/tree/rootofrootof) with the above two sections commented out. Again, I would be happy to work with someone more qualified to get this working!\r\n\r\n[Trace 1] After First Commenting\r\n--------------------------------------------\r\n\r\n```\r\n---------------------------------------------------------------------------\r\nDomainError                               Traceback (most recent call last)\r\n<ipython-input-4-cc81d1e3e947> in <module>()\r\n      1 get_ipython().magic(u'pdb 0')\r\n      2 \r\n----> 3 p = RootOf(y**2 - r, 0, radicals=False)\r\n      4 print p\r\n\r\n/Users/cswiercz/.local/lib/python2.7/site-packages/sympy-0.7.7.dev0-py2.7.egg/sympy/polys/rootoftools.pyc in __new__(cls, f, x, index, radicals, expand)\r\n     98         #     raise NotImplementedError(\"RootOf is not supported over %s\" % dom)\r\n     99 \r\n--> 100         root = cls._indexed_root(poly, index)\r\n    101         return coeff*cls._postprocess_root(root, radicals)\r\n    102 \r\n\r\n/Users/cswiercz/.local/lib/python2.7/site-packages/sympy-0.7.7.dev0-py2.7.egg/sympy/polys/rootoftools.pyc in _indexed_root(cls, poly, index)\r\n    406         (_, factors) = poly.factor_list()\r\n    407 \r\n--> 408         reals = cls._get_reals(factors)\r\n    409         reals_count = cls._count_roots(reals)\r\n    410 \r\n\r\n/Users/cswiercz/.local/lib/python2.7/site-packages/sympy-0.7.7.dev0-py2.7.egg/sympy/polys/rootoftools.pyc in _get_reals(cls, factors)\r\n    178 \r\n    179         for factor, k in factors:\r\n--> 180             real_part = cls._get_reals_sqf(factor)\r\n    181             reals.extend([ (root, factor, k) for root in real_part ])\r\n    182 \r\n\r\n/Users/cswiercz/.local/lib/python2.7/site-packages/sympy-0.7.7.dev0-py2.7.egg/sympy/polys/rootoftools.pyc in _get_reals_sqf(cls, factor)\r\n    157             _reals_cache[factor] = real_part = \\\r\n    158                 dup_isolate_real_roots_sqf(\r\n--> 159                     factor.rep.rep, factor.rep.dom, blackbox=True)\r\n    160 \r\n    161         return real_part\r\n\r\n/Users/cswiercz/.local/lib/python2.7/site-packages/sympy-0.7.7.dev0-py2.7.egg/sympy/polys/rootisolation.pyc in dup_isolate_real_roots_sqf(f, K, eps, inf, sup, fast, blackbox)\r\n    502         (_, f), K = dup_clear_denoms(f, K, convert=True), K.get_ring()\r\n    503     elif not K.is_ZZ:\r\n--> 504         raise DomainError(\"isolation of real roots not supported over %s\" % K)\r\n    505 \r\n    506     if dup_degree(f) <= 0:\r\n\r\nDomainError: isolation of real roots not supported over EX\r\n```\r\n\r\n[Trace 2] After Second Commenting\r\n-------------------------------------------------\r\n\r\n```\r\n---------------------------------------------------------------------------\r\nTypeError                                 Traceback (most recent call last)\r\n<ipython-input-4-f3b6aafd55bc> in <module>()\r\n      1 get_ipython().magic(u'pdb 1')\r\n      2 \r\n----> 3 p = RootOf(y**2 - r, 0, radicals=False)\r\n      4 print p\r\n\r\n/Users/cswiercz/.local/lib/python2.7/site-packages/sympy-0.7.7.dev0-py2.7.egg/sympy/polys/rootoftools.pyc in __new__(cls, f, x, index, radicals, expand)\r\n     98         #     raise NotImplementedError(\"RootOf is not supported over %s\" % dom)\r\n     99 \r\n--> 100         root = cls._indexed_root(poly, index)\r\n    101         return coeff*cls._postprocess_root(root, radicals)\r\n    102 \r\n\r\n/Users/cswiercz/.local/lib/python2.7/site-packages/sympy-0.7.7.dev0-py2.7.egg/sympy/polys/rootoftools.pyc in _indexed_root(cls, poly, index)\r\n    406         (_, factors) = poly.factor_list()\r\n    407 \r\n--> 408         reals = cls._get_reals(factors)\r\n    409         reals_count = cls._count_roots(reals)\r\n    410 \r\n\r\n/Users/cswiercz/.local/lib/python2.7/site-packages/sympy-0.7.7.dev0-py2.7.egg/sympy/polys/rootoftools.pyc in _get_reals(cls, factors)\r\n    178 \r\n    179         for factor, k in factors:\r\n--> 180             real_part = cls._get_reals_sqf(factor)\r\n    181             reals.extend([ (root, factor, k) for root in real_part ])\r\n    182 \r\n\r\n/Users/cswiercz/.local/lib/python2.7/site-packages/sympy-0.7.7.dev0-py2.7.egg/sympy/polys/rootoftools.pyc in _get_reals_sqf(cls, factor)\r\n    157             _reals_cache[factor] = real_part = \\\r\n    158                 dup_isolate_real_roots_sqf(\r\n--> 159                     factor.rep.rep, factor.rep.dom, blackbox=True)\r\n    160 \r\n    161         return real_part\r\n\r\n/Users/cswiercz/.local/lib/python2.7/site-packages/sympy-0.7.7.dev0-py2.7.egg/sympy/polys/rootisolation.pyc in dup_isolate_real_roots_sqf(f, K, eps, inf, sup, fast, blackbox)\r\n    509     I_zero, f = _isolate_zero(f, K, inf, sup, basis=False, sqf=True)\r\n    510 \r\n--> 511     I_neg = dup_inner_isolate_negative_roots(f, K, eps=eps, inf=inf, sup=sup, fast=fast)\r\n    512     I_pos = dup_inner_isolate_positive_roots(f, K, eps=eps, inf=inf, sup=sup, fast=fast)\r\n    513 \r\n\r\n/Users/cswiercz/.local/lib/python2.7/site-packages/sympy-0.7.7.dev0-py2.7.egg/sympy/polys/rootisolation.pyc in dup_inner_isolate_negative_roots(f, K, inf, sup, eps, fast, mobius)\r\n    463     elif not mobius:\r\n    464         for f, M in roots:\r\n--> 465             u, v = _mobius_to_interval(M, F)\r\n    466             results.append((-v, -u))\r\n    467     else:\r\n\r\n/Users/cswiercz/.local/lib/python2.7/site-packages/sympy-0.7.7.dev0-py2.7.egg/sympy/polys/rootisolation.pyc in _mobius_to_interval(M, field)\r\n    146     a, b, c, d = M\r\n    147 \r\n--> 148     s, t = field(a, c), field(b, d)\r\n    149 \r\n    150     if s <= t:\r\n\r\n/Users/cswiercz/.local/lib/python2.7/site-packages/sympy-0.7.7.dev0-py2.7.egg/sympy/polys/domains/domain.pyc in __call__(self, *args)\r\n     70     def __call__(self, *args):\r\n     71         \"\"\"Construct an element of ``self`` domain from ``args``. \"\"\"\r\n---> 72         return self.new(*args)\r\n     73 \r\n     74     def normal(self, *args):\r\n\r\n/Users/cswiercz/.local/lib/python2.7/site-packages/sympy-0.7.7.dev0-py2.7.egg/sympy/polys/domains/domain.pyc in new(self, *args)\r\n     62 \r\n     63     def new(self, *args):\r\n---> 64         return self.dtype(*args)\r\n     65 \r\n     66     @property\r\n\r\nTypeError: __init__() takes exactly 2 arguments (3 given)\r\n```"},"comment":{"url":"https://api.github.com/repos/sympy/sympy/issues/comments/108125839","html_url":"https://github.com/sympy/sympy/issues/9366#issuecomment-108125839","issue_url":"https://api.github.com/repos/sympy/sympy/issues/9366","id":108125839,"user":{"login":"cswiercz","id":915840,"avatar_url":"https://avatars.githubusercontent.com/u/915840?v=3","gravatar_id":"","url":"https://api.github.com/users/cswiercz","html_url":"https://github.com/cswiercz","followers_url":"https://api.github.com/users/cswiercz/followers","following_url":"https://api.github.com/users/cswiercz/following{/other_user}","gists_url":"https://api.github.com/users/cswiercz/gists{/gist_id}","starred_url":"https://api.github.com/users/cswiercz/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/cswiercz/subscriptions","organizations_url":"https://api.github.com/users/cswiercz/orgs","repos_url":"https://api.github.com/users/cswiercz/repos","events_url":"https://api.github.com/users/cswiercz/events{/privacy}","received_events_url":"https://api.github.com/users/cswiercz/received_events","type":"User","site_admin":false},"created_at":"2015-06-02T23:12:44Z","updated_at":"2015-06-02T23:12:44Z","body":"@jksuom I stepped away from this problem for a bit due to thesis work. Now I'm back. Thank you for the responses above.\r\n\r\nThe following is mostly for myself as I think about how to implement this on my own (and want to document my thoughts), but it turns out that Sympy can already determine the norm of `p(t,X)`:\r\n\r\n```python\r\nfrom sympy import Dummy, RootOf, Poly\r\nfrom sympy.abc import x\r\n_x = Dummy(str(x))\r\nt = RootOf(_x**5 + 4*_x + 2, 0)\r\np = Poly(x**4 + t*x + 1, x, extension=t) # or, using \"domain=QQ.algebraic_field(s)\"\r\n\r\nprint p\r\nprint p.domain.is_Algebraic\r\nprint p.sqf_norm()\r\n```\r\n```\r\nPoly(x**4 - RootOf(_x**5 + 4*_x + 2, 0)*x + 1, x, domain='QQ<-RootOf(_x**5 + 4*_x + 2, 0)>')\r\nTrue\r\n(0, Poly(x**4 - RootOf(_x**5 + 4*_x + 2, 0)*x + 1, x, domain='QQ<-RootOf(_x**5 + 4*_x + 2, 0)>'), Poly(x**20 + 5*x**16 + 10*x**12 + 14*x**8 + 2*x**5 + 9*x**4 + 1, x, domain='QQ'))\r\n```\r\n\r\nSo that's nice. (Although, I tried it for the example `f = (x**4 + t*x + 1)**2`, let it run for approximately 30 minutes on my machine, and still hadn't received a result.)\r\n\r\nNow, I need to figure out how to use this norm with the complex root isolation algorithm. From what I understand, the algorithm is based on the [Collins and Krandick](http://dl.acm.org/citation.cfm?id=143308) paper. Perhaps there's a way to modify it..."}}