Probabilistic_Algorithms - Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Probabilistic_Algorithms

Probabilistic Algorithm Control in Maple

  

Several algorithms in Maple have a probabilistic implementation of Monte-Carlo type.  This means that the output of the algorithm may be incorrect, but with (controllably) very low probability. Typically these are algorithms that compute values modulo a sequence of primes, then perform reconstruction to obtain an integer or rational result. Termination is controlled by either bounding the product of the primes required to reconstruct the result (thus making the algorithm deterministic) or terminating when the reconstructed result does not change for several primes in a row (thus making the output probabilistic). Probabilistic algorithms are useful when it is not possible to efficiently compute a good bound.

  

In cases where the deterministic bound can be poor, but is not expensive to compute, a competing bounds model is used, and the algorithm terminates when either the probabilistic bound or deterministic bound is met, whichever comes first.

  

Algorithms with this type of probabilistic implementations include:

• 

Determinant: integer Matrices

• 

LinearSolve: integer Matrices

• 

CharacteristicPolynomial: integer Matrices

• 

Eigenvalues: uses CharacteristicPolynomial

• 

resultant: bivariate with integer coefficients

  

 

  

In cases where the deterministic bound can be expensive to compute (as expensive or more expensive than computing the actual result) only the probabilistic bound is used by default, and the deterministic bound can only be used if the probabilistic aspect of the algorithm is disabled.

  

Algorithms with this type of probabilistic implementations include:

• 

resultant: univariate with integer coefficients

  

The probabilistic behavior of these functions can be controlled by setting the _EnvProbabilistic environment variable. The value of _EnvProbabilistic may be set as follows:

• 

true or unset: probability bound is set to 1.10−30

• 

false or 0: probability bound is set to 0, meaning the algorithm is deterministic

• 

numeric value: this must be a value between 0 and 0.00004, and sets the probability bound

  

Note that in many cases the deterministic bound can be arbitrarily larger than the problem requires, and in these cases the use of the probabilistic approach can achieve great gains over a pure deterministic implementation. Setting _EnvProbabilistic:=false can cause extreme slowdowns for many computations.

Examples

Computation of the univariate resultant of two cyclotomic polynomials

p1NumberTheoryCyclotomicPolynomial1501,x:

p2NumberTheoryCyclotomicPolynomial1502,x:

t1timeresultantp1,p2,x

t10.005

(1)

Without the probabilistic approach, this is much more expensive

forgetresultant:

_EnvProbabilistic0:

t2timeresultantp1,p2,x

t20.378

(2)

t2t1

75.60000000

(3)

and in fact computation of the resultant bound alone requires more than 10 times the total time required to compute the probabilistic answer on this extreme example.

See Also

LinearAlgebra[CharacteristicPolynomial]

LinearAlgebra[Determinant]

LinearAlgebra[LinearSolve]

resultant