PolynomialTools - Maple Programming Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Optimization : PolynomialTools/MinimalPolynomial

PolynomialTools

  

MinimalPolynomial

  

find minimal polynomial for an exact or approximate root

  

AnnihilatingPolynomial

  

find an annihilating polynomial for an approximate root

 

Calling Sequence

Parameters

Options

Description

Examples

Compatibility

Calling Sequence

MinimalPolynomial(r, x)

MinimalPolynomial(r, x, n, acc)

AnnihilatingPolynomial(r, x, n, acc)

Parameters

r

-

exact or approximate root

x

-

(optional) variable name

n

-

an upperbound on the degree of the polynomial sought

Options

• 

acc 

  

desired accuracy of the approximation

• 

digits : posint

  

A value for Digits to be used for all numerical computations.

Description

• 

The MinimalPolynomial and AnnihilatingPolynomial functions find a polynomial with integer coefficients which has the algebraic number r as one of its roots.

• 

If r is an exact algebraic number, and n and acc are not given, then MinimalPolynomial calls evala/Minpoly to compute an exact minimal polynomial of r.

• 

Otherwise the AnnihilatingPolynomial and MinimalPolynomial functions, use a lattice-based algorithm to find a polynomial of degree n (or less) with small integer coefficients which has the given approximation r of an algebraic number as one of its roots.  They differ in that, the output of MinimalPolynomial is guaranteed to be an irreducible polynomial, while the output of AnnihilatingPolynomial is the raw output of the lattice algorithm.

• 

If a name is not specified for the variable x, then _X is used.

• 

The root r may be real or complex.  It may be input as a floating-point approximation to a root or as an exact algebraic number.  In the latter case, if an approximate algorithm is being used, r will first be evaluated in floating point at Digits precision using evalf.

• 

The value accfr is given the same weight as the coefficients in determining f, the minimal polynomial. If it is not specified, the default value for acc is 10Digits2max1,rn.  Larger values indicate the desire for better approximations.

• 

This function is part of the PolynomialTools package, and so it can be used in the form MinimalPolynomial(..) only after executing the command with(PolynomialTools). However, it can always be accessed through the long form of the command by using PolynomialTools[MinimalPolynomial](..).

Examples

withPolynomialTools:

rfevalf1+sqrt2

rf2.414213562

(1)

MinimalPolynomialrf,x,2

x22x1

(2)

r1+sqrt2

r1+2

(3)

When r is exact, and no degree bound given, an exact method is used

MinimalPolynomialr10,x

100x220x1

(4)

Otherwise the lattice-based approximation is used

MinimalPolynomialr10,x,25

25x12+8x117x1021x9+14x82x7+9x6+14x5+5x44x3+4x25x+1

(5)

If r is less than 1, and the accuracy is set low by default, and the output of AnnihilatingPolynomial could be a simple monomial.

AnnihilatingPolynomialr10,x,25,10.10

x16

(6)

Setting the accuracy higher can help avoid such trivial output.

AnnihilatingPolynomialr10,x,25,10.25

x21x19+2x18+2x17+8x16+4x15x14+4x133x123x116x105x94x8+3x7+x68x5+4x35x2+x

(7)

MinimalPolynomial1.234,3

22_X35_X2+61_X109

(8)

fsolve,_X

1.234000001

(9)

Sometimes the exact and approximate algorithms will agree but it is not guaranteed. The approximate algorithm typically be faster.

ssqrt2+sqrt3

s2+I3

(10)

MinimalPolynomials,x

x4+2x2+25

(11)

MinimalPolynomials,x,4

x4+2x2+25

(12)

taddsqrt1i+1ithprimei,i=1..3

t2+I3+5

(13)

PCodeTools:-UsageMinimalPolynomialt,x

memory used=13.07MiB, alloc change=8.00MiB, cpu time=62.00ms, real time=62.00ms, gc time=0ns

Px816x6+184x4+960x2+3600

(14)

The numeric algorithm is faster, but does not get the exact answer unless the working precision is increased

CodeTools:-UsageMinimalPolynomialt,x,degreeP,x

memory used=1.24MiB, alloc change=0 bytes, cpu time=20.00ms, real time=19.00ms, gc time=0ns

2x715x6+38x5+6x4177x3+453x2+139x146

(15)

CodeTools:-UsageMinimalPolynomialt,x,degreeP,x,digits=25

memory used=2.77MiB, alloc change=0 bytes, cpu time=23.00ms, real time=24.00ms, gc time=0ns

x816x6+184x4+960x2+3600

(16)

Compatibility

• 

The output of MinimalPolynomial(r, n, acc) prior to Maple 18 used the variable x.  As of Maple 18, the default variable used is _X. You can change this using the x argument.

• 

As of 2020, MinimalPolynomial(r, x) calls evala(Minpoly(r,x)) if r is an exact algebraic number. To force the previous behavior, r can be replaced with evalf(r) in the calling sequence or an explicit degree bound can be passed as a second or third argument.

• 

The PolynomialTools[AnnihilatingPolynomial] command was introduced in Maple 18.

• 

The PolynomialTools[MinimalPolynomial] command was updated in Maple 18.

• 

The x parameter was introduced in Maple 18.

• 

For more information on Maple 18 changes, see Updates in Maple 18.

• 

The r parameter was updated in Maple 2020.

• 

The 'digits' option was introduced in Maple 2020.

• 

For more information on Maple 2020 changes, see Updates in Maple 2020.

See Also

evala/Minpoly

evala/Norm

IntegerRelations[LLL]

LinearAlgebra[MinimalPolynomial]