Probabilistic_Algorithms - Maple Help

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
 •
 • 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 $\mathrm{_EnvProbabilistic}$ environment variable. The value of $\mathrm{_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

 > $\mathrm{p1}≔\mathrm{NumberTheory}\left[\mathrm{CyclotomicPolynomial}\right]\left(1501,x\right):$
 > $\mathrm{p2}≔\mathrm{NumberTheory}\left[\mathrm{CyclotomicPolynomial}\right]\left(1502,x\right):$
 > $\mathrm{t1}≔\mathrm{time}\left(\mathrm{resultant}\left(\mathrm{p1},\mathrm{p2},x\right)\right)$
 ${\mathrm{t1}}{≔}{0.004}$ (1)

Without the probabilistic approach, this is much more expensive

 > $\mathrm{forget}\left(\mathrm{resultant}\right):$
 > $\mathrm{_EnvProbabilistic}≔0:$
 > $\mathrm{t2}≔\mathrm{time}\left(\mathrm{resultant}\left(\mathrm{p1},\mathrm{p2},x\right)\right)$
 ${\mathrm{t2}}{≔}{0.316}$ (2)
 > $\frac{\mathrm{t2}}{\mathrm{t1}}$
 ${79.00000000}$ (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.