inverse_series method for polynomials #19005

videlec · 2015-08-09T13:34:50Z

The polynomials in Sage lack many series operation (see #18356 for some motivation). We implement a generic cpdef Polynomial inverse_series(self, long prec) method and specialized ones for polynomials using flint backends.

See also #19006

CC: @sagetrac-pernici @mezzarobba

Component: commutative algebra

Author: Vincent Delecroix

Branch/Commit: 8a09308

Reviewer: Marc Mezzarobba

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

The text was updated successfully, but these errors were encountered:

videlec · 2015-08-09T13:38:18Z

Branch: u/vdelecroix/19005

videlec · 2015-08-09T13:38:18Z

New commits:

`5d2ebb8`	`trac #19005: generic inverse_series`
`40ff24d`	`trac #19005: truncate return self for large precision`
`466fa3c`	`trac #19005: more flint declaration`
`e01540b`	`Trac #19005: specialized inverse_series for flint backends`

videlec · 2015-08-09T13:38:18Z

Commit: e01540b

mezzarobba · 2015-08-18T15:01:05Z

comment:3

Hi Vincent,

Could you please explain why you'd like to have these features as methods of polynomial objects rather than power series objects? Thanks!

videlec · 2015-08-18T15:41:57Z

comment:4

Hi Marc,

Replying to @mezzarobba:

Could you please explain why you'd like to have these features as methods of polynomial objects rather than power series objects? Thanks!

A power series just wraps a polynomial. So it would be better to have specialized algorithms for polynomials and wrap them at the power series level. Would you prefer one power series element per polynomial class? As soon as this is reviewed, I will change the power series implementation to use this method and it will be much faster. I can do that here if you prefer.
Power series are much slower and involving them in a polynomial algorithm implies a creation of parent (which is damn slow). Moreover you only care about the polynomial at the end. You can have a look at special resultants composed_sum and composed_product #18356 for motivation from this side.

Vincent

mezzarobba · 2015-08-25T10:15:58Z

comment:5

Replying to @videlec:

Could you please explain why you'd like to have these features as methods of polynomial objects rather than power series objects? Thanks!

A power series just wraps a polynomial. So it would be better to have specialized algorithms for polynomials and wrap them at the power series level. Would you prefer one power series element per polynomial class?

No, as long as the methods you are implementing on polynomials are just helpers for generic implementations on power series, I agree. But I wouldn't want to clutter the interface of polynomials with every possible operation on power series, elements of quotients of polynomial rings, etc.

Anyway, this ticket probably wasn't the right place to make this comment, because I agree that inversion modulo x^k is fundamental enough to be part of the interface of polynomials themselves.

Power series are much slower and involving them in a polynomial algorithm implies a creation of parent (which is damn slow).

Well, that's probably something that should be fixed on its own! :-)

mezzarobba · 2015-08-25T11:10:40Z

comment:6

The docstring of inverse_series claims that it works over any ring, but after patching matrix0.pyx to make is_unit synonymous with is_invertible, I get:

sage: R.<x> = MatrixSpace(QQ, 2)[]
sage: pol = R.random_element()
sage: list(pol)
[
[   2    0]  [2 1]  [-1  0]
[-1/2 -1/2], [0 2], [ 2 -2]
]
sage: inv = pol.inverse_series(5)
sage: (inv*pol).truncate(5).degree()
4
sage: (pol*inv).truncate(5).degree()
4

Did you intend it to work over non-commutative rings?

sagetrac-git · 2015-08-26T00:35:18Z

Changed commit from e01540b to 82d2740

sagetrac-git · 2015-08-26T00:35:18Z

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

`e51a669`	`trac #19005: generic inverse_series`
`e594c17`	`trac #19005: truncate return self for large precision`
`ca2ac91`	`trac #19005: more flint declaration`
`4705c72`	`Trac #19005: specialized inverse_series for flint backends`
`740c149`	`Trac 19005: is_unit for matrices`
`82d2740`	`Trac 19005: inverse_series over noncommutative rings`

videlec · 2015-08-26T00:35:45Z

Reviewer: Marc Mezzarobba

sagetrac-git · 2015-08-26T00:43:20Z

Changed commit from 82d2740 to 7e775c5

sagetrac-git · 2015-08-26T00:43:20Z

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

`8098f1a`	`Trac 19005: is_unit for matrices`
`7e775c5`	`Trac 19005: inverse_series over noncommutative rings`

bgrenet · 2015-08-27T09:37:10Z

comment:11

Though I am not definitive on this, I find it weird to have the two distinct methods inverse_mod and inverse_series with p.inverse_series(10) == p.inverse_mod(x^10). Wouldn't it be possible to make your code a special case of inverse_mod, or to make it a hidden function (_inverse_series) which is called as a special case of inverse_mod? Actually, these are two distinct changes I propose, with two distinct reasons:

It would be make inverse_mod faster for monomials:

sage: %timeit p.inverse_series(10)
The slowest run took 24.39 times longer than the fastest. This could mean that an intermediate result is being cached 
100000 loops, best of 3: 1.96 µs per loop
sage: %timeit p.inverse_mod(x^10)
The slowest run took 6.16 times longer than the fastest. This could mean that an intermediate result is being cached 
10000 loops, best of 3: 26.2 µs per loop

The name inverse_series make me think that the result will be a series, so if I want a truncated series (that is a polynomial), I am more naturally inclined to try the inverse_mod method. And I suspect other users may have the same behavior.

videlec · 2015-08-27T23:28:25Z

comment:12

Hi Bruno,

Replying to @bgrenet:

Though I am not definitive on this, I find it weird to have the two distinct methods inverse_mod and inverse_series with p.inverse_series(10) == p.inverse_mod(x^10). Wouldn't it be possible to make your code a special case of inverse_mod, or to make it a hidden function (_inverse_series) which is called as a special case of inverse_mod? Actually, these are two distinct changes I propose, with two distinct reasons:

I definitely do not want to involve a case search to get the inverse series (the calls to isinstance, from sage.rings.ideal import Ideal all the if takes a lot of time). The function inverse_series has type definition in input that will make it efficient in Cython code (e.g. power series). So I am against having it as a special case of inverse_mod. Thoug, if you think it would be interesting you can add a special case to inverse_mod but I am not sure it is worth it. It might be better to just add a SEEALSO in the documentation.

The name inverse_series make me think that the result will be a series, so if I want a truncated series (that is a polynomial), I am more naturally inclined to try the inverse_mod method. And I suspect other users may have the same behavior.

What about truncated_inverse_series or inverse_series_trunc? (there is already a _mul_trunc_).

sagetrac-git · 2015-08-27T23:50:31Z

Changed commit from 7e775c5 to a6c1b39

sagetrac-git · 2015-08-27T23:50:31Z

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

`a6c1b39`	`Trac 19005: fix a doctest`

mezzarobba · 2015-08-28T10:04:59Z

comment:14

Hi Vincent, hi Bruno,

Replying to @videlec:

I definitely do not want to involve a case search to get the inverse series (the calls to isinstance, from sage.rings.ideal import Ideal all the if takes a lot of time). The function inverse_series has type definition in input that will make it efficient in Cython code (e.g. power series). So I am against having it as a special case of inverse_mod. Thoug, if you think it would be interesting you can add a special case to inverse_mod but I am not sure it is worth it. It might be better to just add a SEEALSO in the documentation.

I tend to agree.

The name inverse_series make me think that the result will be a series, so if I want a truncated series (that is a polynomial), I am more naturally inclined to try the inverse_mod method. And I suspect other users may have the same behavior.

What about truncated_inverse_series or inverse_series_trunc? (there is already a _mul_trunc_).

Ore perhaps inverse_mod_xk? I thought about suggesting a different name when I wrote my comments above, but I didn't find anything that I really liked better than inverse_series...

bgrenet · 2015-08-28T14:11:44Z

comment:15

Hi Vincent, hi (again) Marc,

Replying to @mezzarobba:

Hi Vincent, hi Bruno,

Replying to @videlec:

I definitely do not want to involve a case search to get the inverse series (the calls to isinstance, from sage.rings.ideal import Ideal all the if takes a lot of time). The function inverse_series has type definition in input that will make it efficient in Cython code (e.g. power series). So I am against having it as a special case of inverse_mod. Thoug, if you think it would be interesting you can add a special case to inverse_mod but I am not sure it is worth it. It might be better to just add a SEEALSO in the documentation.

I tend to agree.

Well, a SEEALSO looks like a good solution to me also.

The name inverse_series make me think that the result will be a series, so if I want a truncated series (that is a polynomial), I am more naturally inclined to try the inverse_mod method. And I suspect other users may have the same behavior.

What about truncated_inverse_series or inverse_series_trunc? (there is already a _mul_trunc_).

Ore perhaps inverse_mod_xk? I thought about suggesting a different name when I wrote my comments above, but I didn't find anything that I really liked better than inverse_series...

My preferred choice goes to inverse_series_trunc (or inverse_series_truncated if you do not find it too long) since it will easily be found using tabulation and describes well the behavior.

sagetrac-git · 2015-08-29T15:37:52Z

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

`d3ca1db`	`trac #19005: generic inverse_series`
`7636b64`	`trac #19005: truncate return self for large precision`
`2648ba9`	`trac #19005: more flint declaration`
`cd62420`	`Trac #19005: specialized inverse_series for flint backends`
`91337f0`	`Trac 19005: is_unit for matrices`
`e45d880`	`Trac 19005: inverse_series over noncommutative rings`
`1362ca8`	`Trac 19005: fix a doctest`
`7294833`	`Trac 19005: a SEEALSO block`

sagetrac-git · 2015-08-29T15:37:52Z

Changed commit from a6c1b39 to 7294833

sagetrac-git · 2015-08-29T15:52:56Z

Changed commit from 7294833 to d16898a

sagetrac-git · 2015-08-29T15:52:56Z

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

`d16898a`	`19005: inverse_series -> inverse_series_trunc`

videlec · 2015-08-29T15:53:34Z

comment:18

Rebased and updated with your last remarks.

Vincent

mezzarobba · 2015-09-01T18:21:32Z

comment:19

The generic version fails when the truncation order is negative (inconsistency with the others versions) or zero (which is a problem by itself):

sage: (1 + polygen(GF(2))).inverse_series_trunc(0)
...
ValueError: N (=0) must be a positive integer

sage: (1 + polygen(ZZ)).inverse_series_trunc(-1)
0

I believe the doctest in rings.py that you fixed was meant to test the code path resulting in a NotImplementedError.
You may want to change two*current to current + current in the generic implementation? (Not sure if this is a good idea, but it could be much faster for some rings.)
Why the blank line in matrix0.py?
“The method works over any polynomial ring”?

Otherwise looks good to me.

sagetrac-git · 2015-09-01T22:07:00Z

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

`3d1d7c7`	`Trac 19005: is_unit for matrices`
`ced7b03`	`Trac 19005: inverse_series over noncommutative rings`
`74ee015`	`Trac 19005: fix a doctest`
`d30be7a`	`Trac 19005: a SEEALSO block`
`464341f`	`19005: inverse_series -> inverse_series_trunc`
`674a8f8`	`Trac 19005: check that prec is positive`
`3ded62a`	`Trac 19005: on -> over`
`8a09308`	`Trac 19005: two * current -> current + current`

sagetrac-git · 2015-09-01T22:07:00Z

Changed commit from d16898a to 8a09308

videlec · 2015-09-01T22:07:29Z

comment:22

Replying to @mezzarobba:
I fixed everything except

I believe the doctest in rings.py that you fixed was meant to test the code path resulting in a NotImplementedError.

Of course. I will not create a dummy ring just for checking this code path anyway.

Vincent

mezzarobba · 2015-09-02T07:39:09Z

comment:23

Replying to @videlec:

Replying to @mezzarobba:
I fixed everything except

I believe the doctest in rings.py that you fixed was meant to test the code path resulting in a NotImplementedError.

Of course. I will not create a dummy ring just for checking this code path anyway.

Fair enough. But I was wondering why you didn't just remove the test...

vbraun · 2015-09-02T17:25:29Z

Changed branch from u/vdelecroix/19005 to 8a09308

videlec added this to the sage-6.9 milestone Aug 9, 2015

videlec added c: commutative algebra labels Aug 9, 2015

videlec added the s: needs review label Aug 9, 2015

This comment has been minimized.

Sign in to view

mezzarobba added s: needs work and removed s: needs review labels Aug 25, 2015

videlec added s: needs review and removed s: needs work labels Aug 26, 2015

mezzarobba added s: needs work and removed s: needs review labels Sep 1, 2015

videlec added s: needs review and removed s: needs work labels Sep 1, 2015

mezzarobba added s: positive review and removed s: needs review labels Sep 2, 2015

vbraun removed the s: positive review label Sep 2, 2015

vbraun closed this as completed in adb4699 Sep 2, 2015

videlec mentioned this issue Jan 18, 2016

special resultants composed_sum and composed_product #18356

Closed

mezzarobba mentioned this issue Aug 25, 2015

transcendental functions of polynomial #19006

Closed

videlec mentioned this issue Dec 22, 2015

Use inverse_series_trunc in power series #19137

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

inverse_series method for polynomials #19005

inverse_series method for polynomials #19005

videlec commented Aug 9, 2015

videlec commented Aug 9, 2015

videlec commented Aug 9, 2015

videlec commented Aug 9, 2015

This comment has been minimized.

mezzarobba commented Aug 18, 2015

videlec commented Aug 18, 2015

mezzarobba commented Aug 25, 2015

mezzarobba commented Aug 25, 2015

sagetrac-git mannequin commented Aug 26, 2015

sagetrac-git mannequin commented Aug 26, 2015

videlec commented Aug 26, 2015

sagetrac-git mannequin commented Aug 26, 2015

sagetrac-git mannequin commented Aug 26, 2015

bgrenet commented Aug 27, 2015

videlec commented Aug 27, 2015

sagetrac-git mannequin commented Aug 27, 2015

sagetrac-git mannequin commented Aug 27, 2015

mezzarobba commented Aug 28, 2015

bgrenet commented Aug 28, 2015

sagetrac-git mannequin commented Aug 29, 2015

sagetrac-git mannequin commented Aug 29, 2015

sagetrac-git mannequin commented Aug 29, 2015

sagetrac-git mannequin commented Aug 29, 2015

videlec commented Aug 29, 2015

mezzarobba commented Sep 1, 2015

sagetrac-git mannequin commented Sep 1, 2015

sagetrac-git mannequin commented Sep 1, 2015

videlec commented Sep 1, 2015

mezzarobba commented Sep 2, 2015

vbraun commented Sep 2, 2015

inverse_series method for polynomials #19005

inverse_series method for polynomials #19005

Comments

videlec commented Aug 9, 2015

videlec commented Aug 9, 2015

videlec commented Aug 9, 2015

videlec commented Aug 9, 2015

This comment has been minimized.

mezzarobba commented Aug 18, 2015

videlec commented Aug 18, 2015

mezzarobba commented Aug 25, 2015

mezzarobba commented Aug 25, 2015

sagetrac-git mannequin commented Aug 26, 2015

sagetrac-git mannequin commented Aug 26, 2015

videlec commented Aug 26, 2015

sagetrac-git mannequin commented Aug 26, 2015

sagetrac-git mannequin commented Aug 26, 2015

bgrenet commented Aug 27, 2015

videlec commented Aug 27, 2015

sagetrac-git mannequin commented Aug 27, 2015

sagetrac-git mannequin commented Aug 27, 2015

mezzarobba commented Aug 28, 2015

bgrenet commented Aug 28, 2015

sagetrac-git mannequin commented Aug 29, 2015

sagetrac-git mannequin commented Aug 29, 2015

sagetrac-git mannequin commented Aug 29, 2015

sagetrac-git mannequin commented Aug 29, 2015

videlec commented Aug 29, 2015

mezzarobba commented Sep 1, 2015

sagetrac-git mannequin commented Sep 1, 2015

sagetrac-git mannequin commented Sep 1, 2015

videlec commented Sep 1, 2015

mezzarobba commented Sep 2, 2015

vbraun commented Sep 2, 2015