[MathJax off]

3 Polynomials

3.1 The Floats pseudo-field

Polynomials with floating-point coefficients may be manipulated in GAP; though they behave, in subtle ways, quite differently than polynomials over rings. A "pseudo-field" of floating-point numbers is available to create them using the standard GAP syntax.

3.1-1 FLOAT_PSEUDOFIELD

The "pseudo-field" of floating-point numbers, containing all floating-point numbers in the current implementation.

Note that it is not really a field, e.g. because addition of floating-point numbers is not associative. It is mainly used to create indeterminates, as in the following example:

gap> x := Indeterminate(FLOAT_PSEUDOFIELD,"x");
x
gap> 2*x^2+3;
2.0*x^2+3.0
gap> Value(last,10);
203.0

3.2 Roots of polynomials

The Jenkins-Traub algorithm has been implemented, in arbitrary precision for MPFR and MPC.

Furthermore, CXSC can provide complex enclosures for the roots of a complex polynomial.

3.3 Finding integer relations

The PSLQ algorithm has been implemented by Steve A. Linton, as an external contribution to Float. This algorithm receives as input a vector of floats \(x\) and a required precision \(\epsilon\), and seeks an integer vector \(v\) such that \(|x\cdot v|<\epsilon\). The implementation follows quite closely the original article [BB01].

3.3-1 PSLQ

Returns: An integer vector \(v\) with \(|x\cdot v|<\epsilon\).

The PSLQ algorithm by Bailey and Broadhurst (see [BB01]) searches for an integer relation between the entries in \(x\).

\(\beta\) and \(\gamma\) are algorithm tuning parameters, and default to \(4/10\) and \(2/\sqrt(3)\) respectively.

The second form implements the "Multi-pair" variant of the algorithm, which is better suited to parallelization.

gap> PSLQ([1.0,(1+Sqrt(5.0))/2],1.e-2);

[ 55, -34 ] # Fibonacci numbers
gap> RootsFloat([1,-4,2]*1.0);

[ 0.292893, 1.70711 ] # roots of 2x^2-4x+1
gap> PSLQ(List([0..2],i->last[1]^i),1.e-7);

[ 1, -4, 2 ] # a degree-2 polynomial fitting well

3.4 LLL lattice reduction

A faster implementation of the LLL lattice reduction algorithm has also been implemented. It is accessible via the commands FPLLLReducedBasis(m) and FPLLLShortestVector(m).

generated by GAPDoc2HTML