#7644: generic power series reversion
-----------------------------+----------------------------------------------
Reporter: was | Owner: AlexGhitza
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-4.6.1
Component: algebra | Keywords: lagrange, reversion
Author: Niles Johnson | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
-----------------------------+----------------------------------------------
Old description:
> From this [http://groups.google.com/group/sage-
> support/browse_thread/thread/34fdf02add8100b6 sage-support] thread: Make
> the following work over any base ring:
> {{{
> 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 Bainbridge says about power series reversion, which uses pari in
> some cases, and maybe isn't there in others:
> {{{
> 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]
> }}}
>
> == Apply ==
>
> 1. [attachment:trac_7644_reversion_lagrange_2.2.patch]
New description:
From this [http://groups.google.com/group/sage-
support/browse_thread/thread/34fdf02add8100b6 sage-support] thread: Make
the following work over any base ring:
{{{
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 Bainbridge says about power series reversion, which uses pari in some
cases, and maybe isn't there in others:
{{{
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]
}}}
== Apply ==
1. [attachment:trac_7644_reversion_lagrange_3.patch]
--
Comment(by niles):
Replying to [comment:10 fwclarke]:
> I've been looking at this.
Thanks!
> One concern is that for power series with rational coefficients the
existing method using pari is a great deal faster, so that at least in
this case the pari method should be retained.
Yes, especially if there is work in progress to support converting more
rings to pari. I wrote a revised patch which first attempts to convert to
pari and do reversion there, and then tries the Lagrange inversion if
conversion to pari fails. I think that implementation means that this
patch can be independent of #4376 -- it will simply perform better when
that patch is included.
> I also think it is sensible to be able to revert infinite precision
series, either by specifying the desired precision or by using the
parent's default precision.
Yes, upon further consideration I agree. I've made this and two other
improvements:
1. Given a power series with infinite precision and degree `deg`, it's
reversion is computed with precision `deg + 1`.
1. Given a power series whose leading coefficient is not a unit, the code
tries to pass to the fraction field of the base ring and compute the
reversion there.
1. Given a power series over a base ring of positive characteristic, the
code tries to lift to a characteristic zero base (using `.lift()`),
compute the reversion, and then push back down to the positive
characteristic base. This works over finite fields and `Zmod(n)`, but
fails over a base ring like `Zmod(n)[x]`.
Each of these is demonstrated with an example.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/7644#comment:11>
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 post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
