#1956: implement multivariate truncated power series arithmetic
-------------------------------------------+--------------------------------
Reporter: was | Owner: pernici
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-4.6.2
Component: commutative algebra | Keywords: multivariate power
series
Author: Niles Johnson | Upstream: N/A
Reviewer: Martin Albrecht, Simon King | Merged:
Work_issues: |
-------------------------------------------+--------------------------------
Comment(by pernici):
Niles,
going back to the benchmarks you posted in ticket #1956 (see also
bench1.sage
posted here), here is a comparison with PARI
{{{
(2) latest patch in this ticket
(3) PARI/GP
times in ms
test no. 1 2 3 4 5 6 7 8
(2) 28.2 2.3 24.8 166 8.16 21 45.2 56.7
(3) 27.8 20 19.7 94.4 16 43.2 47.2 48
}}}
PARI ranges from 8.7x slower to 1.8x faster; it is slowest in the
second example; the timings for (3) fluctuate a lot, unlike those of (2);
above I gave the first timings I got.
I took a few times the timings for (3) in the second example
{{{
sage: %timeit gp('(1 + T^3*(a^3 + b^3) + T^4*(c^4 + d^4) +
O(T^(15)))^-20')
25 loops, best of 3: 17.3 ms per loop
}}}
I got timings from 14 ms to 23 ms, while I get regularly 2.3 ms for (2)
{{{
sage: L.<a,b,c,d> = PowerSeriesRing(QQ,4)
sage: %timeit (1 + a^3 + b^3 + c^4 + d^4 + L.O(15))^-20
125 loops, best of 3: 2.3 ms per loop
}}}
even taking the best time for PARI in this example, it is still 6x slower.
I decided to make comparison with PARI/GP prompted by your post in ticket
#1956 about distributing the review of that ticket.
I thought that another item there could be:
comparison with other CAS
and so I tried the comparison with PARI.
IMHO this ticket could be closed: I consider settled that generic
truncated
multiplication is faster than Karatsuba for multivariate series.
The comparison with PARI is fairly favorable; the latest patch is
from 6x faster to 2.5x slower than PARI/GP in the given benchmarks with
the QQ field, and it is generic code, working with any ring.
These benchmarks should help reviewers in settling the item:
Performance: the multivariate power series arithmetic is fast enough to be
included in Sage
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/1956#comment:86>
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.
