Search code examples
c++gmpgslpolynomials

Polynomial solving with arbitrary precision

We have been using GSL to solve polynomials. However, we wish to use arbitrary precision to solve polynomials. I looked into GMP and Boost multi-precision library, however, I couldn't find any routine for polynomial solving with floating point coefficients.

  1. Does there exist any library, which is free and open-source, for solving polynomials with arbitrary precision or a very high precision (>200 positions after decimal)?

  2. Is it possible to make use of GSL polynomial solver routine with the change in data-type to be that of GMP arbitrary precision?

  3. Would it rather be easy to write polynomial solver, using one of the standard algorithms, with GMP arbitrary precision data types?

Please feel free to comment if it is not clear.

Solution
    1. MPSolve provides a library to solve polynomials using multi-precision. Internally it uses GMP.

    Following can be observed:

    • The computations can be done in integer, rational, and floating-point arbitrary precision.
    • The coefficients of the polynomial and various other options are given as input through a file. One can rig the original code to directly call the function from their own program.
    • The solutions can be reported in various formats, such as exponential, only real, etc.
    • The solver has been verified for several standard polynomial test cases and checks out.
    • The solver internally uses random number which is seeded through the /dev/random on a Linux machine. This causes a problem that the solver is slow on the subsequent runs as the entropy generated is not enough before the start of the future runs. This could be bypassed by replacing it with standard pseudo-random generators.
    • An attempt was made to integrate the solver as a library. However, serious segmentation faults occur which were difficult to debug. Hence, the solver was being used by calling its executable. Note: this is just from my experience and hopefully it can be done in a better way.
    • A new C++ version is being developed and, hopefully, shall resolve these issues.
    1. It is tedious to fork the GSL polynomial solver to use GMP data-type. It will be rather easier and also the code will be more in one's control and understanding, if the solver is written (see no. 3).
    1. As suggested in the answer, GMP and MPFR multi-precision libraries can be used and a polynomial solver can be written using standard polynomial solving techniques, such as Jenkins-Traub Algorithm or QR based techniques.

    Boost C++ Libraries provide wrappers for using GMP and MPFR which might be very handy to use.