#10532: Faster multiplication for multivariate power series
-----------------------------------+----------------------------------------
Reporter: niles | Owner: malb
Type: enhancement | Status: needs_info
Priority: major | Milestone:
Component: commutative algebra | Keywords: multivariate power series
multiplication Karatsuba
Author: pernici | Upstream: N/A
Reviewer: Niles Johnson | Merged:
Work_issues: |
-----------------------------------+----------------------------------------
Comment(by pernici):
The attached trac_10532_square_trunc.patch is applied after #1956 patches,
trac_1956_faster_MPowerSeries_mul2.patch and trac_10532_invert.patch
With this patch truncated multiplication is optimized for squares.
Benchmark comparison with PARI/GP:
{{{
sage: N = 4
sage: R = PowerSeriesRing(QQ,N,'x')
sage: x = R.gens()
sage: sx = sum(x)
sage: prec = 20
sage: n = 1
sage: %time p = ((1 + sx + R.O(prec))^-1 + (1 + 2*sx + R.O(prec))^-1)^-n
Wall time: 4.06 s
}}}
to do the computation with `gp` allocate more memory than the one assigned
by default; here the computation
is done directly with the background field
{{{
sage: try:
....: gp.allocatemem()
....: except:
....: pass
....:
sage: N = 4
sage: prec = 20
sage: n = 1
sage: sx = '+'.join(['x%d' % i for i in range(N)])
sage: fmt = '((1 + t*(%s) + O(t^%s))^-1 + (1 + 2*t*(%s) +
O(t^%s))^-1)^-%s'
sage: %time p1 = gp(fmt %(sx,prec,sx,prec,n))
Wall time: 1.56 s
(0) version of ticket #1956
(1) with trac_10532_invert.patch
(2) with trac_10532_square_trunc.patch
(3) with gp (PARI/GP)
N prec n (0) (1) (2) (3)
2 30 1 1.2 0.10 0.10 0.06
2 30 20 8.6 0.22 0.18 0.12
2 50 1 21 1.2 1.2 0.55
2 50 20 213 2.1 1.8 1.2
4 15 1 42 0.46 0.46 0.22
4 15 20 323 1.2 0.96 0.43
4 20 1 673 4.1 4.1 1.6
4 20 20 >7000 10 8.1 3.2
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10532#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.
