#8972: Inversion and fraction fields for power series rings
--------------------------+-------------------------------------------------
Reporter: SimonKing | Owner: AlexGhitza
Type: defect | Status: needs_review
Priority: major | Milestone: sage-4.4.2
Component: algebra | Keywords: power series ring, fraction field
Author: Simon King | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
--------------------------+-------------------------------------------------
Changes (by SimonKing):
* status: needs_work => needs_review
* work_issues: improve timings =>
Comment:
The second patch does several things:
1. It turned out that in several places it is assumed that the quotient
of two power series is a power series, not a Laurent series. I tried to
take care of this.
2. I improved the timings, so that (according to the timings below) the
performance is competitive (sometimes clearly better, sometimes very
little worse) then the original performance.
The reason why the old timings were good was some kind of lazyness: The
result of a division was not in the fraction field (as it should be!), but
in a simpler ring, so that subsequent computations became easier. On the
other hand, transformation into a Laurent polynomial was quite expensive,
since there ''always'' was a transformation into the Laurent Series Ring's
underlying Power Series Ring -- even if the given data already belong to
it.
Solution (as usual): Add an optional argument "check" to the init method
of Laurent Series.
And then I tried to benefit from keeping the results as simple as possible
(like the old code did), but in a more proper way. Let ``f`` be a Laurent
series in a Laurent series ring ``L``. In the old code, one always had
``L.power_series_ring() is f.valuation_zero_part().parent()``. I suggest
to relax this condition: It is sufficient to have a coercion:
{{{
sage: R.<x> = ZZ[[]]
sage: f = 1/(1+2*x)
sage: f.parent()
Laurent Series Ring in x over Rational Field
sage: f.parent().power_series_ring()
Power Series Ring in x over Rational Field
sage: f.power_series().parent()
Power Series Ring in x over Integer Ring
}}}
'''__Timings__'''
Without the two patches:
{{{
sage: R.<x> = ZZ[[]]
sage: timeit('a=1/x')
625 loops, best of 3: 291 µs per loop
sage: timeit('a=(1+x)/x')
625 loops, best of 3: 295 µs per loop
sage: timeit('a=1/(1+x)')
625 loops, best of 3: 1.07 ms per loop
sage: timeit('a=(1+x)/(1-x)')
625 loops, best of 3: 1.07 ms per loop
sage: y = (3*x+2)/(1+x)
sage: y=y/x
sage: z = (x+x^2+1)/(1+x^4+2*x^3+4*x)
sage: z=y/x
sage: timeit('y+z')
625 loops, best of 3: 213 µs per loop
sage: timeit('y*z')
625 loops, best of 3: 118 µs per loop
sage: timeit('y-z')
625 loops, best of 3: 212 µs per loop
sage: timeit('y/z')
ERROR: An unexpected error occurred while tokenizing input
The following traceback may be corrupted or invalid
The error message is: ('EOF in multi-line statement', (27, 0))
---------------------------------------------------------------------------
ArithmeticError Traceback (most recent call
last)
...
ArithmeticError: division not defined
}}}
With the two patches:
{{{
sage: R.<x> = ZZ[[]]
sage: timeit('a=1/x')
625 loops, best of 3: 220 µs per loop
sage: timeit('a=(1+x)/x')
625 loops, best of 3: 228 µs per loop
sage: timeit('a=1/(1+x)')
625 loops, best of 3: 1.25 ms per loop
sage: timeit('a=(1+x)/(1-x)')
625 loops, best of 3: 1.26 ms per loop
sage: y = (3*x+2)/(1+x)
sage: y=y/x
sage: z = (x+x^2+1)/(1+x^4+2*x^3+4*x)
sage: z=y/x
sage: timeit('y+z')
625 loops, best of 3: 191 µs per loop
sage: timeit('y*z')
625 loops, best of 3: 92.6 µs per loop
sage: timeit('y-z')
625 loops, best of 3: 191 µs per loop
sage: timeit('y/z')
25 loops, best of 3: 9.35 ms per loop
}}}
So, my patches not only fix some bugs, but they also slightly improve the
performance.
I tested all files that I have changed, but I can not exclude errors in
other files.
I forgot to insert my name as an author, but presumably there will be a
revision needed anyway, after comments of referees...
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8972#comment:10>
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.
