#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):
Attachments: bench1.sage, mu2.sage
Here are some benchmarks comparing:
(1) with do_mul_trunc_generic
from trac_10480_fast_PowerSeries_poly_multiplication2.patch,
trac_1956_faster_MPowerSeries_mul.patch
(2,K) with do_trunc_karatsuba, where K is K_threshold
from trac_karatsuba_improvements.patch,
trac_10480_fast_PowerSeries_poly_multiplication-alternative.patch
(1) or (2) are applied after applying
trac_1956_multi_power_series_new_4.patch,
trac_1956_uni_multi_ps_2.patch,
trac_1956_multi_ps_cleanup.patch.
These tests are run with QQ and GF(7) as examples of fields
implemented in libsingular, RR as field not implemented there.
Various values of K are tried; (1) corresponds to the K=infinity case
for QQ and GF(7) (slightly slower because do_mul_trunc_generic has a
slightly slower implementation than the corresponding do_trunc_classical
by lftabera), but not for RR (and I guess for other fields not used in
libsingular), where (1) is slower.
The conclusion is that I think that (2) with K=infinity (or a large
integer to avoid using infinity) is the best choice.
bench1.sage are the benchmarks posted by Niles to compare with Magma,
with precision multiplied by N.
times are in seconds;
processor:4-core: Intel Core i7 CPU 860 @ 2.80GHz
on x86_64 GNU/Linux
{{{
prec = prec1*N
bench1.sage with GF(7)
test no. 1 2 3 4 5 6 7 8
prec1 16 15 50 30 51 30 30 30
N=3
(1) 0.45 0.03 0.49 0.49 0.45
(2,8) 2.16 0.06 1.21 1.25 1.10
(2,64) 0.45 0.03 0.55 0.56 0.54
(2,128) 0.43 0.03 0.44 0.45 0.44
N=4
(1) 1.80 0.06 1.44 1.34 1.22
(2,8) 3.95 0.12 3.89 3.79 3.25
(2,64) 1.88 0.06 1.69 1.60 1.50
(2,128) 1.78 0.06 1.45 1.34 1.22
N=5
(1) 8.96 0.21 5.01 4.65 4.27
(2,8) 23.2 0.52 14.8 14.3 12.3
(2,64) 11.2 0.23 6.55 6.01 5.53
(2,128) 8.74 0.19 5.50 5.11 4.69
N=6
(1) 27.0 0.67 9.99 9.35 9.17
(2,8) 87.2 1.56 30.4 31.2 26.4
(2,64) 34.5 0.74 13.6 12.8 12.4
(2,128) 26.1 0.67 10.9 10.1 9.79
N=7
(1) 40.8 1.46 18.6 17.3 16.1
(2,8) 132 3.67 57.6 60.4 51.4
(2,64) 51.1 1.55 25.0 23.3 21.1
(2,128) 39.3 1.51 20.4 19.2 17.6
(2,256) 38.3 1.32 18.3 16.9 15.9
bench1.sage with RR
test no. 1 2 3 4 5 6 7 8
prec1 16 15 50 30 51 30 30 30
N=1
(1) 1.18 0.06 0.88 0.70 0.23 0.67 0.69 0.70
(2,8) 0.34 0.04 0.61 4.92 0.18 0.47 0.57 0.89
(2,64) 0.18 0.04 0.74 0.27 0.20 0.24 0.26 0.26
N=2
(1) 57 0.96 1.6 8.4 0.67 8.2 8.5 8.4
(2,8) 19.5 0.29 1.4 >540 0.44 9.9 32 183
(2,64) 6.06 0.16 1.2 2.65 0.43 2.55 2.63 2.68
(2,128) 6.07 0.16 1.3 2.64 0.48 2.57 2.63 2.63
N=3
(2,64) 58.1 0.93 1.39 79.4 0.72 18.5 28.8 48.8
(2,128) 58.9 0.94 1.59 11.8 0.78 11.6 12.0 11.7
}}}
mu2.sage is a modification of the benchmark mu.sage posted in ticket #1956
in which the random polynomials are evaluated in t_i + 1;
the various series are stored in dat/ to compare times with
the same series and different algorithms; this is a workabout for
the lack of something like random.seed for random_element.
Timings are only indicative.
{{{
mu2.sage with QQ
N=1 2 3 4 5 6 7 8
n=2
prec=20 bound=20
(1) 0.007 0.01 0.02 0.04 0.09 0.21 0.58 1.79
(2,8) 0.015 0.03 0.06 0.10 0.22 0.58 1.88 5.92
(2,32) 0.007 0.01 0.02 0.04 0.09 0.20 0.57 1.74
prec=20 bound=100
(1) 0.007 0.01 0.03 0.05 0.11 0.28 0.79 2.4
(2,8) 0.019 0.04 0.07 0.13 0.30 0.85 2.64 8.2
(2,32) 0.007 0.01 0.03 0.05 0.11 0.27 0.78 2.4
prec=100 bound=100
(1) 2.96 4.46 7.14 13.4 31.8
(2,8) 18.0 32.6 67.1 162 494
(2,32) 6.82 10.7 18.8 38.7 104
(2,128) 2.91 4.40 7.23 13.5 32.1
mu2.sage with GF(7)
n=2
prec=100 bound=100
(1) 0.08 0.08 0.08 0.08 0.09 0.09 0.09 0.09
(2,8) 0.41 0.45 0.45 0.44 0.45 0.45 0.46 0.44
(2,128) 0.07 0.08 0.08 0.08 0.08 0.08 0.08 0.08
prec=200 bound=200
(1) 1.05 1.21 1.22 1.23 1.22
(2,8) 11.0 12.5 12.4 12.4 12.5
(2,128) 1.41 1.59 1.58 1.59 1.58
(2,256) 1.00 1.14 1.12 1.14 1.15
mu2.sage with RR
n=2
prec=20 bound=20
(1) 0.03 0.06 0.06 0.06 0.06 0.06 0.06 0.06
(2,8) 0.03 0.04 0.15 0.41 1.15 3.66 12.8 45.7
(2,128) 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01
prec=20 bound=100
(1) 0.05 0.05 0.06 0.06 0.06 0.06 0.06 0.06
(2,8) 0.03 0.07 0.23 0.42 1.08 2.71 5.94 10.2
(2,128) 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01
prec=100 bound=100
(1) 1.87 1.87 1.91 1.87 1.88
(2,8) 1.06 8.95 69.0 332 2050
(2,128) 0.31 0.31 0.31 0.31 0.31
n=4
prec=20 bound=20
(1) 4.05 68.8 69.5 71.1 76.1
(2,8) 3.91 66.0 615 >2000
(2,128) 1.16 2.00 2.02 2.05 2.03
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10532#comment:3>
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.
