#16516: Faster roots computation for sparse polynomials over ZZ
-------------------------------------+-------------------------------------
Reporter: bruno | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.4
Component: commutative | Resolution:
algebra | Merged in:
Keywords: roots, sparse | Reviewers:
polynomial | Work issues:
Authors: Bruno Grenet | Commit:
Report Upstream: N/A | d72a8f1554235a389d8c42e278d3779895d568b5
Branch: | Stopgaps:
u/bruno/faster_roots_computation_for_sparse_polynomials_over_zz|
Dependencies: |
-------------------------------------+-------------------------------------
Changes (by bruno):
* status: needs_work => needs_review
Comment:
I changed the following aspects of my code:
* Replace each `<>` by `!=`
* Add `sig_on`/`sig_off`'s
* Remove the tests on the constant coefficient: This was a hack to speed
up some computations (when the constant coefficient is `±1`), but this
leads to the slow down noticed by [comment:38 jdemeyer] for the roots of
`(x-1)^2000`. It had nothing to do with the `"sparse"` algorithm. (More on
this in the note below.)
* I changed the automatic choice of algorithm: Based on extensive tests
(not exhaustive though, by definition), it appears that the slow-down that
exists in some examples using the `"sparse"` algorithm rather than the
`"dense"` algorithm becomes negligible from around degree `100`, with
never more that 10% slow down, and almost always <1% (and of course quite
often there is a speed-up!). Note that I also add a shortcut for
completely dense polynomials (with density `1`) when we are sure the
`"dense"` algorithm will be used as a fallback to avoid some useless
(though not expensive) computations.
**Almost unrelated note on the "constant coefficient trick":** As written
above, I have removed some tests that were made on the constant
coefficient. The trick I used is that the constant coefficient is the
product of the roots, thus if a polynomial has a "small" constant
coefficient, it can be interesting to use some kind of brute force
algorithm to discover these roots, or to first take a gcd before computing
the roots. I removed the trick since it has some drawbacks. If it is more
correctly written, it may become useful but in any case, it should be the
object of another ticket. Maybe some day...
--
Ticket URL: <http://trac.sagemath.org/ticket/16516#comment:42>
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.
