#16516: Faster roots computation for sparse polynomials over ZZ
-------------------------------------+-------------------------------------
Reporter: bruno | Owner:
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-6.3
Component: commutative | Resolution:
algebra | Merged in:
Keywords: roots, sparse | Reviewers:
polynomial | Work issues:
Authors: Bruno Grenet | Commit:
Report Upstream: N/A | be6deca10dd8d25ace0e9d821c6cc5551ca8d47f
Branch: | Stopgaps:
u/bruno/faster_roots_computation_for_sparse_polynomials_over_zz|
Dependencies: |
-------------------------------------+-------------------------------------
Comment (by bruno):
Below are my answers to Vincent's comments:
1) ''`==` vs `is`:'' Should be OK now
2) ''Comment the code:'' Done
3) ''Syntax error in the doc:'' Done. "make doc" works now.
4) ''Method `sparsity` in "polynomial_element.pyx":'' I totally changed
the method since it was obviously badly written. I wanted to avoid
constructing a list of nonzero monomials to get a better complexity but
this was not a good idea! I hope the new (much simpler!) version is fine.
I add quite a lot of tests in this function (as well as in others).
5) ''Name of the method `sparsity`:'' I would say that this name is fairly
standard. It may be used more often to speak about "the fact of being
sparse or not" rather than "the number of nonzero monomials", but still
you can find this term in several papers (''cf'' for instance
http://www.math.purdue.edu/~sbasu/ccc04.ps or http://eccc.hpi-
web.de/report/2014/056/download/). Further, I find the term nicer than
using a periphrasis but I let you tell me what you think is best. I don't
mind changing the term if it appears not to be appropriate. I looked at
similar terms in matrix_sparse.pyx and related files. I appears that
`num_nonzero` is used a bit, and `sparsity` is only used in comments to
speak about "the fact of being sparse or not".
6) ''`range` vs `xrange`, and def `k` as `int`:'' I defined `k` (as well
as other variables `i` and `j`) as `int`, but I let `xrange` rather than
`range`. I did not notice the promised big gain though.
7) ''`.extend()` does not return anything:'' I note. Yet I removed the
case "dense_with_gcd" since I have not been able to build a case where
this is faster than the algorithm "dense".
8) ''`content` issue:'' I let a distinction between sparse and dense
polynomials until the issue is solved.
--
Ticket URL: <http://trac.sagemath.org/ticket/16516#comment:13>
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.
