MPSolve 3.2.1
Loading...
Searching...
No Matches
General documentation

What is MPSolve

MPSolve is a C library that allow to find solution to univariate polynomial equations with arbitrary precision.

More precisely, MPSolve can handle polynomials but not necessarly in their monomial form. Support is now given even for secular equation and more implicit representation are scheduled to be added later.

Installing MPSolve system-wide

First, you need to get MPSolve. You can get the latest release via git or download it via http grabbing it at http://www.dm.unipi.it/... If you downloaded the source tarball this operation is pretty straightforward. You can simply unpack it and then

./configure
make
[sudo] make install

These commands will install the library libmps.so in your system library directory. In this way you will be able compile your source file using a command similar to

gcc -o myprogram -lmps -lgmp -lm myprogram.c.

MPSolve extended arithmetic types

To perform its computations MPSolve uses some more types than standard C does. You will need to interact with these to give and obtain data from MPSolve.

There are three main category of types that you will be required to deal with:

  1. Standard floating point doubles;
  2. DPE types;
  3. Multiprecision GMP types

Floating point simple types

There is clearly nothing to explain about floating point doubles, but MPSolve needs to deal with complex floating point and it uses a type called cplx_t that is nothing more than a struct with two double field, r and i that represents the real and imaginary part of the given complex number. You should access these fields with macro provided in this way:

cplx_t my_complex_number;
double theta = 0.5;
cplx_Re (my_complex_number) = cos (theta);
cplx_Im (my_complex_number) = sin (theta);

Some standard complex number are provided for convenicence, such as cplx_one and cplx_zero.

To get an idea of all the routines that you can use you can read the mt.h header file. But for a simple start, the routines that you will need are cplx_add(), cplx_sub(), cplx_mul() and cplx_div(). I think that it's pretty clear what they do.

The DPE types

The DPE are have the same precision of the doubles but allow the exponent to be much larger; the exponent is stored as a long value so the maximum reachable one is LONG_MAX, while the minimum is LONG_MIN.

In the mt library that is embedded in MPSolve two version of the DPE types are provided: the real and the complex one. They are called RDPE and CDPE, respectively.

The function used to handle these types are almost the same of the complex one case, so we will not cover they extensively here.

GMP types

GMP types are used to represent multiprecision data that is used to get arbitrary high precision approximation of the roots. See http://gmplib.org for details on the use of GMP.

Using the libmps interface

The library provides some useful routine to interact with the polynomial solver. Most of them are designed to handle polynomial definition and are implemented in interface.c

This is a typical example of how you'll be using MPSolve.

// Select the degree
int n = 4;
// Allocate a new mps_context that hold the status of a computation.
// Its field should never be accessed directly but only via appropriate
//functions.
mps_context * status = mps_context_new ();
// Create a polynomial that will be solved
mps_monomial_poly * poly = mps_monomial_poly_new (status, n);
// Set the coefficients. We will solve x^n - 1 in here
mps_monomial_poly_set_coefficient_int (status, poly, 0, -1, 0);
mps_monomial_poly_set_coefficient_int (status, poly, n, 1, 0);
// Select some common output options, i.e. 512 bits of precision
// (more or less 200 digits guaranteed) and approximation goal.
mps_context_set_output_prec (status, 512);
mps_context_set_output_goal (status, MPS_OUTPUT_GOAL_APPROXIMATE);
// Solve the polynomial
mps_context_set_input_poly (status, poly);
mps_mpsolve (status);
// Get the roots in a <code>cplx_t</code> vector. Please note that
// this make completely useless to have asked 512 bits of output
// precision, and you should use mps_context_get_roots_m() to get
// multiprecision approximation of the roots.
cplx_t * results = cplx_valloc (n);
mps_context_get_roots_d (status, &results, NULL);
// Free the data used. This will free the monomial_poly if you have
// not done it by yourself.
mps_context_free (status);
cplx_vfree (results);
this struct holds the state of the mps computation
Definition: context.h:55
Data regarding a polynomial represented in the monomial base.
Definition: monomial-poly.h:44

As pointed out in the comments, this piece of code is not that smart, since it asks for a lot of digits in output, but then discard all this good by copying the roots in floating point cplx_t types.

Please see the documentation of mps_context_get_roots_m() for a better way to get the results. It was not used in example in order to keep it short and clear.

How to include libmps

In general libmps will be usable by including the header file mps/mps.h. Please note that almost all structures defined in MPSolve will be available only as incomplete declarations, so they should be used with pointers, and manipulated with available functions.

Remember to include always mps/mps.h and not the other headers in the directory. This is not supported and not guaranteed to work.

For example you can instantiate a pointer to a new mps_context with the function mps_context_new(), add the input to it, solve the polynoial with mps_mpsolve() and then free its resources with mps_context_free().

The data structures that will be mostly used are:

  1. mps_context: This structure holds the state of the computation and must be instanciated for every polynomial solving operation. After allocating a pointer to an mps_context you should, generally,:
    1. Set the input data and output requirements (i.e. the input polynomial, the desired output digits and goal, ...)
    2. Ask libmps to solve the polynomial by calling mps_mpsolve()
    3. Retrieve the computed data with the appropriate accessors functions mps_context_get_roots_d() or mps_context_get_roots_m(). All the functions usable on an mps_context pointer are available in status.h.
  2. mps_monomial_poly: A polynomial given by its coefficients. Can be allocated with mps_monomial_poly_new() and manipulated with the functions in monomial-poly.h. Once it is the desired polynomial to solve you can call mps_context_set_input_poly() to set it as the active polynomial to solve.
  3. mps_secular_equation: The same as the monomial poly, but for secular equations. See secular-equation.h for some functions to allocate, free and manipulate them.

Calling MPSolve asynchronously

Desktop application using MPSolve to solve polynomials may want to call a non-blocking version of mps_mpsolve(). This is provided inside the package as mps_mpsolve_async().

This routine will return a mps_handle pointer that can be used to wait for the result by calling mps_mpsolve_wait() on it.