Goto Chapter: Top 1 2 3 4 Bib Ind

### 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
 ‣ FLOAT_PSEUDOFIELD ( global variable )

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
 ‣ PSLQ( x, epsilon[, gamma] ) ( function )
 ‣ PSLQ_MP( x, epsilon[, gamma[, beta]] ) ( function )

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).

Goto Chapter: Top 1 2 3 4 Bib Ind

generated by GAPDoc2HTML