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