#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_invert.patch is applied after #1956 patches and
trac_1956_faster_MPowerSeries_mul2.patch
In this patch `__invert__` is implemented using `_mul_trunc_generic`;
inversion of a generic multivariate series becomes much faster.
In the benchmarks (0) is without this patch, (1) with it
{{{
sage: N = 4
sage: R = PowerSeriesRing(QQ,N,'x')
sage: x = R.gens()
sage: sx = sum(x)
sage: prec = 15
sage: p = (1 + sx + R.O(prec))^-1 + (1 + 2*sx + R.O(prec))^-1
sage: %time p1 = p^-1
Wall time: 0.40 s
N prec (0) (1)
2 30 1.18 0.08
2 50 30.3 0.87
4 15 42.0 0.40
4 20 662 3.2
}}}
{{{
sage: N = 4
sage: R = PowerSeriesRing(QQ,N,'x')
sage: x = R.gens()
sage: prec = 30
sage: p = sum([(i+1)*x[i]^(i+1) for i in range(N)]) + R.O(prec)
sage: p = 1 + sum([p^i/i for i in range(1,prec)])
sage: %time p1 = p^-1
Wall time: 0.28 s
N prec (0) (1)
2 30 0.37 0.03
2 50 5.7 0.28
4 30 32.6 0.28
8 30 1566 1.0
}}}
A special kind of series inversion are series of degree much lower than
prec, like
{{{
p = 1 + 2*x[0] + 3*x[1] + 4*x[2] + 5*x[3] + R.O(30)
}}}
inversion is much faster because in the iteration in the Newton method
the expensive multiplication at order next_prec becomes trivial.
It remains a square of a polynomial of degree roughly next_prec/2 .
In this case this patch does not change speed; in this ticket there is a
lot
of benchmarks for this case, see bench1.sage
Finally I point out that in ticket #10720 I wrote a similar but slower
version of `__invert__` for series on rings of polynomials; I will improve
that version, but notice that the speedup of `__invert__` in a generic
series on rings of polynomials is much smaller than here.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10532#comment:7>
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.
