Faster roots computation for sparse polynomials over ZZ

[bgrenet]

Algorithms exist for the computation of the roots of sparse polynomials, which are much faster than the "generic" algorithms which work for dense polynomials.

In this ticket, I implement one of these algorithms, for integer roots of sparse polynomials over ZZ.

Component: commutative algebra

Keywords: roots, sparse polynomial

Author: Bruno Grenet

Branch/Commit: 686d2b3

Reviewer: Vincent Delecroix, Travis Scrimshaw, Jeroen Demeyer

Issue created by migration from https://trac.sagemath.org/ticket/16516

[bgrenet]

Description changed:

--- 
+++ 
@@ -1,3 +1,3 @@
 Algorithms exist for the computation of the roots of sparse polynomials, which are much faster than the "generic" algorithms which work for dense polynomials.
 
-In this ticket, I implement one of these algorithms, for integer roots of sparse polynomials over ZZ.
+In this ticket, I implement one of these algorithms, for integer roots of sparse polynomials over ZZ and over QQ.

[bgrenet]

Branch: u/bruno/faster_roots_computation_for_sparse_polynomials_over_zz

[bgrenet]

Commit: 920c16e

[bgrenet]

Description changed:

--- 
+++ 
@@ -1,3 +1,3 @@
 Algorithms exist for the computation of the roots of sparse polynomials, which are much faster than the "generic" algorithms which work for dense polynomials.
 
-In this ticket, I implement one of these algorithms, for integer roots of sparse polynomials over ZZ and over QQ.
+In this ticket, I implement one of these algorithms, for integer roots of sparse polynomials over ZZ.

[sagetrac-git]

Changed commit from 920c16e to e725544

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

e725544

New function for computing roots of sparse polynomials over ZZ

[videlec]

comment:5

Hi Bruno,

It seems reasonable to have it in integer_ring.pyx. And I think that it would be good to allow it for dense polynomial as well. You certainly know what is the good measure of sparseness... you could implement a method .density() of .sparness_XYZ() on polynomials that would help you to find the good threshold for the different algorithms.

For better code, please:

• remove the trailing whitespaces
• there is no need for ; at the end of each line
• for list update it is better to use .append(x) for adding one element and .extend(iterator) for extending with several elements
• not ring is None -> ring is not None (the is not is a Python operator)

And you must provide timings to see whether it is better with your code for small input. You can use the command timeit as in

sage: R.<T> = ZZ[]
sage: p = R.random_element(degree=10)
sage: timeit("p.roots()")
625 loops, best of 3: 223 µs per loop

It would be nice to make the following works:

sage: R.<T> = PolynomialRing(ZZ, sparse=True)
sage: p = R.random_element(degree=10)
sage: p.roots(QQbar)
Traceback (most recent call last):
...
AttributeError: 'Polynomial_generic_sparse' object has no attribute 'gcd'

It will be a nice thing to have in Sage!

More remarks to come,
Vincent

[sagetrac-git]

Changed commit from e725544 to f344cdc