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.

I have side questions, which may improve my code (or my tests):

- S.random_element() for S a sparse_polynomial ring return by defaut a degree-2 polynomial. For sparse polynomials, wouldn't it make sense to return a polynomial of "high" degree (to be determined) but with "few" nonzero monomials? Again, I have a code for that that I can include.

- How exactly is stored a Sparse Polynomial? I tried to follow the "__init__" functions but I was unable to finally understand the real representation of these objects. I suspect this is a dictionary (or something approaching) with the keys being the exponents and the values being the coefficients. In such case, what is the fastest way to access these elements?

- The algorithm I implemented uses some auxiliary functions that are not of real interest outside the algorithm. How should I do to avoid this functions be available for the users?

Thanks in advance!
Bruno Grenet

===

References:
[CuKoiSma99]
F. Cucker, P. Koiran, and S. Smale. A polynomial time algorithm for Diophantine equations in one variable. /J. Symb. Comput./, 27(1):21--30, 1999.

[Len99]
H. Lenstra Jr. On the factorization of lacunary polynomials. In /Number theory in progress/, pages 277--291. De Gruyter, 1999.

[BiCheRo13]
J. Bi, Q. Cheng, and J. M. Rojas. /Sub-Linear Root Detection, and New Hardness Results, for Sparse Polynomials Over Finite Fields/. In Proc. ISSAC, 2013. arXiv:1204.1113.

[Sag14]
M. Sagraloff. A/Near-Optimal Algorithm for Computing Real Roots of Sparse Polynomials./ In Proc. ISSAC, 2014. arXiv:1401.6011






--
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.

Reply via email to