#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 | f344cdc5b4a9e316a52f5372a30a3db1ac5043ab
Branch: | Stopgaps:
u/bruno/faster_roots_computation_for_sparse_polynomials_over_zz|
Dependencies: |
-------------------------------------+-------------------------------------
Changes (by vdelecroix):
* status: needs_review => needs_work
Comment:
Hi,
'''Global remarks:'''
1) You seem to have a global problem with the difference between `==` and
`is` so have a look at [[http://stackoverflow.com/questions/13650293
/python-is-operator|python-is-operator on stackoverflow]].
2)
Comment your code when it is complicated like
{{{
if cst_coeff is not ZZ(1):
i_min=0
polys=[]
for i in xrange(1,k):
if e[i]-e[i-1] > c_max.nbits():
polys.append(R(p[ e[i_min]:e[i] ].shift(-e[i_min])))
i_min=i
c_max=c[i].abs()
else:
c_max=max(c[i].abs(),c_max)
polys.append(R(p[ e[i_min]:1+e[k-1] ].shift(-e[i_min])))
}}}
open softwares should also be readable softwares
3) You have syntax error in the documentation (which will create error
when you try to build the documentation with "make doc"):
{{{
``algorithm'' -- the algorithm to use
}}}
should be
{{{
``algorithm`` -- the algorithm to use
}}}
ie open and close with back quotes.
'''Specific ones:'''
4) In the method sparsity that you implemented in
"polynomial_element.pyx", the variable c is not initialized. So
{{{
sage: K.<x>=QQ[]
sage: (x^7 + x^3 + 1).sparsity()
32665
}}}
Moreover, the following test is not safe at all
{{{
if l.pop() is not zero
}}}
you can not believe that the zero always occupy the same memory. For
instance
{{{
sage: K = QQ['x']
sage: K.zero().constant_coefficient() is QQ.zero()
False
}}}
Moreover, using try except is totally useless in that case... You might be
inspired by the implementation of `coefficients`. Hopefully, I am not the
one who teach you programming at school ;-) Please test this method with
other base rings (at least QQ, QQbar, ZZ/nZZ GF(p), GF(p^n)).
5) Are you sure that the term sparsity is standard? I would rather go for
something more explicit like "num_nonzero_coefficients" or something
similar. I hoped to find a similar method in matrices but did not find it.
6) In your function `_roots_univariate_polynomial`, there is no gain in
using `xrange` instead of `range`. But there will be a '''big''' one if
you define `k` as an int!
6) Using the `gcd` from `sage.rings.arith` (in the line `p=gcd(p,q)`) is
slow compared to `p = p.gcd(q)`. (and do not forget to remove the import)
Vincent
Vincent
--
Ticket URL: <http://trac.sagemath.org/ticket/16516#comment:9>
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.
