I'm looking for the best way of implementing the following algorithm: consider the set of all polynomials with a high degree (say, degree 30) whose coefficients ranges from a given set of values (say, {-1,0,1}). To any polynomial of this set, I want to apply some test (say, to verify if all its roots are real). If the polynomial pass in the test, I want to print it and its roots (numerically evaluated). If it does not pass, do nothing. (actually, my test is somewhat more complicated than this, but this is enough to clarify my point).

In the example above, I do not need to evaluate the roots of each polynomial in the set to verify if its roots are all real or not, since I can use instead, for instance, the Sturm theorem, or some numerical algorithm for isolating the roots intervals, and also other intermediate filter-tests as Descartes's rule of sign and so on. It is only when the polynomial pass on all these tests—so that I'm sure that all its roots are real—that I want to print the polynomial and its roots.

The problem is the following: since the degree is very high, there are too many polynomials to test for. This takes a high computational time even to run the list only. Therefore, I want to know what is the best language to implement the code and what is the best way of generating the list of polynomials for run the tests. Currently, I implemented the code on Maple, through a nested loop structure (one for loop for each polynomial coefficient), but I believe that there is a smarter way to do that. Maybe some way of parallelizing the loops would be desirable.

I do not master any programing language, but I can learn fast. I'm comfortable with Maple, Mathematica and I'm learning SageMath. I know a little of Python as well and I think that Cython is a good idea to implement the code, but I'm not sure … Any help will be very welcome and I thank you all in advance.


1 Answer 1


You can use backtracking to generate your polynomials. This can be parallelized in pretty much any language you choose. You may also want to call the Sturm sequence finder in the FLINT library from your script for speed.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.