#1956: implement multivariate power series arithmetic
-----------------------------------+----------------------------------------
Reporter: was | Owner: malb
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-feature
Component: commutative algebra | Keywords:
Author: niles | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
-----------------------------------+----------------------------------------
Comment(by niles):
Replying to [comment:7 malb]:
> Replying to [comment:6 niles]:
>
> > > * It would be nice if you could add line breaks around 80 for the
doc strings
fixed now
> > > * the arithmetic functions doctests do not test correctness of the
output
arithmetic tests now printed, and confirmed with polynomial tests
> Have you compared the speed with, say, Magma?
Here are five simple comparisons, three with 2 variables and two with 4
variables, all over QQ. This sage patch performs substantially better in
3/4 cases, with magma performing substantially better in the other case.
Using polynomial multiplication easily beats magma's restriction on the
number of coefficients it will compute for a lazy power series (test 3).
Processor: `6-core: model name: Intel(R) Xeon(R) CPU X7460 @ 2.66GHz`
sage:
{{{
sage: L.<a,b,c,d> = MPowerSeriesRing(QQ,4)
sage: %timeit s = (1 + 2*a + 3*b + 4*d + L(0).O(16))^-5
5 loops, best of 3: 3.18 s per loop
sage: time (1 + a^3 + b^3 + c^4 + d^4 + L(0).O(15))^-20
CPU times: user 0.02 s, sys: 0.00 s, total: 0.02 s
Wall time: 0.02 s
<SNIP>
sage: f = -1/6*b^6*d^14 - 1/9*a^4*b^10*c^4*d^12 + b^10*c^11*d^21 -
a*b^14*c^24*d^4 - 1/66*a^16*b^11*c^17 + L(0).O(50)
sage: time f^20
CPU times: user 0.16 s, sys: 0.00 s, total: 0.16 s
Wall time: 0.16 s
1/3656158440062976*b^120*d^280
+ 5/1371059415023616*a^4*b^124*c^4*d^278
+ 95/4113178245070848*a^8*b^128*c^8*d^276
- 5/152339935002624*b^124*c^11*d^287
+ 5/152339935002624*a*b^128*c^24*d^270
+ 5/10054435710173184*a^16*b^125*c^17*d^266
+ O(a, b, c, d)^430
}}}
magma:
{{{
> L<a, b, c, d> := LazyPowerSeriesRing(Rationals(), 4);
> s := (1 + 2*a + 3*b + 4*d)^-5;
> time Coefficients(s, 15);
<SNIP>
Time: 29.020
> s := (1 + a^3 + b^3 + c^4 + d^4)^-20;
> time Coefficients(s, 14);
<SNIP>
Time: 48.850
> s := (-1/6*b^6*d^14 - 1/9*a^4*b^10*c^4*d^12 + b^10*c^11*d^21 -
a*b^14*c^24*d^4 - 1/66*a^16*b^11*c^17)^20;
> time Coefficients(s, 14);
<SNIP>
Time: 16.340
> time Coefficients(s, 429);
>> time Coefficients(s, 429);
^
Runtime error in 'Coefficients': The number of coefficients to be returned
must be small
}}}
sage:
{{{
sage: Z.<a,b> = MPowerSeriesRing(QQ,2)
sage: time (1 + 1/2*a + 3*b + 4*a*b + 1/5*a^2 + 5/6*b^2 + Z(0).O(30))^-20
CPU times: user 12.67 s, sys: 0.01 s, total: 12.68 s
Wall time: 12.68 s
<SNIP>
sage: f = 1 + a^14*b^9 + 8/3*a^22*b^11 - 1/13*a^23*b^19 + a^15*b^28 +
Z(0).O(51)
sage: time f^-20
CPU times: user 0.05 s, sys: 0.00 s, total: 0.05 s
Wall time: 0.05 s
1 - 20*a^14*b^9 - 160/3*a^22*b^11 + 20/13*a^23*b^19
- 20*a^15*b^28 + 210*a^28*b^18 + O(a, b)^51
}}}
magma:
{{{
> Z<a, b> := LazyPowerSeriesRing(Rationals(), 2);
> t := (1 + 1/2*a + 3*b + 4*a*b + 1/5*a^2 + 5/6*b^2)^-20;
> time Coefficients(t, 29);
<SNIP>
Time: 1.580
> s := (1 + a^14*b^9 + 8/3*a^22*b^11 - 1/13*a^23*b^19 + a^15*b^28)^-20;
> time Coefficients(s, 50);
<SNIP>
Time: 90.840
}}}
In the case where this package performs badly, it seems to be caused by
the rational coefficients:
{{{
sage: Z.<a,b> = MPowerSeriesRing(QQ,2)
sage: time (1 + a + b + a*b + a^2 + b^2 + Z(0).O(30))^-20;
CPU times: user 1.90 s, sys: 0.00 s, total: 1.90 s
Wall time: 1.90 s
sage: time (1 + a + 2*b - a*b + 3*a^2 - b^2 + Z(0).O(30))^-20;
CPU times: user 2.78 s, sys: 0.00 s, total: 2.78 s
Wall time: 2.78 s
sage: time (1 + a + 12*b - 10*a*b + 13*a^2 - 7*b^2 + Z(0).O(30))^-20;
CPU times: user 3.14 s, sys: 0.00 s, total: 3.14 s
Wall time: 3.14 s
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/1956#comment:8>
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.
