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.