406 views

Skip to first unread message

Dec 7, 2009, 11:18:19 AM12/7/09

to sage-support

Hi there,

Does anyone know if Sage has a function for computing the composition

inverse of a power series (not the reciprocal)?

--Matt

P.S. Just started using sage and finding it very useful. Thanks for

developing it.

Does anyone know if Sage has a function for computing the composition

inverse of a power series (not the reciprocal)?

--Matt

P.S. Just started using sage and finding it very useful. Thanks for

developing it.

Dec 7, 2009, 1:43:43 PM12/7/09

to sage-support

2009/12/7 Matt Bainbridge <bainbri...@gmail.com>:

sage: R.<x> = QQ[[]]

sage: f = 1/(1-x) - 1; f

x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9 + x^10 + x^11 + x^12

+ x^13 + x^14 + x^15 + x^16 + x^17 + x^18 + x^19 + O(x^20)

sage: g = f.reversion(); g

x - x^2 + x^3 - x^4 + x^5 - x^6 + x^7 - x^8 + x^9 - x^10 + x^11 - x^12

+ x^13 - x^14 + x^15 - x^16 + x^17 - x^18 + x^19 + O(x^20)

sage: f(g)

x + O(x^20)

> --Matt

>

> P.S. Just started using sage and finding it very useful. Thanks for

> developing it.

>

> --

> To post to this group, send email to sage-s...@googlegroups.com

> To unsubscribe from this group, send email to sage-support...@googlegroups.com

> For more options, visit this group at http://groups.google.com/group/sage-support

> URL: http://www.sagemath.org

--

William Stein

Associate Professor of Mathematics

University of Washington

http://wstein.org

> Hi there,

>

> Does anyone know if Sage has a function for computing the composition

> inverse of a power series (not the reciprocal)?

Yep, we have that:
>

> Does anyone know if Sage has a function for computing the composition

> inverse of a power series (not the reciprocal)?

sage: R.<x> = QQ[[]]

sage: f = 1/(1-x) - 1; f

x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9 + x^10 + x^11 + x^12

+ x^13 + x^14 + x^15 + x^16 + x^17 + x^18 + x^19 + O(x^20)

sage: g = f.reversion(); g

x - x^2 + x^3 - x^4 + x^5 - x^6 + x^7 - x^8 + x^9 - x^10 + x^11 - x^12

+ x^13 - x^14 + x^15 - x^16 + x^17 - x^18 + x^19 + O(x^20)

sage: f(g)

x + O(x^20)

> --Matt

>

> P.S. Just started using sage and finding it very useful. Thanks for

> developing it.

>

> To post to this group, send email to sage-s...@googlegroups.com

> To unsubscribe from this group, send email to sage-support...@googlegroups.com

> For more options, visit this group at http://groups.google.com/group/sage-support

> URL: http://www.sagemath.org

--

William Stein

Associate Professor of Mathematics

University of Washington

http://wstein.org

Dec 7, 2009, 2:04:23 PM12/7/09

to sage-support

Thanks, William!

I guess so far it only works over Q?

--Matt

On Dec 7, 7:43 pm, William Stein <wst...@gmail.com> wrote:

> 2009/12/7 Matt Bainbridge <bainbridge.m...@gmail.com>:

I guess so far it only works over Q?

--Matt

On Dec 7, 7:43 pm, William Stein <wst...@gmail.com> wrote:

> 2009/12/7 Matt Bainbridge <bainbridge.m...@gmail.com>:

>

> > Hi there,

>

> > Does anyone know if Sage has a function for computing the composition

> > inverse of a power series (not the reciprocal)?

>

> Yep, we have that:

>

> sage: R.<x> = QQ[[]]

> sage: f = 1/(1-x) - 1; f

> x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9 + x^10 + x^11 + x^12

> + x^13 + x^14 + x^15 + x^16 + x^17 + x^18 + x^19 + O(x^20)

> sage: g = f.reversion(); g

> x - x^2 + x^3 - x^4 + x^5 - x^6 + x^7 - x^8 + x^9 - x^10 + x^11 - x^12

> + x^13 - x^14 + x^15 - x^16 + x^17 - x^18 + x^19 + O(x^20)

> sage: f(g)

> x + O(x^20)

>

> > --Matt

>

> > P.S. Just started using sage and finding it very useful. Thanks for

> > developing it.

>

> > --

> > To post to this group, send email to sage-s...@googlegroups.com

> > To unsubscribe from this group, send email to sage-support...@googlegroups.com

> > For more options, visit this group athttp://groups.google.com/group/sage-support
> > Hi there,

>

> > Does anyone know if Sage has a function for computing the composition

> > inverse of a power series (not the reciprocal)?

>

> Yep, we have that:

>

> sage: R.<x> = QQ[[]]

> sage: f = 1/(1-x) - 1; f

> x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9 + x^10 + x^11 + x^12

> + x^13 + x^14 + x^15 + x^16 + x^17 + x^18 + x^19 + O(x^20)

> sage: g = f.reversion(); g

> x - x^2 + x^3 - x^4 + x^5 - x^6 + x^7 - x^8 + x^9 - x^10 + x^11 - x^12

> + x^13 - x^14 + x^15 - x^16 + x^17 - x^18 + x^19 + O(x^20)

> sage: f(g)

> x + O(x^20)

>

> > --Matt

>

> > P.S. Just started using sage and finding it very useful. Thanks for

> > developing it.

>

> > --

> > To post to this group, send email to sage-s...@googlegroups.com

> > To unsubscribe from this group, send email to sage-support...@googlegroups.com

Dec 9, 2009, 10:35:59 AM12/9/09

to sage-support

On Mon, Dec 7, 2009 at 11:04 AM, Matt Bainbridge

<bainbri...@gmail.com> wrote:

> Thanks, William!

>

> I guess so far it only works over Q?

>

> --Matt

>

It calls off to PARI, so it probably works (or can trivially be made
<bainbri...@gmail.com> wrote:

> Thanks, William!

>

> I guess so far it only works over Q?

>

> --Matt

>

to work) over any base that PARI supports. In case it isn't

implemented in general in sage, it would be nice if somebody were to

add that.

William

Dec 9, 2009, 11:15:33 AM12/9/09

to sage-s...@googlegroups.com

William Stein <wst...@gmail.com> writes:

> On Mon, Dec 7, 2009 at 11:04 AM, Matt Bainbridge

> <bainbri...@gmail.com> wrote:

>> Thanks, William!

>>

>> I guess so far it only works over Q?

>>

>> --Matt

>>

>

> It calls off to PARI, so it probably works (or can trivially be made

> to work) over any base that PARI supports.

In case it doesn't and you really really need it, and there is no other way to do it, you could call
> On Mon, Dec 7, 2009 at 11:04 AM, Matt Bainbridge

> <bainbri...@gmail.com> wrote:

>> Thanks, William!

>>

>> I guess so far it only works over Q?

>>

>> --Matt

>>

>

> It calls off to PARI, so it probably works (or can trivially be made

> to work) over any base that PARI supports.

the fricas implementation for lazy power series. Eg: (WARNING: ASCII art follows)

sage: X=fricas('monomial(1,1)$UnivariateTaylorSeries(SquareMatrix(2, PrimeField 7), x, 0)')

sage: X

x

sage: s = 4*(fricas.recip(1-2*X)-1)

sage: s

+2 0+ 2 +4 0+ 3 4 +2 0+ 5 +4 0+ 6 7 +2 0+ 8 +4 0+ 9 10 11

x + | |x + | |x + x + | |x + | |x + x + | |x + | |x + x + O(x )

+0 2+ +0 4+ +0 2+ +0 4+ +0 2+ +0 4+

sage: t = fricas.revert(s)

sage: t

+5 0+ 2 +4 0+ 3 4 +2 0+ 5 +3 0+ 6 7 +5 0+ 8 +4 0+ 9 10 11

x + | |x + | |x - x + | |x + | |x + x + | |x + | |x - x + O(x )

+0 5+ +0 4+ +0 2+ +0 3+ +0 5+ +0 4+

sage: fricas.elt(t,s)

11

x + O(x )

sage: fricas.coefficient(t, 100)

+6 0+

| |

+0 6+

(Unfortunately, the sage wrapper is not very polished... The computations should be pretty fast

though.)

Martin

Dec 9, 2009, 1:50:56 PM12/9/09

to sage-support

Its easy enough to code this in sage. This seems to work over any

field:

def ps_inverse(f):

if f.prec() is infinity:

raise ValueError, "series must have finite precision for

reversion"

if f.valuation() != 1:

raise ValueError, "series must have valuation one for

reversion"

t = parent(f).gen()

a = 1/f.coefficients()[0]

g = a*t

for i in range(2, f.prec()):

g -= ps_coefficient((f + O(t^(i+1)))(g),i)*a*t^i

g += O(t^f.prec())

return g

def ps_coefficient(f,i):

if i >= f.prec():

raise ValueError, "that coefficient is undefined"

else:

return f.padded_list(f.prec())[i]

field:

def ps_inverse(f):

if f.prec() is infinity:

raise ValueError, "series must have finite precision for

reversion"

if f.valuation() != 1:

raise ValueError, "series must have valuation one for

reversion"

t = parent(f).gen()

a = 1/f.coefficients()[0]

g = a*t

for i in range(2, f.prec()):

g -= ps_coefficient((f + O(t^(i+1)))(g),i)*a*t^i

g += O(t^f.prec())

return g

def ps_coefficient(f,i):

if i >= f.prec():

raise ValueError, "that coefficient is undefined"

else:

return f.padded_list(f.prec())[i]

Dec 9, 2009, 3:20:29 PM12/9/09

to sage-s...@googlegroups.com

On Wed, Dec 9, 2009 at 10:50 AM, Matt Bainbridge

<bainbri...@gmail.com> wrote:

> Its easy enough to code this in sage. This seems to work over any

> field:

Thanks. This is now http://trac.sagemath.org/sage_trac/ticket/7644
<bainbri...@gmail.com> wrote:

> Its easy enough to code this in sage. This seems to work over any

> field:

>

>

> def ps_inverse(f):

> if f.prec() is infinity:

> raise ValueError, "series must have finite precision for

> reversion"

> if f.valuation() != 1:

> raise ValueError, "series must have valuation one for

> reversion"

> t = parent(f).gen()

> a = 1/f.coefficients()[0]

> g = a*t

> for i in range(2, f.prec()):

> g -= ps_coefficient((f + O(t^(i+1)))(g),i)*a*t^i

> g += O(t^f.prec())

> return g

>

> def ps_coefficient(f,i):

> if i >= f.prec():

> raise ValueError, "that coefficient is undefined"

> else:

> return f.padded_list(f.prec())[i]

>

> --

> To post to this group, send email to sage-s...@googlegroups.com

> To unsubscribe from this group, send email to sage-support...@googlegroups.com

> For more options, visit this group at http://groups.google.com/group/sage-support
> To post to this group, send email to sage-s...@googlegroups.com

> To unsubscribe from this group, send email to sage-support...@googlegroups.com

Dec 25, 2009, 9:58:42 AM12/25/09

to sage-support

Some code for Lagrange inversion has been posted on the "generic power

series reversion" trac ticket: http://trac.sagemath.org/sage_trac/ticket/7644

series reversion" trac ticket: http://trac.sagemath.org/sage_trac/ticket/7644

The code doesn't quite run, since it references some other function

(ps_coefficient); here's an updated version which uses only built-in

functions:

def ps_inverse_Lagrange(f):

if f.valuation() != 1:

raise ValueError, "series must have valuation one for

reversion"

if f.prec() is infinity:

raise ValueError, "series must have finite precision for

reversion"

t = parent(f).gen()

h = t/f

k = 1

g = 0

for i in range(1, f.prec()):

k *= h

g += (1/i)*k.padded_list(i)[i - 1]*t^i

g += O(t^f.prec())

return g

On Dec 9, 3:20 pm, William Stein <wst...@gmail.com> wrote:

> On Wed, Dec 9, 2009 at 10:50 AM, Matt Bainbridge

>

> > For more options, visit this group athttp://groups.google.com/group/sage-support

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu