#16516: Faster roots computation for sparse polynomials over ZZ
-------------------------------------+-------------------------------------
Reporter: bruno | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.3
Component: commutative | Resolution:
algebra | Merged in:
Keywords: roots, sparse | Reviewers:
polynomial | Work issues:
Authors: | Commit:
Report Upstream: N/A | f344cdc5b4a9e316a52f5372a30a3db1ac5043ab
Branch: | Stopgaps:
u/bruno/faster_roots_computation_for_sparse_polynomials_over_zz|
Dependencies: |
-------------------------------------+-------------------------------------
Comment (by bruno):
Hi Vincent,
Thanks for the comments. I pushed a new version taking them into account,
especially for the "better code" part.
For roots over QQbar, I think it is not really related to this ticket. It
is related to #15790 (implementation of GCD for sparse polynomials). I'd
like to work in this other ticket too.
Now for the most complicate part (to my mind), timings. The issue is the
following: Whether the new algorithm is better than the previous one is
not a matter of density. For instance, if you have `p = 3 - x + x^7 * q`
where `q` is a very high-degree dense polynomial, integer roots of `p` are
common roots of `3-x` and `q`. And the same thing may happen ''in the
middle'' of a polynomial. In a sense, the only way to detect such things
is to use the loop in the algorithm. Of course, for low-degree random
polynomials, this will make the algorithm slower.
For the discussion, I refer to the previous algorithm
`self._roots_from_factorization(...)`
as the ''dense algorithm'', and the new algorithm I implemented as the
''sparse algorithm''.
I did tests:
* In the first one, the roots are computed using the dense algorithm and
then the sparse algorithm, and I compute the ratio of the time it takes.
The ration is `>1` if the sparse algorithm is worst than the dense one.
The left column is the degree, and then 10 tests are performed with random
polynomial of the given degree. As you can see, the sparse algorithm is
often worst, by a factor between 1.5 and 3, and is sometimes better by a
factor of 10 to 25.
* In the second one, I added a condition of the sparsity (i.e. number of
nonzero terms) of the polynomial: `if p.degree() - p.sparsity() -
p.valuation() < 10`, I use the dense algorithm. The timings are then
almost equal for both algorithm for small degrees, but sometimes (not as
often as for the first test) the new algorithm is much better. For large
degrees, we get the same kind of results as in the first test.
As a consequence of these tests, I do not know how the algorithm should be
chosen. Do you have any idea (or any idea of which other tests I should
perform to be able to chose)?
Finally, I also use the fact that a nonzero root of an integer polynomial
should divide its lowest-degree coefficient (constant coefficient if the
valuation is zero) to accelerate the computations. On the one hand, if the
absolute value `cst_coeff` of the constant coefficient is small, the dense
algorithm can compute the product `q` of the `(x-i)*(x+i)` for `1 <= i <=
cst_coeff` and compute the roots of the `gcd` of `self` and `q` instead of
`q`. My tests show that it really improves the computation time. (Note yet
that because of #15790, this cannot work for the moment with sparse
polynomials.) On the other hand, in the sparse algorithm, it is useless to
compute the split of `self` into a list `polys` when the `cst_coeff` is
`1`.
== Tests
=== First test:
{{{
2 [1.80, 2.15, 2.27, 2.14, 1.80, 1.37, 1.37, 2.10, 2.19, 2.19]
4 [2.17, 1.32, 1.41, 2.12, 2.22, 1.89, 2.01, 1.43, 1.85, 2.11]
6 [2.14, 1.38, 0.968, 1.13, 0.466, 2.12, 1.88, 2.15, 1.87, 1.96]
8 [2.07, 1.93, 2.02, 1.83, 2.08, 1.83, 2.57, 1.76, 1.82, 1.95]
10 [1.77, 2.06, 2.10, 2.13, 2.16, 1.78, 0.709, 2.26, 2.16, 2.02]
12 [1.76, 1.79, 0.671, 1.14, 1.26, 2.12, 2.00, 1.97, 1.78, 2.68]
14 [1.66, 0.651, 1.66, 2.07, 2.31, 0.590, 1.13, 0.930, 2.04, 1.66]
16 [2.13, 1.63, 2.24, 0.586, 0.802, 0.772, 1.71, 1.67, 0.592, 2.06]
18 [0.540, 0.667, 2.11, 1.70, 2.19, 1.99, 1.99, 1.98, 0.758, 1.07]
20 [0.568, 1.64, 1.01, 2.17, 1.64, 0.460, 2.07, 2.81, 1.83, 0.501]
22 [0.392, 2.18, 1.63, 1.50, 1.66, 1.95, 1.77, 0.394, 1.53, 2.08]
24 [0.545, 2.86, 1.64, 1.72, 1.94, 2.19, 1.66, 1.56, 0.351, 0.427]
26 [0.381, 1.51, 0.318, 0.394, 1.99, 0.467, 1.52, 1.89, 1.61, 1.53]
28 [1.55, 1.59, 1.95, 0.320, 2.08, 1.48, 1.99, 1.85, 1.47, 1.51]
30 [2.01, 2.02, 2.04, 1.47, 2.02, 0.267, 1.47, 0.339, 2.04, 2.02]
32 [2.01, 1.99, 1.99, 1.99, 2.01, 2.01, 2.01, 2.01, 0.259, 0.288]
34 [2.01, 2.00, 2.01, 0.287, 2.03, 2.01, 0.398, 0.245, 2.01, 1.98]
36 [0.237, 2.00, 2.02, 1.99, 2.02, 2.01, 2.01, 2.01, 1.94, 0.262]
38 [2.00, 0.256, 0.283, 2.01, 2.00, 0.242, 2.01, 2.01, 2.01, 0.235]
40 [1.99, 2.01, 1.98, 2.00, 2.00, 2.01, 2.00, 2.01, 2.01, 2.00]
42 [2.01, 2.00, 2.00, 2.00, 2.00, 2.00, 2.00, 0.218, 1.99, 2.01]
44 [2.00, 2.00, 0.224, 2.00, 2.00, 2.00, 0.597, 2.00, 2.00, 0.203]
46 [0.174, 2.17, 0.170, 2.22, 0.555, 1.84, 0.645, 1.96, 0.188, 2.01]
48 [1.95, 2.03, 1.98, 2.03, 1.92, 1.94, 2.09, 2.00, 2.00, 2.02]
50 [1.97, 1.97, 2.03, 1.99, 2.00, 0.671, 2.00, 2.00, 0.155, 0.149]
52 [1.99, 0.172, 2.00, 2.01, 1.99, 0.173, 0.141, 2.01, 2.00, 1.99]
54 [1.99, 0.119, 2.00, 2.00, 1.99, 0.125, 0.154, 1.99, 1.99, 2.07]
56 [1.99, 2.00, 0.424, 1.98, 2.01, 1.99, 2.04, 2.01, 2.00, 2.00]
58 [2.00, 1.99, 0.590, 2.02, 0.123, 0.122, 2.01, 1.98, 2.00, 1.99]
60 [2.00, 1.99, 0.100, 2.02, 2.05, 2.02, 1.98, 1.95, 0.117, 1.96]
62 [0.0989, 1.97, 1.98, 0.126, 2.00, 1.98, 0.0992, 0.108, 0.120, 1.99]
64 [1.98, 1.98, 0.0956, 0.142, 0.0896, 2.02, 0.110, 0.106, 2.02, 2.00]
66 [2.01, 2.00, 0.210, 2.00, 2.00, 2.00, 1.98, 1.97, 1.99, 0.115]
68 [2.01, 0.0913, 2.00, 2.00, 2.01, 1.98, 1.99, 0.0813, 2.02, 1.99]
70 [0.0866, 0.0826, 2.00, 2.00, 2.00, 0.0900, 2.00, 1.99, 2.00, 0.105]
72 [2.00, 1.99, 0.268, 2.00, 2.00, 2.00, 2.00, 1.99, 2.00, 2.00]
74 [2.00, 0.430, 2.00, 2.00, 2.00, 0.0803, 2.00, 0.0924, 2.03, 2.02]
76 [1.97, 1.99, 1.98, 0.111, 2.00, 2.00, 2.00, 2.01, 0.0905, 0.0919]
78 [2.00, 2.02, 2.00, 1.99, 0.0716, 2.01, 2.00, 2.00, 2.00, 2.00]
80 [1.99, 0.0748, 2.00, 0.437, 1.99, 2.01, 2.00, 0.0731, 2.00, 2.01]
82 [2.00, 1.99, 0.0549, 0.0575, 2.01, 1.99, 0.0642, 0.0519, 1.99, 2.00]
84 [2.00, 0.0547, 1.99, 2.02, 2.01, 2.01, 1.99, 0.0712, 2.00, 2.01]
86 [1.97, 2.02, 2.00, 2.00, 2.01, 2.00, 2.00, 2.00, 0.0562, 2.01]
88 [2.00, 0.0534, 0.0605, 2.00, 2.00, 0.0567, 0.0709, 1.99, 2.00, 2.00]
90 [0.0553, 0.0496, 2.01, 1.99, 2.00, 2.00, 1.98, 0.0476, 2.01, 0.0541]
92 [1.98, 1.99, 2.00, 0.0545, 2.00, 2.00, 2.00, 1.99, 2.01, 2.01]
94 [1.99, 0.0425, 0.0579, 1.96, 2.01, 0.250, 0.106, 0.0561, 1.97, 2.00]
96 [0.0520, 2.00, 1.96, 2.00, 2.00, 0.0508, 2.00, 0.0480, 1.99, 2.01]
98 [0.0458, 0.0515, 0.0415, 2.01, 1.99, 2.01, 0.0510, 0.0526, 0.0455,
2.00]
}}}
=== Second test
{{{
2 [1.02, 1.02, 1.02, 1.02, 1.01, 1.01, 1.02, 1.02, 1.01, 1.02]
4 [1.02, 1.02, 1.02, 1.02, 1.02, 1.02, 1.02, 1.02, 1.02, 1.02]
6 [1.01, 1.03, 1.02, 1.03, 1.02, 1.02, 1.02, 1.02, 1.02, 1.02]
8 [1.01, 1.01, 1.02, 1.01, 1.01, 1.01, 1.02, 1.02, 1.01, 1.02]
10 [1.01, 1.02, 1.01, 1.01, 1.01, 1.01, 1.02, 1.02, 1.01, 1.02]
12 [1.01, 1.01, 1.02, 1.01, 1.01, 1.01, 1.01, 1.01, 1.01, 1.01]
14 [1.01, 1.01, 1.01, 1.02, 1.01, 1.01, 1.01, 1.02, 1.01, 1.01]
16 [1.01, 1.01, 1.01, 1.01, 1.01, 1.01, 1.01, 1.01, 1.01, 1.01]
18 [1.01, 1.01, 1.01, 1.01, 1.01, 1.01, 1.01, 1.01, 1.01, 1.01]
20 [1.01, 1.01, 1.01, 1.01, 1.00, 1.01, 1.01, 1.01, 1.01, 1.01]
22 [1.00, 1.00, 1.00, 1.01, 1.01, 1.01, 1.01, 1.00, 1.01, 1.00]
24 [1.01, 1.01, 1.01, 1.01, 1.01, 1.01, 1.01, 1.01, 1.00, 1.00]
26 [0.996, 0.966, 1.00, 1.01, 1.01, 1.01, 1.00, 1.00, 1.00, 1.01]
28 [1.01, 1.00, 1.00, 1.01, 1.00, 1.01, 1.01, 1.00, 1.00, 1.00]
30 [1.00, 1.01, 1.00, 1.01, 1.01, 1.01, 1.00, 1.01, 1.01, 1.00]
32 [1.00, 1.06, 1.01, 1.00, 1.00, 1.00, 1.01, 1.00, 1.00, 1.00]
34 [1.00, 1.00, 1.01, 1.00, 1.00, 1.01, 1.00, 1.01, 1.00, 1.01]
36 [1.00, 1.01, 1.01, 1.01, 1.00, 1.00, 1.00, 1.00, 1.00, 1.00]
38 [1.00, 1.00, 1.00, 1.00, 1.00, 1.00, 1.00, 1.00, 1.00, 0.358]
40 [1.01, 1.00, 1.00, 2.01, 1.00, 1.00, 1.00, 1.01, 1.00, 1.00]
42 [1.00, 1.00, 1.01, 1.00, 2.01, 1.00, 1.00, 1.00, 1.00, 1.00]
44 [1.00, 1.00, 1.00, 1.01, 1.00, 1.00, 1.00, 1.00, 1.01, 1.00]
46 [0.150, 1.00, 1.00, 1.00, 1.00, 1.00, 0.196, 1.00, 0.188, 2.00]
48 [0.153, 2.01, 1.01, 2.00, 1.01, 2.00, 1.00, 1.00, 1.00, 1.00]
50 [1.00, 1.00, 1.00, 1.00, 2.01, 1.00, 1.00, 0.163, 1.00, 1.99]
52 [1.00, 1.00, 1.00, 1.00, 0.166, 1.02, 1.00, 1.00, 1.01, 1.00]
54 [1.00, 0.166, 1.00, 1.00, 1.00, 2.01, 2.00, 0.153, 2.00, 0.992]
56 [1.00, 2.00, 1.00, 1.00, 2.01, 0.134, 2.00, 2.00, 0.999, 1.00]
58 [0.604, 0.423, 0.132, 2.00, 1.99, 2.00, 1.00, 1.00, 2.01, 0.119]
60 [1.00, 1.00, 0.117, 2.00, 1.00, 2.00, 2.01, 2.00, 0.119, 1.00]
62 [2.00, 0.151, 2.00, 2.00, 1.00, 0.139, 1.00, 2.00, 2.01, 0.106]
64 [1.99, 2.00, 0.103, 1.99, 2.00, 2.00, 0.120, 1.00, 1.00, 1.00]
66 [2.00, 2.00, 1.99, 2.00, 2.00, 2.00, 2.00, 2.01, 2.00, 1.00]
68 [1.99, 1.99, 1.00, 2.00, 2.00, 1.00, 2.00, 2.00, 0.950, 1.99]
70 [1.98, 2.00, 2.01, 1.00, 1.00, 0.0791, 2.00, 1.00, 0.118, 0.0964]
72 [0.429, 2.00, 2.00, 1.99, 1.98, 2.00, 1.99, 2.00, 0.128, 2.01]
74 [0.0890, 0.0795, 1.99, 2.00, 2.01, 2.00, 1.97, 0.0945, 2.00, 1.00]
76 [1.99, 1.99, 2.01, 2.01, 2.02, 2.01, 0.0878, 2.00, 0.0740, 2.01]
78 [1.00, 2.00, 2.03, 2.00, 1.00, 2.00, 0.0617, 0.0812, 2.00, 1.00]
80 [0.0651, 0.0687, 1.98, 2.00, 1.98, 2.00, 2.00, 0.0696, 0.0791, 0.0770]
82 [2.00, 0.0788, 2.00, 1.99, 0.0828, 2.00, 2.02, 2.00, 0.0669, 2.01]
84 [1.02, 1.99, 2.00, 2.01, 0.318, 2.00, 2.00, 1.99, 2.01, 2.01]
86 [2.00, 0.0669, 2.00, 2.00, 2.00, 1.98, 0.0551, 2.00, 2.00, 0.135]
88 [0.0540, 2.00, 2.00, 2.00, 2.00, 2.00, 2.00, 1.99, 2.00, 0.0682]
90 [2.00, 2.02, 1.91, 2.01, 2.01, 2.00, 2.00, 2.00, 2.00, 2.00]
92 [2.00, 1.98, 2.00, 1.99, 1.99, 2.00, 2.00, 2.00, 2.00, 2.00]
94 [1.00, 0.0574, 2.00, 1.00, 2.00, 2.00, 0.0594, 2.00, 2.00, 2.00]
96 [2.00, 2.00, 2.00, 2.00, 0.0420, 2.00, 2.00, 2.00, 2.01, 2.00]
98 [0.0425, 0.0565, 2.01, 2.00, 2.00, 1.99, 1.99, 2.00, 0.0462, 2.00]
}}}
--
Ticket URL: <http://trac.sagemath.org/ticket/16516#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 unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
