nth_root for (Laurent) power series

[sagetrac-pernici]

There is a nth_root method defined on univariate polynomial (via Newton method)

sage: R.<x> = QQ[]
sage: ((1 + x - x^2)**5).nth_root(5)
-x^2 + x + 1

We provide a more general implementation in a new method _nth_root_series that compute the series expansion of the n-th root for univariate polynomials. Using it we implement straightforward nth_root for univariate (Laurent) power series.

This branch will not consider support for extend=True (see this sage-devel thread). When extend=True the method will simply raise a NotImplementedError while waiting for Puiseux series in Sage (see #4618).

On multi-variate polynomials there is also a nth_root method but which is implemented via factorization (sic)! The multivariate case should just call the univariate case with appropriate variable ordering. This will be dealt with in another ticket.

CC: @robertwb @bgrenet

Component: commutative algebra

Keywords: power series

Author: Mario Pernici, Vincent Delecroix

Branch/Commit: eddd45d

Reviewer: Sébastien Labbé

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

[sagetrac-pernici]

Attachment: trac_10720_power_series_nth_root.patch.gz

[sagetrac-pernici]

Changed keywords from none to power series

[sagetrac-pernici]

Author: mario pernici

[sagetrac-pernici]

Attachment: trac_10720_power_series_nth_root_2.patch.gz

[sagetrac-pernici]

comment:3

The nth-root of power series y = x^n is computed using
the Newton method for y = x^-n

x' = (1+1/n)*x - y*x^(n+1)/n

sage: R.<t> = QQ[]
sage: p = (1 + 2*t + 5*t^2 + 7*t^3 + O(t^4))^3
sage: p.nth_root(3)
1 + 2*t + 5*t^2 + 7*t^3 + O(t^4)
sage: p = (1 + 2*t + 5*t^2 + 7*t^3 + O(t^4))^-3
sage: p.nth_root(-3)
1 + 2*t + 5*t^2 + 7*t^3 + O(t^4)

With this patch nth_root works also for series on ZZ

sage: R.<t> = ZZ[[]]
sage: p = 1 + 4*t^2 + 3*t^3 + O(t^4)
sage: p.nth_root(2)
1 + 2*t^2 + 3/2*t^3 + O(t^4)
sage: p.sqrt(2)
1 + 2*t^2 + 3/2*t^3 + O(t^4)
sage: p.nth_root(3)
1 + 4/3*t^2 + t^3 + O(t^4)
sage: p = 4*t^2 + 3*t^3 + O(t^4)
sage: p.nth_root(2)
2*t + 3/4*t^2 + O(t^3)
sage: p.sqrt(2)
Traceback (most recent call last):
...
TypeError: no conversion of this rational to integer

there is a bug in sqrt in this case.

nth_root can be used to compute the square root of series which
currently sqrt does not support

sage: R.<x,y> = QQ[]
sage: S.<t> = R[[]]
sage: p = 4 + t*x + t^2*y + O(t^3)
sage: p.nth_root(2)
2 + 1/4*x*t + (-1/64*x^2 + 1/4*y)*t^2 + O(t^3)
sage: p = 32*t^5 + x*t^6 + y*t^7 + O(t^8)
sage: p.nth_root(5)
2*t + 1/80*x*t^2 + (-1/6400*x^2 + 1/80*y)*t^3 + O(t^4)
sage: p.sqrt()
Traceback (most recent call last):
...
AttributeError: 'sage.rings.polynomial.multi_polynomial_libsingular.MPolynomial_libsingular' object has no attribute 'sqrt'

nth-root iteration formula is division-free, which is convenient in this
case; in this case sqrt could call nth_root.

nth_root can be used in the multivariate series considered
in ticket #1956 .

[sagetrac-pernici]

comment:4

in the above message there is a wrong example on where sqrt fails;
here is the corrected example

sage: R.<x,y> = QQ[]
sage: S.<t> = R[[]]
sage: p = 4 + t*x + t^2*y + O(t^3)
sage: p.nth_root(2)
2 + 1/4*x*t + (-1/64*x^2 + 1/4*y)*t^2 + O(t^3)
sage: p.sqrt()
Traceback (most recent call last):
...
AttributeError: 'sage.rings.polynomial.multi_polynomial_libsingular.MPolynomial_libsingular' object has no attribute 'sqrt'
}

[robertwb]

comment:6

Apply only trac_10720_power_series_nth_root_2.patch

[sagetrac-pernici]

comment:7

Attachment: trac_10720_power_series_nth_root_3.patch.gz

With trac_10720_power_series_nth_root_3.patch nth_root is much faster for n large

sage: S.<t> = QQ[[]]
sage: p = t.exp(30)
sage: %time p1 = p.nth_root(1000)
Wall time: 0.01 s

with the previous version it takes 84s

[sagetrac-pernici]

Attachment: trac_10720_power_series_nth_root_4.patch.gz

[sagetrac-pernici]

comment:8

With trac_10720_power_series_nth_root_4.patch
nth_root and inversion become faster for series on
polynomial rings, when used together with
trac_10480_fast_PowerSeries_poly_multiplication-alternative.patch
from ticket #10480 (otherwise these functions perform as without the patch).

In the following benchmarks apply
trac_karatsuba_improvements.patch and
trac_10480_fast_PowerSeries_poly_multiplication-alternative.patch,
trac_10720_power_series_nth_root_2.patch and
trac_10720_power_series_nth_root_3.patch;
in (2) apply also the new patch

sage: N = 2
sage: R= PolynomialRing(QQ,N,'x')
sage: x = R.gens()
sage: S.<t> = R[[]]
sage: sx = sum(x)
sage: prec = 15
sage: p = (t.exp(prec)).subs({t:t*sx})
sage: %time p1 = p^-1
sage: %time p1 = p.nth_root(2)

Inversion benchmark:

N  prec  (1)    (2)
2  15    0.06   0.01
3  15    2.1    0.07
4  15    58     0.5
5  15    1440   3.4

Square root benchmark:

N  prec  (1)    (2)
2  15    0.15   0.03
3  15    5.2    0.31
4  15    161    3.3

The speedup is large because the terms with high degree in t
are large polynomials, due to the combinatorial
possibilities with several variables; using _mul_ instead of _mul_trunc
several products involving these large polynomials are computed and
later truncated away.

[sagetrac-johanbosman]

comment:10

This is an enhancement rather than a defect.

[vbraun]

comment:11

Which patches need to be applied? Please put some information in the ticket description.

If trac_10720_power_series_nth_root_3.patch is meant to be applied, please add a doctest to __pow_trunc.

[saraedum]

comment:13

As Volker mentioned, __pow_trunc lacks a docstring. (Just to remove this from the list of tickets needing review until that is fixed.)

[sagetrac-git]

Changed commit from 1c3d038 to 2e432e1

[sagetrac-git]

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

2e432e1

10720: use Newton method for x^-n instead

[videlec]

comment:35

It is indeed better

sage: S.<t> = QQ[[]]
sage: p = t.exp(30)
sage: %time p1 = p.nth_root(1000)
CPU times: user 3.8 ms, sys: 30 µs, total: 3.83 ms
Wall time: 3.69 ms

[videlec]

comment:36

Replying to @fchapoton:

One related remark:

Thanks to ticket #14115, it is now easy to implement a general rational power by

def rational_power(f,alpha):
    return (f.log()*alpha).exp()

I do not know how it compares in terms of speed with the method of this ticket.

sage: R.<x> = PowerSeriesRing(QQ, default_prec=100)
sage: p = (1 + 2*x - x^4)**200
sage: %timeit p1 = p.nth_root(1000)
100 loops, best of 3: 4.18 ms per loop
sage: %timeit p2 = (p.log()/1000).exp()
100 loops, best of 3: 5.84 ms per loop

But the main advantage of the method proposed here is that it works in positive characteristic.

[sagetrac-git]

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

bcade8a

10720: more examples

[sagetrac-git]

Changed commit from 2e432e1 to bcade8a

[videlec]

Changed author from Vincent Delecroix to Mario Pernici, Vincent Delecroix

[seblabbe]

comment:39

1. def _nth_root_series(self, long n, long prec, start=None): is missing a INPUT block, in which, in particular, the goal of input start should be explained.

2. At two places the input block says - ``prec`` -- integer (optional) - precision of the result, but the code does prec = min(self.prec(), prec). I suggest to add a sentence advertising it saying something like If prec is larger than self.prec(), then self.prec() is used.

[seblabbe]

comment:40

3. Check that the result are consistent -> results

[seblabbe]

Reviewer: Sébastien Labbé

[seblabbe]

comment:41

Once, those three changes on the documentation aspect are done, feel free to change the status to positive review on my behalf.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

0d7545d	10720: _nth_root_series for univariate polynomials
fc2bb60	10720: nth_root for (Laurent) power series
c83d4c7	10720: use Newton method for x^-n instead
3a5d992	10720: more examples
eddd45d	10720: doc fixes

[sagetrac-git]

Changed commit from bcade8a to eddd45d

[videlec]

comment:43

rebased and fixed. I am only setting to needs review to have some patchbot reviews.

[videlec]

comment:44

Merci Sébastien!

[vbraun]

Changed branch from u/vdelecroix/10720 to eddd45d