     [file version.texi not included]

This manual is for MPFRCX, a library for the arithmetic of polynomials with multiple precision real or complex floating point coefficients, version VERSION of UPDATED-MONTH.

Copyright © 2007, 2008, 2009, 2010, 2011, 2012, 2017, 2018, 2020 Andreas Enge

     Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.3 or any later version published by the Free Software Foundation; with no Invariant Sections. A copy of the license is included in the section entitled ``GNU Free Documentation License.''

MPFRCX
******

This manual documents how to install and use the Multiple Precision Real and Complex Polynomial Library, version VERSION as of UPDATED-MONTH.

MPFRCX Copying Conditions
*************************

The MPFRCX Library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version, see the file COPYING.LESSER.

The MPFRCX Library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public License for more details.

Introduction to MPFRCX
**********************

MPFRCX is a portable library written in C for arithmetic of polynomials with arbitrary precision real or complex floating point coefficients. It is based on the GNU MP, the MPFR and the MPC libraries.

Installing MPFRCX
*****************

To build MPFRCX, you first have to install GNU MP, MPFR and MPC on your computer. For MPC, the minimal supported version is 1.0; the minimally required versions of GNU MP and MPFR depend on the MPC version used. You need a C compiler, preferably GCC, but any reasonable compiler should work.  And you need a standard Unix make program, plus some other standard Unix utility programs.

Here are the steps needed to install the library on Unix systems:

 1. tar xzf mpfrcx-VERSION.tar.gz

 2. cd mpfrcx-VERSION

 3. ./configure

     if GMP, MPFR and MPC are installed into standard directories, that is, directories that are searched by default by the compiler and the linking tools.

     ./configure --with-gmp=<gmp_install_dir>

     is used to indicate a different location where GMP is installed.

     ./configure --with-mpfr=<mpfr_install_dir>

     is used to indicate a different location where MPFR is installed.

     ./configure --with-mpc=<mpc_install_dir>

     is used to indicate a different location where MPC is installed.

     ./configure --with-gmp=<gmp_install_dir> --with-mpfr=<mpfr_install_dir> --with-mpc=<mpc_install_dir>

     is used to indicate different locations of GMP, MPFR and MPC.

     Warning! Do not use these options if you have CPPFLAGS and/or LDFLAGS containing a -I or -L option with a directory that contains a GMP header or library file, as these options just add -I and -L options to CPPFLAGS and LDFLAGS after the ones that are currently declared, so that DIR will have a lower precedence. Also, this may not work if DIR is a system directory.

 4. make

     This compiles MPFRCX in the working directory.

 5. make check

     This will make sure MPFRCX was built correctly.

     If you get error messages, please report them to andreas.enge@inria.fr (see Reporting Bugs, for information on what to include in useful bug reports).

 6. make install

     This will copy the file mpfrcx.h to the directory /usr/local/include, the file libmpfrcx.a to the directory /usr/local/lib, and the file mpfrcx.info to the directory /usr/local/share/info (or if you passed the --prefix option to configure, using the prefix directory given as argument to --prefix instead of /usr/local). Note: you need write permissions on these directories.

Other `make' Targets
====================

There are some other useful make targets:

  * mpfrcx.pdf or pdf inside the docsubdirectory

     Create a PDF version of the manual, in mpfrcx.pdf.

  * mpfrcx.html or html inside the docsubdirectory

     Create an HTML version of the manual, in several pages in the directory mpfrcx.html; if you want only one output HTML file, then type makeinfo --html --no-split mpfrcx.texi instead.

  * clean

     Delete all object files and archive files, but not the configuration files.

  * distclean

     Delete all files not included in the distribution.

  * uninstall

     Delete all files copied by make install.

Reporting Bugs
**************

If you think you have found a bug in the MPFRCX library, please investigate and report it.

There are a few things you should take into account when you compose your bug report. Please send us a minimal test case that makes it possible for us to reproduce the bug. Include instructions on how to run the test case, and why the result differs from what you would expect.

Please include compiler version information in your bug report. This can be extracted using cc -V on some machines, or, if you are using gcc, gcc -v.  Also, include the output from uname -a.

Send your bug report to: andreas.enge@inria.fr.

Beware that the MPFRCX library is in a very early development stage, and some functions, while working correctly, may be terribly inefficient. You might want to send an e-mail to the above address if you are interested in one of the more exotic functions to enquire about its status.

MPFRCX Basics
*************

MPFRCX provides types and functions for working with univariate polynomials, taking as coefficients either real or complex floating point numbers of arbitrary precision. The functions are collected in the library libmpfrcx.a and declared in the header file mpfrcx.h.

Nomenclature and Types
======================

A real polynomial is a polynomial whose coefficients are of type mpfr_t. The C data type for such objects is mpfrx_t. All coefficients are supposed to have the same floating point precision. Besides its list of coefficients, a variable of type mpfrx_t contains the degree of the polynomial as an int and the precision of its coefficients as an mp_prec_t. If the degree of a polynomial increases, its list of coefficients is lengthened accordingly; on the other hand, if the degree decreases, the memory allocated to the now superfluous coefficients is not freed, unless explicitly requested by a call to mpfrx_realloc, see Initialisation Functions.

A complex polynomial is a polynomial whose coefficients are of type mpc_t. The C data type for such objects is mpcx_t. All coefficients are supposed to have the same floating point precision, and this both for their real and their imaginary parts. Otherwise, complex polynomials behave like real ones.

When calling the functions described in the following, arguments of type mpfrx_ptr or mpfrx_srcptr stand for arbitrary variables of type mpfrx_t; the former may be modified by the function, the latter not. The same holds for mpcx_ptr and mpcx_srcptr.

Notice that unlike for operations with real numbers of type mpfr_t and complex numbers of type mpc_t, there are no rounding modes for operations with polynomials and no precise semantics; polynomial arithmetic is realised by calls to functions on the coefficients, which may accumulate rounding errors.

Function Classes
================

Functions  and macros working with real polynomials begin with mpfrx_, those treating complex polynomials begin with mpcx_. For the time being, there are no mixed operations.

MPFRCX Variable Conventions
===========================

As a general rule, all MPFRCX functions expect output arguments before input arguments, in analogy with GMP, MPFR and MPC.

MPFRCX allows you to use the same variable for both input and output in the same expression.  For example, the main function for multiplication of real polynomials, mpfrx_mul, can be used like this: mpfrx_mul (f, f, f) to replace F by its square.

Before you can assign to an MPFRCX variable, you need to initialise it by calling one of the special initialisation functions.  When you are done with a variable, you need to clear it out, using one of the functions for that purpose.

A variable should be initialised only once; after a variable has been initialised, values may be assigned to it any number of times.

Functions
*********

All publicly visible functions exist with the same behaviour for real or complex polynomials; their names start with mpfrx_ resp. mpcx_. For the time being, the only specific functions concern the fast Fourier transform and are internal to the library.

Initialisation Functions
========================

An mpfrx_t or mpcx_t object must be initialised before storing the first value in it, using the function mpfrx_init or mpcx_init.

 -- Function: void mpfrx_init (mpfrx_ptr F, const int SIZE, const mp_prec_t PREC)
 -- Function: void mpcx_init (mpcx_ptr F, const int SIZE, const mp_prec_t PREC)
     Initialise F with initial space for SIZE coefficients of precision PREC, and set it to zero. It is possible to assign a polynomial with more than SIZE coefficients to F later on; the size of F is then increased automatically. Beware that SIZE=d+1 coefficients are needed to store a polynomial of degree d.

 -- Function: void mpfrx_clear (mpfrx_ptr Z)
 -- Function: void mpcx_clear (mpcx_ptr Z)
     Free the space currently occupied by Z.  Make sure to call this function on each variable precisely once.

 -- Function: void mpfrx_realloc (mpfrx_ptr F, const int SIZE)
 -- Function: void mpcx_realloc (mpcx_ptr F, const int SIZE)
     Changes the number of coefficients stored in F to SIZE, which may be more or less than (or equal to) the previous size, while preserving the precision of the coefficients. If F still fits (that is, its degree is at most SIZE-1), its value is preserved, otherwise, it is replaced by 0.

Assignment Functions
====================

These functions assign new values to already initialised polynomials (see Initialisation Functions).

 -- Function: void mpfrx_set (mpfrx_ptr H, mpfrx_srcptr F)
 -- Function: void mpcx_set (mpcx_ptr H, mpcx_srcptr F)
 -- Function: void mpcx_set_frx (mpcx_ptr H, mpfrx_srcptr F)
     Set the value of H from F. The precision of H is preserved, and the coefficients of F are rounded if the target precision is lower.

 -- Function: void mpfrx_swap (mpfrx_ptr F, mpfrx_ptr G)
 -- Function: void mpcx_swap (mpcx_ptr F, mpcx_ptr G)
     Swap the contents of the variables F and G. If their coefficients do not have the same precision, precisions are swapped as well. The effect is thus not the same as obtained by several calls to mpfrx_set or mpcx_set, respectively, with an additional temporary variable, which would keep the respective precisions of F and G unchanged.

Combined Initialisation and Assignment Functions
================================================

 -- Function: void mpfrx_init_set (mpfrx_ptr H, mpfrx_srcptr F)
 -- Function: void mpcx_init_set (mpcx_ptr H, mpcx_srcptr F)
     Initialise H with the same precision as F and set its value from F.

Access Functions
================

 -- Macro: int mpfrx_get_prec (mpfrx_srcptr F)
 -- Macro: int mpcx_get_prec (mpcx_srcptr F)
     Return the common precision of the coefficients of F.

 -- Function: void mpfrx_set_prec (mpfrx_ptr F, const mp_prec_t PREC)
 -- Function: void mpcx_set_prec (mpcx_ptr F, const mp_prc_t PREC)
     Set the precision of the coefficients of F to PREC and replace F by the zero polynomial. The effect is similar to a call to mpfrx_clear resp. mpcx_clear followed by a call to mpfrx_init resp. mpcx_init, but the number of coefficients in the polynomial is kept.

 -- Macro: int mpfrx_get_deg (mpfrx_srcptr F)
 -- Macro: int mpcx_get_deg (mpcx_srcptr F)
     Return the degree of F, which is -1 for the zero polynomial.

 -- Function: void mpfrx_set_deg (mpfrx_ptr F, const int DEG)
 -- Function: void mpcx_set_deg (mpcx_ptr F, const int DEG)
     Set the degree of F to DEG while preserving the coefficients. If the degree increases, the new coefficients are set to NaN and need to be set manually before computing with the variable, see mpfrx_set_coeff and mpcx_set_coeff. If necessary, new coefficients are allocated.

 -- Function: mpfr_ptr mpfrx_get_coeff (mpfrx_srcptr F, const unsigned int I)
 -- Function: mpc_ptr mpcx_get_coeff (mpcx_srcptr F, const unsigned int I)
     Return a pointer to coefficient I of F, or NULL if the degree of F is less than I.

 -- Function: void mpfrx_set_coeff (mpfrx_ptr F, const unsigned int I, mpfr_srcptr COEFF)
 -- Function: void mpcx_set_coeff (mpcx_ptr F, const unsigned int I, mpc_scrptr COEFF)
     Set the coefficient I of F to COEFF. If the current degree of F is smaller than I, then the degree of F is set to I; intermediate coefficients are set to NaN.

Comparison and Miscellaneous Functions
======================================

 -- Function: int mpfrx_cmp (mpfrx_srcptr F, mpfrx_srcptr G)
 -- Function: int mpcx_cmp (mpcx_srcptr F, mpcx_srcptr G)
     Return 0 if F equals G and -1 if not. The coefficients of F and G are compared one by one; so even if the two polynomials have different precisions, they may be recognised as equal.

 -- Function: void mpfrx_urandom (mpfrx_ptr F, int DEG, gmp_rand_state_t STATE)
 -- Function: void mpcx_urandom (mpcx_ptr F, int DEG, gmp_rand_state_t STATE)
     If DEG<0, set F to be the 0 polynomial. Otherwise, generate a uniformly distributed random degree between 0 and DEG (inclusive), and a random polynomial of this degree. Each coefficient is chosen uniformly at random in the unit interval [0, 1] resp. the unit square [0, 1] x [0, 1]; except for the leading coefficient, which cannot be 0.

     STATE is a gmp_randstate_t structure which should be created using the GMP rand_init function, see the GMP manual.

 -- Macro: const int MPFRCX_VERSION_MAJOR
 -- Macro: const int MPFRCX_VERSION_MINOR
 -- Macro: const int MPFRCX_VERSION_PATCHLEVEL
 -- Macro: const char* MPFRCX_VERSION_STRING

The major, minor and patchlevel version number of the library. These are concatenated and separated by '.' to form the version string; '-dev' is added to the version string of development snapshots.

 -- Function: const char * mpfrcx_get_version (void)
     Return the MPFRCX version as a null-terminated string.

Input and Output Functions
==========================

The following function writes a polynomial to an output stream. When using it, you need to include stdio.h before mpfrcx.h.

 -- Function: size_t mpfrx_out_str (FILE* STREAM, int BASE, size_t N_DIGITS, mpfrx_srcptr F)
 -- Function: size_t mpcx_out_str (FILE* STREAM, int BASE, size_t N_DIGITS, mpcx_srcptr F)

     Output F to STREAM using the given BASE and the given number of digits N_DIGITS for the coefficients. If N_DIGITS is 0, then a suitable number of digits is chosen so that reading the polynomial into a variable of the same precision as F yields the same polynomial again (this input function needs yet to be written...).

     The output starts with an opening bracket '(', followed by the degree and a list of coefficients in decreasing order of degree (separated by spaces) and a closing bracket ')'.

     Return the number of written characters.

Basic Polynomial Arithmetic
===========================

 -- Function: void mpfrx_add (mpfrx_ptr H, mpfrx_srcptr F, mpfrx_srcptr G)
 -- Function: void mpcx_add (mpcx_ptr H, mpcx_srcptr F, mpcx_srcptr G)
     Set H to F + G.

 -- Function: void mpfrx_sub (mpfrx_ptr H, mpfrx_srcptr F, mpfrx_srcptr G)
 -- Function: void mpfrx_si_sub (mpfrx_ptr H, const long int F, mpfrx_srcptr G)
 -- Function: void mpcx_sub (mpcx_ptr H, mpcx_srcptr F, mpcx_srcptr G)
 -- Function: void mpcx_si_sub (mpcx_ptr H, const long int F, mpcx_srcptr G)
     Set H to F - G.

 -- Function: void mpfrx_neg (mpfrx_ptr H, mpfrx_srcptr F)
 -- Function: void mpcx_neg (mpcx_ptr H, mpcx_srcptr F)
     Set H to -F.

 -- Function: void mpfrx_mul (mpfrx_ptr H, mpfrx_srcptr F, mpfrx_srcptr G)
 -- Function: void mpfrx_mul_fr (mpfrx_ptr H, mpfrx_srcptr F, mpfr_srcptr G)
 -- Function: void mpfrx_mul_si (mpfrx_ptr H, mpfrx_srcptr F, const long int G)
 -- Function: void mpfrx_mul_ui (mpfrx_ptr H, mpfrx_srcptr F, const unsigned long int G)
 -- Function: void mpcx_mul (mpcx_ptr H, mpcx_srcptr F, mpcx_srcptr G)
 -- Function: void mpcx_mul_c (mpcx_ptr H, mpcx_srcptr F, mpc_srcptr G)
 -- Function: void mpcx_mul_fr (mpcx_ptr H, mpcx_srcptr F, mpfr_srcptr G)
 -- Function: void mpcx_mul_si (mpcx_ptr H, mpcx_srcptr F, const long int G)
 -- Function: void mpcx_mul_ui (mpcx_ptr H, mpcx_srcptr F, const unsigned long int G)
     Set H to F * G.

 -- Function: void mpfrx_mul_x (mpfrx_ptr H, mpfrx_srcptr F, const unsigned int N)
 -- Function: void mpcx_mul_x (mpcx_ptr H, mpcx_srcptr F, const unsigned int N)
     Set H to F * XN

 -- Function: void mpfrx_rem (mpfrx_ptr R, mpfrx_srcptr F, mpfrx_srcptr G)
 -- Function: void mpcx_rem (mpcx_ptr R, mpcx_srcptr F, mpcx_srcptr G)
     Set R to the remainder of F divided by G.

 -- Function: void mpfrcx_real (mpfrx_ptr H, mpcx_srcptr F)
 -- Function: void mpfrcx_imag (mpfrx_ptr H, mpcx_srcptr F)
     Set H to the real or the imaginary part of F, respectively. The prefix mpfrcx indicates the mixed type of the operations, with an mpcx argument and an mpfrx result.

Higher Level Functions
======================

 -- Function: void mpfrx_eval (mpfr_ptr R, mpfrx_srcptr F, mpfr_srcptr X)
 -- Function: void mpcx_eval (mpc_ptr R, mpcx_srcptr F, mpc_srcptr X)
     Set R to the value f(x) of F at X, obtained using a Horner scheme.

 -- Function: void mpfrx_derive (mpfrx_ptr H, mpfrx_srcptr F)
 -- Function: void mpcx_derive (mpcx_ptr H, mpcx_srcptr F)
     Set H to the derivative of F.

 -- Function: void mpfrx_root (mpfr_ptr ROOT, mpfrx_srcptr F)
 -- Function: void mpcx_root (mpc_ptr ROOT, mpcx_srcptr F)
     Computes a root of F. The variable ROOT is supposed to contain an initial approximation, that is refined via Newton iterations until it does not change any more. No special care is taken to avoid infinite loops.

Tree Based Functions
====================

The following functions implement asymptotically fast operations on arrays of polynomials, usually through the use of subproduct trees. Such a tree is a binary tree constructed from an array of polynomials by storing these polynomials in the leaves of the tree. Each parent node contains the product of the child nodes, so that the root of the tree contains the product of all the leaves. Internally, subproduct trees are variables of types mpfrx_tree_t and mpcx_tree_t. (Analogously to the situation with polynomials, in the following, mpfrx_tree_ptr and mpfcx_tree_ptr are used for variables of type mpfrx_tree_t and mpcx_tree_t that may be modified by the function, and mpfrx_tree_srcptr and mpfcx_tree_srcptr for variables that are not modified.)

 -- Function: void mpfrx_tree_init (mpfrx_tree_ptr T, int NO, mpfr_prec_t PREC)
 -- Function: void mpcx_tree_init (mpcx_tree_ptr T, int NO, mpfr_prec_t PREC)
     Initialises T as a subproduct tree with NO leaves in which all polynomials stored in the nodes will have precision PREC. All nodes are initialised by a call to mpfrx_init or mpcx_init, respectively.

 -- Function: void mpfrx_tree_clear (mpfrx_tree_ptr T)
 -- Function: void mpcx_tree_clear (mpcx_tree_ptr T)
     Frees the subproduct tree referenced by T, and all the polynomials stored in its nodes by calls to mpfrx_clear or mpcx_clear, respectively.

 -- Function: void mpfrx_subproducttree (mpfrx_tree_ptr T, mpfrx_t *FACTORS)
 -- Function: void mpcx_subproducttree (mpcx_tree_ptr T, mpcx_t *FACTORS)
     Computes the subproduct tree T whose leaves contains the polynomials in the array FACTORS. The variable T needs to have been initialised by a call to mpfrx_tree_init or mpcx_tree_init, respectively, and FACTORS needs to contain at least as many elements as there are leaves in T. (If there are more elements in FACTORS, the last ones are ignored.)

     So a typical usage is a call to mpfrx_tree_init, followed by a call to mpfrx_subproducttree, and finally a call to mpfrcx_tree_clear.

     FACTORS is not modified by the function.

 -- Function: void mpfrx_tree_get_root (mpfrx_ptr F, mpfrx_tree_srcptr T)
 -- Function: void mpcx_tree_get_root (mpcx_ptr F, mpcx_tree_srcptr T)
     Assigns the root of the tree T to F.

     For instance, if T has been obtained by a call to mpfrx_subproducttree or mpcx_subproducttree, this retrieves the product of all polynomials on the leaves.

 -- Function: void mpfrx_reconstruct (mpfrx_ptr H, mpfrx_t* FACTORS, int NO)
 -- Function: void mpcx_reconstruct (mpcx_ptr H, mpcx_t* FACTORS, int NO)
     Computes the product of the first NO polynomials in the array FACTORS and stores it in H (which may be one of the elements of FACTORS; apart from that, FACTORS is not modified).

     The same effect could be obtained by a call to mpfrx_subproducttree or mpcx_subproducttree, respectively, followed by mpfrx_tree_get_root or mpcx_tree_get_root, respectively. But to save space by a factor of O(log(no)), this function uses a separate implementation.

 -- Function: void mpfrx_hecke (mpfrx_ptr ROP, mpfrx_tree_srcptr SUBPRODUCTS, mpfrx_t *VALS)
 -- Function: void mpcx_hecke (mpcx_ptr ROP, mpcx_tree_srcptr SUBPRODUCTS, mpcx_t *VALS)
     Assume that T has been created (by a call to mpfrx_subproducttree or mpcx_subproducttree, respectively) with the elements of the array FACTORS on its leaves, and let F be the product of all the elements in FACTORS (or, equivalently, the polynomial at the root of SUBPRODUCTTREE). Then the function computes Σ VALS[i]*F/FACTORS[i] and returns the result in ROP. It can be used to compute the Hecke representation of algebraic numbers, whence its name.

 -- Function: void mpfrx_product_and_hecke (mpfrx_t *ROP, mpfrx_t **VALS, int NO_POLS, int NO_FACTORS)
 -- Function: void mpcx_product_and_hecke (mpcx_t *ROP, mpcx_t **VALS, int NO_POLS, int NO_FACTORS)
     Combines one call to mpfrx_subproducttree (resp. mpcx_subproducttree) and one or more calls to mpfrx_hecke (resp. mpcx_hecke) into one function, which allows to not store the subproduct tree and thus to conserve memory without computational overhead. The function behaves as if a subproduct tree were created from VALS[0], which needs to contain NO_FACTORS elements; the root of the tree is returned in ROP[0]. For I from 1 to NO_POLS-1, it then behaves as if it called mpfrx_hecke (resp. mpcx_hecke) with this subproduct tree and VALS[i], which needs to also contain NO_FACTORS values; the result of the operation is stored in ROP[i].

 -- Function: void mpfrx_multieval (mpfr_t* VALUES, mpfr_t* ARGS, int NO, mpfrx_t F)
 -- Function: void mpcx_multieval (mpc_t* VALUES, mpc_t* ARGS, int NO, mpcx_t F)
     Evaluates the polynomial F in the first NO elements of the array ARGS, and store the values in the first NO entries of VALUES (that must exist and already be initalised).

The following functions are convenience functions; they operate more or less like their counterparts without the suffix _from_roots (see the individual functions for small differences), but instead of a list of polynomials, they take as input a list of roots, which are interpreted as linear polynomials with this root.

 -- Function: void mpfrx_reconstruct_from_roots (mpfrx_ptr H, mpfr_t* ROOTS, int NO)
 -- Function: void mpcx_reconstruct_from_roots (mpcx_ptr H, mpc_t* ROOTS, int NO)
     Compute the polynomial H of degree NO that has the elements of ROOTS as roots (potentially with multiplicity).

 -- Function: void mpfrx_subproducttree_from_roots (mpfrx_tree_ptr T, mpfr_t *ROOTS, int NO)
 -- Function: void mpcx_subproducttree_from_roots (mpcx_tree_ptr T, mpc_t *ROOTS, int NO)
     Unlike their counterparts without the _from_roots suffix, these functions also initialise the subproduct tree to the correct size NO; so they should be called with an uninitialised argument T, which needs to be cleared explicitly later.

     This inconsistency is motivated by the corresponding behaviour of mpfrcx_subproducttree_from_roots, described below.

 -- Function: void mpfrx_hecke_from_roots (mpfrx_ptr ROP, mpfrx_tree_srcptr SUBPRODUCTS, mpfr_t *VALS)
 -- Function: void mpcx_hecke_from_roots (mpcx_ptr ROP, mpcx_tree_srcptr SUBPRODUCTS, mpc_t *VALS)
     The functions assume that SUBPRODUCTS has been generated (for instance by a call to mpfrx_subproducttree_from_roots or mpcx_subproducttree_from_roots) from monic linear polynomials; then VALS corresponds to an array of constant polynomials, which are simply passed as complex numbers.

 -- Function: void mpfrx_product_and_hecke_from_roots (mpfrx_t *ROP, mpfr_t **VALS, int NO_POLS, int NO_FACTORS)
 -- Function: void mpcx_product_and_hecke_from_roots (mpcx_t *ROP, mpc_t **VALS, int NO_POLS, int NO_FACTORS)
     The functions work in the same way as mpfrx_products_and_hecke and mpcx_products_and_hecke, except that the elements in vals[0] are interpreted as linear polynomials with the elements as roots, and the other elements in vals as constant polynomials. Otherwise said, they work like a call to mpcx_subproducttree_from_roots or mpfrx_subproducttree_from_roots with vals [0], followed by calls to mpcx_hecke_from_roots or mpfrx_hecke_from_roots with vals [i] for I from 1 to NO_POLS-1.

The following functions go one step further: They work with real polynomials given by their complex roots; this ``mixed'' nature of the operations is indicated by the prefix mpfrcx instead of mpfrx or mpcx. To use these functions, one needs to indicate whether a root is real or complex, and in the latter case, how the roots are paired. So together with an array ROOTS of elements of type mpc_t, one needs to pass an array of integers CONJUGATES of the same length, where conjugates [i] == j if and only if roots [j] is the complex conjugate of roots [i]. In particular,
conjugates [i] == i if and only if roots [i] is in fact
real. To save memory space, only the first element of each complex-conjugate pair needs to be set, that is, the one with conjugates [i] >= i. Internally, the functions work with linear or quadratic real polynomials obtained by regrouping the roots. For a numerical example, see the following function description.

 -- Function: void mpfrcx_reconstruct_from_roots (mpfrx_ptr H, mpc_t* ROOTS, int* CONJUGATES, int NO)
     Compute the polynomial H of degree NO from its roots given in ROOTS and paired, as seen above, through CONJUGATES.

     For instance, the function may be called with no == 3, roots ==  { (1.2599 0), (-0.6299 1.0911), NULL }  and conjugates == { 1, 3, 2 } ; it then computes the result X^3-2 (modulo some rounding errors) as the product of the linear real polynomial X - 1.2599 and the quadratic real polynomial X^2 + 1.2599 X + 1.5874.

 -- Function: void mpfrcx_subproducttree_from_roots (mpfrx_ptr H, mpc_t* ROOTS, int* CONJUGATES, int NO)
     The function initialises the subproducttree to the correct size, which depends not only on NO, but on the exact number n_1 of real roots and n_2 of pairs of complex-conjugate roots. The tree has n_1+n_2 leaves, with n_1 linear and n_2 quadratic polynomials. The function then computes the subproduct tree, with a polynomial of degree NO= n_1+2n_2 at its root.

 -- Function: void mpfrcx_hecke_from_roots (mpfrx_ptr H, mpfrx_tree_srcptr SUBPRODUCTS, mpc_t *VALS, mpc_t *ROOTS, int *CONJUGATES)
     The function works like mpcx_hecke_from_roots, returning a real polynomial in H, assuming that VALS is an array of real values and pairs of complex-conjugate values corresponding to the roots in ROOTS, paired according to the same array CONJUGATES. It is necessary to pass ROOTS again for constructing the linear real interpolation polynomial for a pair of complex-conjugate values without factoring the corresponding quadratic polynomial on a leaf of SUBPRODUCTS.

 -- Function: void mpfrcx_product_and_hecke_from_roots (mpfrx_t *ROP, mpc_t **VALS, int *CONJUGATES, int NO_POLS, int NO_FACTORS)
     The function works exactly like mpcx_product_and_hecke_from_roots, except that the result is known to be real since all elements of VALS are paired up into complex-conjugate pairs according to CONJUGATES.

Functions for Galois Field Towers
=================================

The functions in this section decompose a solvable Galois number field extension into a tower of extensions, following
Andreas Enge and François Morain:
Fast Decomposition of Polynomials with Known Galois Group.
They have been written in the context of complex multiplication of elliptic curves, for either Hilbert or ray class fields of imaginary-quadratic number fields, or their real subfields, but could be applied in other contexts; abelian extensions of the rationals come to mind, but in principle also Galois extensions of higher degree number fields can be handled.

The general setting is as follows: Let L/Q, where Q is the field of rational numbers, be a Galois number field with Galois group G = (g_0, ..., g_h-1). We assume that a fixed complex embedding of L has been chosen, and that L is given by the corresponding embedding of a generating element x and the action of the Galois group on this element; in other words, by an ordered list (x_0, ..., x_h-1) of complex numbers such that x_i = x^g_i. Moreover, we assume the knowledge of a normal series for G, that is, 1 = H_l-1 < H_l-2 < ... < H_0 < H_-1 = G such that each subgroup H_i is normal in H_i-1. Let L_i be the fixed field of H_i, such that L_l-1 = L and L_-1 = Q. Then we obtain a Galois tower in which L/L_i has group H_i, the extension L_i/Q has group G/H_i, and the extension L_i/L_i-1 has group H_i-1/H_i. For instance, in the abelian case, such a normal series exists such that each quotient H_i-1/H_i is cyclic of prime order. In the case of a ray class field L over an imaginary-quadratic number field K, the Galois group G is a semi-direct product of the (abelian) ray class group and the group of order 2 generated by the complex conjugation automorphism. One may then choose all the H_i down to H_0 such that they do not contain complex conjugation, that is, as subgroups of the ray class group; then L_0=K, so that alongside the extension L/Q, we have also decomposed the Galois extension L/K.

Galois field towers are stored in variables of type mpcx_tower_t; again, pointers to modifiable or unmodifiable towers exist, of types mpcx_tower_ptr and mpcx_tower_srcptr, respectively. The type is defined as a (one-dimensional array of a) C struct containing the following fields:
typedef struct {
   int levels;
   int* d;
   int deg;
   mpcx_t** W;
}

Here, levels is the length of the normal series (called l above). The array entry d[i] stores the relative degree of L_i/L_i-1. The variable deg stores the total degree of the extension L/Q (called h above), which is also the product of all the d[i]. Finally W[i] for i from 1 up to levels-1 holds (after computation) the relative minimal polynomial of a generator of L_i/L_i-1, given by its Hecke representation. Otherwise said, if the absolute extension L_i-1/Q has the minimal polynomial V_i-1 in the variable X_i-1, then W[i] stores the minimal polynomial of X_i, multiplied by the derivative V_i-1'. It is thus a (non-monic, with leading coefficient V_i-1') polynomial of degree d[i] in the variable X_i, the coefficients of which are polynomials in the variable X_i-1, stored in W[i][0] up to W[i][d[i]].

To be consistent with this, the variable W[0] would have to hold V_0 as an array of d[0] constant polynomials in the variable X_0; instead, we chose to use an array of length 1 for W[0] and to let its unique entry W[0][0] directly hold V_0.

 -- Function: void mpcx_tower_init (mpcx_tower_ptr TWR, int L, int* D, mpfr_prec_t PREC)
     Initialises TWR to hold a Galois tower, where L as above is the length of the Galois group decomposition, D the sequence of relative degress as explained above, and PREC is the common precision used for all subsequent computations.

 -- Function: void mpcx_tower_clear (mpcx_tower_ptr TWR)
     Clears TWR and all its components.

 -- Function: void mpcx_tower_decomposition (mpcx_tower_ptr TWR, mpc_t *ROOTS)
     Given an initialised Galois tower TWR, and a generating element of the extension L/Q together with its conjugates under the Galois group in an order compatible with the normal series as explained above in ROOTS, computes absolute and relative extensions corresponding to the subfield tower and stores them in TWR. The precisions of the elements in ROOTS should match the precision with which TWR has been initialised.

     The function chooses as generators ``small'' elementary-symmetric expressions under the action of the relative Galois groups; for instance, if possible the relative trace is preferred, then sums of products of two roots, and so on. The question whether an element generates a subfield is answered on a heuristic basis, since equality of elements cannot be rigorously determined in the presence of rounding errors; so there is a very small risk of the function not finding a generator of a subfield.

     Notice that the defining polynomials of all field extensions should have rational coefficients (or even integral rational coefficients if the generating element in roots[0] is an algebraic integer), but that the identification is not carried out by the function, and that all polynomials are stored with complex coefficients. So this function may in fact also be called when the base field L_-1 is not the field of rational numbers, as long as a suitable function is called afterwards that obtains the symbolic expressions in L_-1 of the coefficients of the generated polynomials from their image under the fixed complex embedding of L, which also induces a fixed embedding of L_-1.

The following variants of the data structures and functions treat a generalisation to an important non-Galois case, that of the real subfields of class fields of imaginary-quadratic number fields. These fields do not form Galois towers, but being the  ``projection'' under complex conjugation, they behave very similarly to extensions of Q that have subgroups of the class group as Galois groups. The mathematical and algorithmic details are described in
Andreas Enge and François Morain:
Fast Decomposition of Polynomials with Known Galois Group.

Roughly speaking, all occurring polynomials are real, and their roots split into real roots and complex-conjugate pairs of complex roots. Since comparison of floating point numbers with rounding errors is a thorny problem, the user is expected to provide the functions with an indication of which roots are paired up; in the targeted application, this information can generally be derived symbolically from the class group.

Such field towers are stored in variables of type mpfrx_tower_t, with pointers mpfrx_ptr to modifiable and mpfrx_srcptr to unmodifiable towers. The type is defined as a (one-dimensional array of a) C struct containing the following fields:
typedef struct {
   int levels;
   int* d;
   int deg;
   mpfrx_t** W;
}
The only difference to mpcx_tower_t is that the polynomials are real instead of complex.

 -- Function: void mpfrx_tower_init (mpfrx_tower_ptr TWR, int L, int* D, mpfr_prec_t PREC)
 -- Function: void mpfrx_tower_clear (mpfrx_tower_ptr TWR)
     These functions behave exactly like their complex counterparts.

 -- Function: void mpfrcx_tower_decomposition (mpfrx_tower_ptr TWR, mpc_t *ROOTS, int *CONJUGATES)
     The function behaves exactly like its complex counterpart mpcx_tower_decomposition. Together with the list ROOTS of complex roots of the class polynomial, in an order compatible with the tower field structure, it expects an array CONJUGATES that designates the pairing of the roots: conjugates [i] == j if and only if roots [j] is the complex conjugate of roots [i]. In particular,
     conjugates [i] == i if and only if roots [i] is in fact
     real. To save memory space, only the first element of each complex-conjugate pair needs to be set, that is, the one with conjugates [i] >= i.

     The prefix mpfrcx of the function name indicates the ``mixed'' nature of the operation: While the results are real, the input values are still of complex type (reflecting that the number fields L_i all have at least one real embedding, but need not be totally real).

Contributors
************

The main developer of the MPFRCX library is Andreas Enge. The functions for Galois field towers are co-authored by Jared Asuncion.

References
**********

  * Torbjörn Granlund et al. gmp -- GNU multiprecision library. Version 5.0.2, http://gmplib.org/

  * Guillaume Hanrot, Vincent Lefèvre, Patrick Pélissier, Philippe Théveny and Paul Zimmermann. mpfr -- A library for multiple-precision floating-point computations with exact rounding. Version 3.1.0, http://www.mpfr.org/

  * Andreas Enge, Mickaël Gastineau, Philippe Théveny and Paul Zimmermann. mpc -- A library for multiprecision complex arithmetic with exact rounding. Version 0.9, http://mpc.multiprecision.org/

  * Andreas Enge and François Morain. Fast Decomposition of Polynomials with Known Galois Group. In Marc Fossorier, Tom Høholdt and Alain Poli (eds.): Applied Algebra, Algebraic Algorithms and Error-Correcting Codes — AAECC-15, vol. 2643 of Lecture Notes in Computer Science, Springer-Verlag, Berlin 2003, pp. 254–264 Extended version: https://www.math.u-bordeaux.fr/~aenge/papers/galois_long.ps.gz

GNU Free Documentation License
******************************

     [file fdl-1.3.texi not included]