Probabilistic Algorithm Control - Maple Help
For the best experience, we recommend viewing online help using Google Chrome or Microsoft Edge.

Online Help

All Products    Maple    MapleSim

Home : Support : Online Help : Mathematics : Linear Algebra : Probabilistic Algorithm Control

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.


Computation of the univariate resultant of two cyclotomic polynomials






Without the probabilistic approach, this is much more expensive









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