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.
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
p1 ≔ NumberTheoryCyclotomicPolynomial⁡1501,x:
p2 ≔ NumberTheoryCyclotomicPolynomial⁡1502,x:
t1 ≔ time⁡resultant⁡p1,p2,x
Without the probabilistic approach, this is much more expensive
_EnvProbabilistic ≔ 0:
t2 ≔ time⁡resultant⁡p1,p2,x
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.
Download Help Document