#1956: implement multivariate power series arithmetic
-------------------------------------------+--------------------------------
Reporter: was | Owner: pernici
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-4.6.1
Component: commutative algebra | Keywords: multivariate power
series
Author: Niles Johnson | Upstream: N/A
Reviewer: Martin Albrecht, Simon King | Merged:
Work_issues: |
-------------------------------------------+--------------------------------
Changes (by pernici):
* owner: malb => pernici
Comment:
After applying trac_1956_multi_power_series_new_4.patch,
trac_1956_uni_multi_ps_2.patch,
trac_1956_multi_ps_cleanup.patch
(main version), apply
trac_10480_fast_PowerSeries_poly_multiplication2.patch from ticket #10480
and
trac_1956_faster_MPowerSeries_mul.patch
(version (1) in benchmarks below)
In the attached patch MPowerSeries._mul_ uses the do_mul_trunc_generic
algorithm in polynomial_element.pyx.
The first benchmark has the 8 inversions posted here by Niles to compare
with Magma, but with precisions multiplied by N; times are in seconds;
processor:4-core: Intel Core i7 CPU 860 @ 2.80GHz
on x86_64 GNU/Linux
{{{
test no. 1 2 3 4 5 6 7 8
N=1
main 2.72 0.02 0.18 10.5 0.05 1.55 2.33 2.61
(1) 0.05 0.01 0.05 0.24 0.03 0.04 0.07 0.09
N=2
main 290 1.7 0.75 1024 0.16 49.0 64.3 73.8
(1) 2.37 0.02 0.07 5.53 0.05 0.68 1.24 1.41
N=3
main 7743 67 4.4 24272 0.84 432 566 651
(1) 32 0.12 0.11 56 0.08 5.2 7.8 9.1
}}}
The next benchmark takes a random series and performs p = p*(p+1) N times;
the same series is used in testing with the two versions; see attached
mu.sage
{{{
N=1 2 3 4
n=2
prec=20 bound=20
main 0.002 0.005 0.005 0.005
(1) 6e-4 6e-4 6e-4 5e-4
prec=100 bound=100
main 0.084 0.81 2.6 3.3
(1) 0.003 0.005 0.006 0.006
prec=200 bound=200
main 0.52 153 3932 7337
(1) 0.03 0.31 1.1 1.2
n=4
prec=20 bound=20
main 0.003 0.003 0.003 0.003
(1) 6e-4 5e-4 5e-4 5e-4
prec=100 bound=100
main 0.087 0.19 0.19 0.19
(1) 0.002 0.002 0.002 0.002
prec=200 bound=200
main 0.59 1.97 1.91 1.66
(1) 0.008 0.008 0.008 0.008
}}}
Applying only trac_10480_fast_PowerSeries_poly_multiplication2.patch, not
trac_1956_faster_MPowerSeries_mul.patch, MPowerSeries._mul_ uses
univariate series multiplication, which uses the do_mul_trunc algorithm
instead of the do_mul_trunc_generic algorithm; the latter is slower
than the unpatched version in some test in un.sage in #10480,
while the former is always faster.
The latter algorithm is always faster than main in the tests above,
and most of the times a few times faster than the former algorithm, so
it seems a better choice for multivariate series.
With this patch _send_to_bg and _send_to_fg are faster; using
the attached benchmark file bg.sage,
n=number of variables, h=precision, N=100 random polynomials,
bg=_send_to_bg, fg=_send_to_fg
{{{
n=2 h=20 n=2 h=100 n=4 h=20 n=4 h=100
bg fg bg fg bg fg bg fg
main 0.89 0.02 42 0.06 1.18 0.02 58 0.06
(1) 0.019 0.002 0.09 0.02 0.018 0.002 0.09 0.01
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/1956#comment:59>
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.
