#20571: Newton method for nth_root of polynomial
-------------------------------------+-------------------------------------
Reporter: vdelecroix | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-7.3
Component: algebra | Resolution:
Keywords: | Merged in:
Authors: Vincent Delecroix | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/vdelecroix/20571 | 530a5639eb44d9f6feccb1b4d382ca356faf3146
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Description changed by vdelecroix:
Old description:
> We can use Newton method to compute n-th root of polynomials.
>
> It is faster than factorization even over ZZ where factor is highly
> optimized:
> {{{
> sage: x = polygen(ZZ)
> sage: p = x**14 + x**3 - 12
>
> sage: q = p**13
> sage: %timeit _ = q.nth_root(13)
> 1000 loops, best of 3: 416 µs per loop
> sage: %timeit _ = q.factor()
> 1000 loops, best of 3: 895 µs per loop
>
> sage: q = p**37
> sage: %timeit _ = q.nth_root(37)
> 1000 loops, best of 3: 1.17 µs per loop
> sage: %timeit _ = q.factor()
> 100 loops, best of 3: 3.92 ms per loop
> }}}
> And the Newton method also works over polynomial when factorization is
> not implemented
> {{{
> sage: R1.<x> = QQ[]
> sage: R2.<y> = R1[]
> sage: R3.<z> = R2[]
> sage: q = (x+y+z)**3
> sage: q.factor()
> Traceback (most recent call last):
> ...
> NotImplementedError:
> sage: q.nth_root(3)
> z + y + x
> }}}
New description:
In #20086 a `nth_root` method for polynomial was implemented using
factorization. But we can use Newton method for that!
It is faster than factorization even over ZZ where factor is highly
optimized:
{{{
sage: x = polygen(ZZ)
sage: p = x**14 + x**3 - 12
sage: q = p**13
sage: %timeit _ = q.nth_root(13)
1000 loops, best of 3: 416 µs per loop
sage: %timeit _ = q.factor()
1000 loops, best of 3: 895 µs per loop
sage: q = p**37
sage: %timeit _ = q.nth_root(37)
1000 loops, best of 3: 1.17 µs per loop
sage: %timeit _ = q.factor()
100 loops, best of 3: 3.92 ms per loop
}}}
And the Newton method also works over polynomial when factorization is not
implemented
{{{
sage: R1.<x> = QQ[]
sage: R2.<y> = R1[]
sage: R3.<z> = R2[]
sage: q = (x+y+z)**3
sage: q.factor()
Traceback (most recent call last):
...
NotImplementedError:
sage: q.nth_root(3)
z + y + x
}}}
--
--
Ticket URL: <http://trac.sagemath.org/ticket/20571#comment:8>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
