Following your advices, I have created a ticket (#16516
<http://trac.sagemath.org/ticket/16516>) on trac, and pushed a
modification. I changed the Polynomial.roots function to look at the
return value of _roots_univariate_polynomial and I added a method
_roots_univariate_polynomial to IntegerRing_class.
Concerning performance issues, the novel algorithm consists in finding
"gaps" in the exponents of the input polynomial to split it into
lower-degree polynomials. To know whether it is faster to use it, the
only way is to try to find gaps. This computation being very fast, I
decided to apply the new algorithm for all sparse polynomials. Actually,
it could also be used with densely represented polynomials which happen
to be sparse, but detecting this fact requires some (quite fast)
computations.
The ticket #16516 now needs review.
Thanks to everybody for the help,
Bruno
Le ven. 20 juin 2014 06:29:35 CEST, Nils Bruin a écrit :
On Friday, June 13, 2014 6:28:17 PM UTC-4, Bruno Grenet wrote:
Dear all,
I am new to Sage development and I'd like some help or advice for
the following task:
There is right now no specific algorithm for computing roots of
Sparse Polynomials in Sage. Such algorithms exist, at least for
polynomials over Z [CuKoiSma99], Q or any finite extension of Q
[Len99], F_p [BiCheRo13] and R [Sag14]. For instance, the first
two algorithms are polynomial-time algorithms in the sparse size
of the polynomial.
I have implemented the first algorithm (over Z). My implementation
is certainly not be perfect, but at least I am able to compute the
integer roots of polynomials of degree ~100 000 with ~5000 nonzero
monomials in less than .1s (on my laptop). The current algorithms
in Sage are totally unable to handle such polynomials.
Now comes my question, which is basically: How to introduce this
new code into Sage?
More specifically, the "roots()" function is defined in
rings/polynomial/polynomial_element.pyx where a selection of
algorithm is made. If I understand correctly, for a polynomial
over ZZ (be it sparse or not), the selection goes through the
condition "K.is_integral_domain()" (line 5799) and then the roots
are computing using "_roots_from_factorization" (line 5809).
There, factoring the input polynomial is (in my cases) hopeless
due to its degree.
What I'd like to do is to branch a new algorithm there. So my more
specific question: Where should the new algorithm go? A solution
may be to have somewhere a specific code for the sparse
polynomials over ZZ, and there put a a function
roots(self,multiplicities=True) to avoid going into the "big"
roots function from rings/polynomial/polynomial_element.pyx.
You are facing two tasks here:
- making the algorithm available in sage. This can be via a function
in some module somewhere or as a method on some class, in this case
sparse polynomials over ZZ. If we have a "sparse polynomials over ZZ"
type, this routine should probably go there.
- letting sage automatically choose to use your algorithm in some
cases. You'd need some extensive testing that you can efficiently
determine criteria and cutoffs for when to use your code and when to
stick with other methods. It may well be that you cannot make this
decision at negligible cost in all situations. In that case, the right
decision is to *not* let sage make the choice automatically and
instead to just keep it available via a specific function/method
and/or via an "algorithm" option on the normal root finding code.
I'd say first do step one. You are saying your code still can use
improvement, so probably you're not quite ready for that yet.
Only once the algorithm is available for manual selection should you
even start with considering the heuristics (if any!) for choosing the
algorithm automatically.
I think it's really nice to extend sage's sparse polynomial support.
--
You received this message because you are subscribed to the Google
Groups "sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send
an email to sage-devel+unsubscr...@googlegroups.com
<mailto:sage-devel+unsubscr...@googlegroups.com>.
To post to this group, send email to sage-devel@googlegroups.com
<mailto:sage-devel@googlegroups.com>.
Visit this group at http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.
--
You received this message because you are subscribed to the Google Groups
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.
